Double-ended queue

Deque

class Deque {
    constructor() {
        this.buf = [,]      // 초기 버퍼
        this.front = 0      // 앞쪽 포인터
        this.back = 0       // 뒤쪽 포인터
    }
}

양쪽 끝에서 삽입과 삭제가 가능하도록 하며 스택과 큐의 기능을 포함함

// 뒤쪽에 추가 
push(value) {
    if (back === front) this.double() // 공간이 부족하면 크기 2배로
    this.buf[this.back++] = value    // 값 추가하고 포인터 이동
}

// 앞쪽에 추가
unshift(value) {
    if (front === back) this.double() // 공간 부족 체크
    if (--this.front < 0) this.front += this.buf.length // 앞쪽에 추가
    this.buf[this.front] = value
}

// 뒤쪽에서 제거 
pop() {
    if (--this.back < 0) this.back += this.buf.length
    return this.buf[this.back]
}

// 앞쪽에서 제거 
shift() {
    const value = this.buf[this.front++]
    if (this.front === this.buf.length) this.front = 0
    return value
}

• 초기 상태가 빈 배열 일때 front(f)와 back(b) 포인터가 모두 0을 가르킴
• push(1)을 하였을 때 back 포인터가 가르키는 위치에 1을 넣고 back 포인터를 오른쪽으로 한칸 이동 시킴
• push(2)를 하면 back 포인터가 가르키는 위치에 2를 넣고 back 포인터를 다시 한 칸 오른쪽으로 이동시킴
• unshift(0)는 앞쪽에 데이터를 추가하고 front 포인터를 왼쪽으로 한칸 이동시킨 후 0을 넣음
• pop()은 back 포인터의 바로 앞 위치에 있는 값을 제거하고 back 포인터를 왼쪽으로 한칸 이동시킴
  
  
  

double() {
    const length = this.buf.length << 1  // 현재 버퍼 크기를 2배로
    
    // 데이터가 버퍼의 끝과 시작에 걸쳐있는 경우
    if (this.back < this.front) {
        const buf = this.buf.slice(this.front)  // front부터 끝까지 자르기
        for (let i = 0; i < this.back; ++i) {
            buf.push(this.buf[i])  // 0부터 back까지 뒤에 붙이기
        }
        this.buf = buf  // 새로운 버퍼로 교체
    }
    
    this.buf.length = length  // 버퍼 크기 2배로 확장
    this.front = 0  // front 포인터 초기화
    this.back = (length >> 1) - 1  // back 포인터 재설정
}

• 현재 버퍼 크기를 2배로 늘림
• 데이터가 버퍼의 끝과 싲가에 걸쳐있는 경우 front부터 끝까지 자른 후 0부터 back까지 뒤에 붙임
• 새로운 버퍼로 교체

1. 일반 배열의 경우

const arr = [1, 2, 3, 4];
arr.unshift(0);  
// [0, 1, 2, 3, 4] 

• 앞에 추가시 모든 요소를 한 칸씩 뒤로 밀어야 하기 때문에 느림

2. Deque

const deque = new Deque();
deque.unshift(0);  // 포인터만 이동 (빠름)
deque.shift();     // 포인터만 이동 (빠름)

• 포인터만 이동해서 빠름