with JavaScripts Study Days 9-11

210519 수요일 9~11일차

# 8일차 복습

CH3 리스트

• #1 : 현재 리스트의 모든 요소보다 클 때만 요소를 삽입하는 함수를 구현하시오. 여기서 크다는 의미는 숫자일 때는 크기를 비교하고, 텍스트일 때는 알파벳순으로 나중을 의미한다.

• #2 현재 리스트의 모든 요소보다 작을 때만 요소를 삽입하는 함수를 구현하시오.

• #3 사람의 이름과 성별을 저장하는 Person 클래스를 구현하시오. 최소한 10개의 Person 객체를 포함하는 리스트를 만드시오. 리스트에서 같은 성별을 가진 사람을 모두 출력하는 함수를 구현하시오.

CH4 스택

• 가장 윗 부분에서만 자료의 추가/삭제가 일어나므로 실행속도가 빠르고 구현이 쉽다.

• 후입선출로 밑바닥에 있는 요소에 접근하려면 모든 요소를 제거하는 수 밖에 없다.

• Top은 pop으로 확인할 수 있지만 요소를 꺼내기 때문에 peek으로 내용을 확인한다. peek은 top - 1의 위치에 접근해 스택의 탑 요소를 확인한다. (스택의 요소가 3이면 top(length)는 3이고 배열의 가장 오른쪽 값은 가장 윗 값이므로 top-1이 top에 있는 요소의 인덱스다.

• 진법 변환

• 회문

• 재귀

210519 수요일 9~11일차

CH5 큐

5.1 큐 동작

5.2 배열 기반의 Queue 클래스 구현

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

let q = new Queue();
q.enqueue("M");
q.enqueue("C");
q.enqueue("J");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue: " + q.front());
console.log("Back of queue: " + q.back());

5.3 Queue 클래스 사용하기 : 스퀘어 댄스 파티에서 파트너 정하기

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function Dancer(name, sex) {
    this.name = name;
    this.sex = sex;
}

function getDancers(males, females) {
// # : text file 읽기const fs = require("fs");
    const names = fs.readFileSync("dancers.txt").toString().split("\n");

// # : trim()으로 앞뒤로 붙어 있는 공백을 없애준다.for (let i = 0; i < names.length; ++i) {
        names[i] = names[i].trim();
    }

    for (let i = 0; i < names.length; ++i) {
// # : 각 행을 sex, name으로 구분하게 한다.let dancer = names[i].split(" ");
// console.log(dancer[0], dancer[1]);let sex = dancer[0];
        let name = dancer[1];
        if (sex === "F") {
            females.enqueue(new Dancer(name, sex));
        } else {
            males.enqueue(new Dancer(name, sex));
        }
    }
}

function dance(males, females) {
    console.log("The dance partners are: \n");
    while (!females.empty() && !males.empty()) {
// # : 남자, 여자 댄서를 짝 짓고 공표한다.let person1 = females.dequeue();
        let person2 = males.dequeue();
        console.log(
            "Female dancer is: " + person1.name,
            "and the male dancer is: " + person2.name
        );
    }
}

let maleDancers = new Queue();
let femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
// if (!femaleDancers.empty()) {//     console.log(femaleDancers.front().name + " is waiting to dance.");// }// if (!maleDancers.empty()) {//     console.log(maleDancers.front().name + " is waiting to dance.");// }// # : 여기서는 얼마나 많은 수의 댄서가 기다리고 있는지 알 수 없다. 큐의 요소 수를 출력하는 함수를 추가한다.function count() {
    return this.dataStore.length;
}

if (femaleDancers.count() > 0) {
    console.log(
        "There are " +
            femaleDancers.count() +
            " female dancers waiting to dance."
    );
}
if (maleDancers.count() > 0) {
    console.log(
        "There are " + maleDancers.count() + " male dancers waiting to dance."
    );
}

5.4 큐로 데이터 정렬하기

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function count() {
    return this.dataStore.length;
}

// @ : 큐로 데이터 정렬하기, 기수 정렬, 1의 자리 기준으로 숫자 정렬 후 10의 자리 기준으로 숫자 정렬. 각 숫자당 1개의 큐이므로 9개의 큐가 필요하다.function distribute(nums, queues, n, digit) {
    for (let i = 0; i < n; ++i) {
        if (digit === 1) {
            queues[nums[i] % 10].enqueue(nums[i]);
        } else {
            queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
        }
    }
}
// @ : 큐에 저장된 숫자를 수집하는 함수function collect(queues, nums) {
    let i = 0;
    for (let digit = 0; digit < 10; ++digit) {
        while (!queues[digit].empty()) {
            nums[i++] = queues[digit].dequeue();
        }
    }
}

function dispArray(arr) {
    for (let i = 0; i < arr.length; ++i) {
        console.log(arr[i] + " ");
    }
}

let queues = [];
for (let i = 0; i < 10; ++i) {
    queues[i] = new Queue();
}
let nums = [];
for (let i = 0; i < 10; ++i) {
    nums[i] = Math.floor(Math.floor(Math.random() * 101));
}
console.log("Before radix sort: ");
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
console.log("\n\nAfter radix sort: ");
dispArray(nums);

5.5 우선순위 큐

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function count() {
    return this.dataStore.length;
}

// # : 우선순위 큐// # : 예진 간호사가 환자 검사 >> 환자상태평가로 우선순위 코드 부여 >> 우선순위 높으면 먼저 진료받음(우선순위 코드가 같으면 선입선출)function Patient(name, code) {
    this.name = name;
    this.code = code;// 우선순위 or 심각성
}
// # : 가장 높은 우선순위(1 > 2 > 3 > 4 > ,,,) 삭제function dequeue() {
    let entry = 0;
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i].code < this.dataStore[entry].code) {
            console.log(
                "deq",
                this.dataStore[i].code,
                this.dataStore[entry].code
            );

            entry = i;
            console.log("ent: ", entry);
        }
    }
    return this.dataStore.splice(entry, 1);
}
// # : 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr +=
            this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
    }
    return retStr;
}
// # : worklet p = new Patient("Smith", 5);
let ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);
p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
console.log(ed.toString());
let seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
// 다음 환자 치료
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());

5.6 연습문제

// # : # 1. Queue 클래스를 고쳐서 Deque 클래스를 만드시오.// # : Deque는 큐와 비슷한 자료구조로 리스트의 앞부분과 끝부분 모두에서 요소의 삽입과 삭제가 일어난다.// # : 프로그램을 이용해 구현한 Deque 클래스를 테스트하시오.function Deque() {
    this.dataStore = [];
    this.push_front = push_front;
    this.push_back = push_back;
    this.pop_front = pop_front;
    this.pop_back = pop_back;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
// # :  push_front() : 맨 앞에 새로운 요소를 삽입한다.// # :  push_back() : 맨 뒤에 새로운 요소를 삽입한다.// # :  pop_front() : 맨 앞에 요소를 제거한다.// # :  pop_back() : 맨 뒤에 요소를 제거한다.// ! : splice(맨 앞 인덱스, 0, 추가하려는 요소)를 이용한다. 두 번째 인자의 길이만큼 삭제하지만 0이면 추가.function push_front(element) {
    this.dataStore.splice(0, 0, element);
}
function push_back(element) {
    this.dataStore.push(element);
}
function pop_front() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}
// ! : back함수에서 length-1을 사용하듯 맨 뒤의 요소에 대한 인덱스를 가져와서 해당 인덱스를 splice로 삭제한다.function pop_back() {
    return this.dataStore.splice(this.dataStore.length - 1, 1);// 배열 앞부분에 저장된 요소를 1개 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

let dq = new Deque();
dq.push_front("M");
dq.push_front("C");
dq.push_front("J");
console.log(dq.toString());
dq.pop_front();
console.log(dq.toString());
dq.pop_back();
console.log(dq.toString());
dq.push_back("A");
dq.push_back("B");
console.log(dq.toString());
console.log("Front of dequeue: " + dq.front());
console.log("Back of dequeue: " + dq.back());

// # : # 2. 1번에서 구현한 Deque 클래스를 이용해 주어진 단어가 회문인지 검사하는 프로그램을 만드시오.function Deque() {
    this.dataStore = [];
    this.push_front = push_front;
    this.push_back = push_back;
    this.pop_front = pop_front;
    this.pop_back = pop_back;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
function push_front(element) {
    this.dataStore.splice(0, 0, element);
}
function push_back(element) {
    this.dataStore.push(element);
}
function pop_front() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}
function pop_back() {
    return this.dataStore.splice(this.dataStore.length - 1, 1);// 배열 앞부분에 저장된 요소를 1개 삭제
}
function front() {
    return this.dataStore[0];
}
function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// # : 문자열이 한줄로 나오도록 수정function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i];
    }
    return retStr;
}
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}
function palindrome(str) {
    let dq = new Deque();

    for (let i = 0; i < str.length; ++i) {
        dq.push_front(str[i]);
    }
    console.log(dq.toString());
    if (str === dq.toString()) {
        console.log("회문입니다.");
    } else {
        console.log("회문 아닙니다.");
    }
}

palindrome("reaer");
palindrome("alsdjfalsdjf");
palindrome("racecar");
palindrome("hello");

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift();// 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function count() {
    return this.dataStore.length;
}

// # : 우선순위 큐// # : 예진 간호사가 환자 검사 >> 환자상태평가로 우선순위 코드 부여 >> 우선순위 높으면 먼저 진료받음(우선순위 코드가 같으면 선입선출)function Patient(name, code) {
    this.name = name;
    this.code = code;// 우선순위 or 심각성
}
// ! : 가장 높은 우선순위(,,, > 4 > 3 > 2 > 1) 삭제function dequeue() {
    let entry = 0;
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i].code > this.dataStore[entry].code) {
            console.log(
                "deq",
                this.dataStore[i].code,
                this.dataStore[entry].code
            );

            entry = i;
            console.log("ent: ", entry);
        }
    }
    return this.dataStore.splice(entry, 1);
}
// # : 출력function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr +=
            this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
    }
    return retStr;
}
// # : worklet p = new Patient("Smith", 5);
let ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);
p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
console.log(ed.toString());
let seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
// 다음 환자 치료
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());