덱에 대해 알아보자.

덱 (Deque, Double-Ended Queue)

덱은 앞(front)과 뒤(rear) 양쪽에서 모두 삽입과 삭제가 가능한 큐 자료구조입니다.

덱의 추상 자료형 ADT

pushFront(x) : 맨 앞에 새로운 요소 삽입
pushBack(x) : 맨 마지막에 새로운 요소 삽입
popFront() : 맨 앞 요소 추출하고 반환
popBack() : 맨 마지막 요소 추출하고 반환
peekFront() : 맨 앞 요소 조회
peekBack() : 맨 마지막 요소 조회
isEmpty() : 비어있는지 확인

size() : 요소 갯수 반환

구현 코드

시간복잡도를 O(1)로 줄이기위해서 front, rear index를 사용합니다.

  
class Deque {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }

  pushFront(value) {
    this.front--;
    this.items[this.front] = value;
  }

  pushBack(value) {
    this.items[this.rear] = value;
    this.rear++;
  }

  popFront() {
    if (this.isEmpty()) {
      throw new Error("Deque is empty");
    }

    const value = this.items[this.front];
    delete this.items[this.front];
    this.front++;

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    }

    return value;
  }

  popBack() {
    if (this.isEmpty()) {
      throw new Error("Deque is empty");
    }

    this.rear--;

    const value = this.items[this.rear];
    delete this.items[this.rear];

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    }

    return value;
  }

  peekFront() {
    if (this.isEmpty()) {
      throw new Error("Deque is empty");
    }

    return this.items[this.front];
  }

  peekBack() {
    if (this.isEmpty()) {
      throw new Error("Deque is empty");
    }

    return this.items[this.rear - 1];
  }

  size() {
    return this.rear - this.front;
  }

  isEmpty() {
    return this.front === this.rear;
  }
}

pushFront

맨 앞에 새로운 요소를 추가하는 것으로 front 값을 감소시킨 후 해당 위치에 요소를 추가합니다.

  
deque.pushFront(1);
deque.pushFront(2);
deque.pushFront(3);

console.log(deque); // { items: { '0': 1, '1': 2, '2': 3 }, front: 0, rear: 3 }

pushBack

맨 마지막에 새로운 요소를 추가하는 것으로 rear index 위치에 요소를 추가한 후 rear 값을 증가합니다.

rear 값은 다음에 삽입할 위치를 가리키는 포인터(Exclusive End)

  
deque.pushBack(1);
deque.pushBack(2);
deque.pushBack(3);

console.log(deque); // { items: { '0': 1, '1': 2, '2': 3 }, front: 0, rear: 3 }

popFront

맨 앞 요소를 추출하는 것으로 front index 위치에 요소를 추출한 후 front 값을 증가시킵니다.

추출한 후 덱이 비어있다면 front, rear 값을 0으로 초기화

  
deque.pushFront(1);
deque.pushFront(2);
deque.pushFront(3);

console.log(deque); // { items: { '0': 1, '1': 2, '2': 3 }, front: 0, rear: 3 }

deque.popFront(); // 3 (front : -2, rear : 0)
deque.popFront(); // 2 (front : -1, rear : 0)

console.log(deque); // { items: { '-1': 1 }, front: -1, rear: 0 }

popBack

맨 마지막 요소를 추출하는 것으로 rear 값을 감소시킨 후 rear index 위치에 요소를 추출합니다.

추출한 후 덱이 비어있다면 front, rear 값을 0으로 초기화

  
deque.pushFront(1);
deque.pushFront(2);
deque.pushFront(3);

console.log(deque); // { items: { '0': 1, '1': 2, '2': 3 }, front: 0, rear: 3 }

deque.popBack(); // 1 (front : -3, rear : -1)
deque.popBack(); // 2 (front : -3, rear : -2)

console.log(deque); // { items: { '-3': 3 }, front : -3, rear : -2 }

peekFront

맨 앞 요소를 확인합니다.

  
deque.pushFront(1);
deque.pushFront(2);
deque.pushFront(3);

console.log(deque.peekFront()); // 3

peekBack

맨 마지막 요소를 확인합니다.

  
deque.pushFront(1);
deque.pushFront(2);
deque.pushFront(3);

console.log(deque.peekBack()); // 1

isEmpty

큐 안에 요소가 있는 지 확인합니다.

front === rear

  
deque.isEmpty(); // true

deque.pushFront(1);

deque.isEmpty(); // false

size

덱 안에 있는 요소들의 갯수를 반환합니다.

rear - front

  
deque.pushFront(1);
deque.pushFront(2);
deque.pushFront(3);

deque.size(); // 3

덱 Deque