자바스크립트 덱(Deque) 구현

덱(Deque)이란?

덱(Deque, Double-ended queue)이란 큐의 앞, 뒤에서 모두 원소를 삽입, 삭제할 수 있는 자료구조를 말한다.
간단히 말하면 큐(Queue)와 스택(Stack)이 합쳐진 느낌이다.

이미지 출처: https://www.geeksforgeeks.org/deque-in-javascript/

자바스크립트의 배열은 shift(), unshift()함수를 사용해서 배열의 앞 혹은 뒤에 데이터를 삽입하거나 삭제할 수 있지만, 데이터를 앞에서부터 삽입하거나 삭제하는 작업은 배열의 전체 원소를 한 칸씩 밀거나 한 칸씩 앞으로 당겨오는 작업이 필요하기 때문에 $O(N)$의 시간이 든다.

반면에 Deque를 사용하면 데이터의 삽입과 삭제를 큐의 앞에서 하든 뒤에서 하든 $O(1)$의 시간복잡도로 수행할 수 있다.

Deque이 사용되는 알고리즘

0-1 BFS

시간복잡도

이미지 출처: https://www.geeksforgeeks.org/deque-set-1-introduction-applications/

구현

class Deque {
    constructor() {
        this.deque = {};
        this.front = 0;
        this.rear = 0;
    }
    pushFront(element) {
        if (this.deque[this.front] === undefined) this.deque[this.front] = element;
        else {
            this.front--;
            this.deque[this.front] = element;
        }
    }
    popFront() {
        const temp = this.deque[this.front];
        delete this.deque[this.front];
        this.front++;
        if (this.front > this.rear) {
            this.front = this.rear = 0;
        }
        return temp;
    }
    pushBack(element) {
        if (this.deque[this.rear] === undefined) this.deque[this.rear] = element;
        else {
            this.rear++;
            this.deque[this.rear] = element;
        }
    }
    popBack() {
        const temp = this.deque[this.rear];
        delete this.deque[this.rear];
        this.rear--;
        if (this.front > this.rear) {
            this.front = this.rear = 0;
        }
        return temp;
    }
    size() {
        if (this.deque[this.front] === undefined) return 0;
        return this.rear - this.front + 1;
    }
}

const deque = new Deque();
deque.pushFront(0);
console.log(deque.size()); // 1
deque.pushFront(1);
console.log(deque.popBack()); // 0
console.log(deque.popFront()); // 1
deque.pushBack(2);
console.log(deque.popFront()); // 2
console.log(deque.size()); // 0

• pushFront() : 큐의 맨 앞에 원소를 삽입하는 함수. 큐가 비어있을 때는 현재 위치에 원소를 삽입하고 front를 -1만큼 이동시킨다.
• popFront() : 큐의 맨 앞 원소를 큐에서 제거하고 반환하는 함수. 원소를 제거했을 때 front가 rear보다 크다면 큐가 빈 것이므로 front와 rear를 0으로 초기화한다.
• pushBack() : 큐의 맨 뒤에 원소를 삽입하는 함수. 큐가 비어있을 때는 현재 위치에 원소를 삽입하고 rear를 +1만큼 이동시킨다.
• popBack() : 큐의 맨 뒤 원소를 큐에서 제거하고 반환하는 함수. 원소를 제거했을 때 rear가 front보다 작다면 큐가 빈 것이므로 front와 rear를 0으로 초기화한다.
• size() : 큐에 담긴 원소의 개수(길이)를 반환하는 함수. 큐가 비어있을 때(front = 0, rear = 0)일 때는 0을 반환해야 하므로 따로 조건문을 걸어준다.