Javascript/Typescript 스택, 큐, 힙, 정렬

자바 스크립트에서 스택을 구현하는 방법

class Stack {
    array;
    constructor() {
        this.array = [];
    }
    public push(data) {
        this.array.push(data); // 배열에 요소를 추가한다
    }
    public pop() {
        return this.array.pop(); // 배열의 맨 뒤에서 요소를 빼낸다.
    }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

자바스크립트에서 큐를 구현하는 방법

class Queue {
    array = [];
    /**
     * enqueue
     */
    public enqueue(data) {
        this.array.push(data); // 배열에 요소를 추가한다
    }
    /**
     * dequeue
     */
    public dequeue() {
        return this.array.shift(); // 첫번째 요소를 반환하고 제거한다.
    }
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());

자바스크립트에서 힙을 구현하는 방법

- 힙은 특정한 규칙을 가지는 트리의 일종입니다. 힙을 이용해서 우선순위 큐를 구현할 수 있습니다.

여기서 말하는 일정한 규칙에 따라서 힙은 두 종류로 나뉩니다.

최대힙과 최소힙으로 나뉩니다.

최대 힙은 완전트리이면서 루트가 자식보다 커야 합니다.

최소 힙은 완전트리이면서 루트가 자식보다 작아야 합니다.

 

완전트리는 노드가 순서대로 들어가있는 트리를 말합니다.

힙은 아래와 같은 규칙으로 구현합니다.

부모 노드 기준으로 왼쪽의 인덱스는 부모 * 2 입니다.

오른 쪽은 부모 * 2 + 1을 하면 됩니다.