JavaScript 원형 덱 구현: 양끝 삽입·삭제와 고정 용량 버퍼

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

왜 덱이 필요한가

일반 큐는 뒤로 넣고 앞으로 꺼냅니다. 편집 기록의 최근 항목을 되돌리려면 뒤에서도 꺼낼 수 있어야 합니다. 덱(deque, double-ended queue)은 이 두 방향을 함께 지원하는 추상 자료형입니다. 여기서 원형 배열은 그 계약을 구현하는 한 방법이지, 덱 자체의 정의는 아닙니다.

JavaScript 배열의 앞에 unshift로 삽입하거나 shift로 삭제하면 인덱스를 앞으로 또는 뒤로 당기는 비용을 고려해야 합니다. 원형 덱은 값의 자리를 옮기지 않고 “논리적 첫 항목이 어디인가”만 바꿉니다. 반대로 중간 위치 삽입이나 정렬이 주작업이라면 이 구조가 특별히 유리하지 않습니다.

저장 계약: front와 length가 의미하는 것

capacity는 1 이상의 정수이며 실행 가능한 메모리 크기 안에서 정합니다. data는 고정 개수의 슬롯, front는 첫 항목의 물리 위치, length는 현재 원소 수입니다. 항상 0 ≤ length ≤ capacity, 0 ≤ front < capacity를 유지하며 논리 위치 i의 실제 위치는 (front + i) % capacity입니다.

삽입은 성공하면 true, 가득 차면 false를 반환하고 기존 값을 바꾸지 않습니다. 오래된 기록을 자동으로 버릴지는 덱을 사용하는 프로그램이 결정합니다. 이런 분리는 실수로 작업을 잃으면 안 되는 큐에도 같은 구현을 재사용하게 해 줍니다.

삭제 결과는 빈 덱이면 {done:true}, 값이 있으면 {done:false,value}입니다. undefined 자체도 저장할 수 있으므로 undefined만 반환하면 “빈 덱”과 “undefined 저장”을 구별하지 못합니다. 이 예제는 별도의 done 표시로 구별합니다. 객체를 저장하면 복사가 아니라 참조가 보관됩니다.

전체 코드와 실행

아래 전체를 deque.cjs로 저장하고 터미널에서 node ./deque.cjs를 실행합니다. Node.js CommonJS 파일 하나이며 npm 패키지나 브라우저가 필요하지 않습니다. module.exports는 테스트용이고 맨 아래 직접 실행 블록이 실제 호출과 출력을 담당합니다.

'use strict';

class CircularDeque {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new RangeError('capacity must be a positive integer');
    }
    this.data = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.length = 0;
  }

  pushFront(value) {
    if (this.length === this.capacity) return false;
    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.data[this.front] = value;
    this.length += 1;
    return true;
  }

  pushBack(value) {
    if (this.length === this.capacity) return false;
    const index = (this.front + this.length) % this.capacity;
    this.data[index] = value;
    this.length += 1;
    return true;
  }

  popFront() {
    if (this.length === 0) return { done: true };
    const value = this.data[this.front];
    this.data[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.length -= 1;
    return { done: false, value };
  }

  popBack() {
    if (this.length === 0) return { done: true };
    const index = (this.front + this.length - 1) % this.capacity;
    const value = this.data[index];
    this.data[index] = undefined;
    this.length -= 1;
    return { done: false, value };
  }

  toArray() {
    const result = [];
    for (let offset = 0; offset < this.length; offset += 1) {
      result.push(this.data[(this.front + offset) % this.capacity]);
    }
    return result;
  }
}

module.exports = { CircularDeque };

if (require.main === module) {
  const deque = new CircularDeque(3);
  deque.pushBack('A');
  deque.pushBack('B');
  const removed = deque.popFront();
  deque.pushBack('C');
  deque.pushFront('D');
  const full = deque.pushBack('E');
  console.log(JSON.stringify({ removed, full, values: deque.toArray(), front: deque.front }));
}

실행 출력

{"removed":{"done":false,"value":"A"},"full":false,"values":["D","B","C"],"front":0}

각 메서드가 불변식을 지키는 방법

pushBack은 length개 뒤의 빈 슬롯을 선택합니다. length를 먼저 늘리면 한 칸 뒤에 써 버리므로 값을 기록한 뒤 증가시킵니다. full 검사를 가장 먼저 하는 이유는 덮어쓰기를 막기 위해서입니다. 읽을 때도 물리 배열 순서가 아니라 front에서 시작하는 순서를 사용합니다.

pushFront는 첫 위치를 한 칸 뒤로 이동시킨 다음 값을 기록합니다. JavaScript의 %는 수학적 양의 모듈러와 달라 -1 % 3이 -1입니다. 따라서 front – 1에 capacity를 더해 음수를 피합니다. front가 0인 경우에도 새 위치는 capacity – 1이 됩니다.

popFront는 현재 front의 값을 먼저 저장하고 슬롯을 비운 뒤 front를 한 칸 전진시킵니다. popBack은 마지막 논리 위치 length – 1을 계산하고 front는 유지합니다. 사용한 슬롯에 undefined를 대입하면 큰 객체에 대한 불필요한 참조를 덱이 계속 붙들지 않습니다.

마지막 항목을 지운 뒤 front가 0이 아니어도 오류가 아닙니다. length가 0이면 어떤 슬롯도 활성 원소가 아니며 다음 삽입은 동일한 인덱스 공식을 따릅니다. 빈 덱을 항상 초기 위치로 되돌려야 한다는 조건은 이 계약에 없습니다.

용량 3에서의 동작 추적

배열을 실제로 순환시키는 경우도 확인해 보세요. 위 표의 빈 상태에서 X,Y를 뒤에 넣으면 슬롯 2와 0에 저장되지만 toArray()는 [X,Y]를 반환합니다. 물리 배열을 그대로 출력하는 것과 논리 덱을 출력하는 것은 다릅니다.

복잡도와 적용 한계

K는 용량, n은 현재 항목 수입니다. 위 비용은 배열 인덱스 접근을 상수 시간으로 보는 일반적인 모델이며 값 자체를 깊은 복사하지 않습니다. 고정 용량이므로 이 구현에는 자동 확장에 따른 가끔 O(n)이 되는 삽입이 없습니다. 대신 K개를 넘으면 반드시 실패합니다.

크기 상한을 모르는 프로그램은 동적 원형 배열이나 연결 덱을 고려할 수 있습니다. 메모리가 제한된 기록 버퍼라면 고정 용량과 명시적 퇴출 정책이 오히려 계약을 선명하게 합니다. 전체 기록을 매번 배열로 반환하면 덱 연산이 빨라도 출력 복사 비용이 더 커질 수 있습니다.

경계 확인과 연습

용량 1에서 삽입·실패·삭제를 반복하고, 빈 상태의 양쪽 삭제, null과 undefined 저장, 물리 끝을 여러 번 넘는 삽입을 확인하세요. 성공한 삽입만 length를 늘리고 성공한 삭제만 줄인다는 조건으로 대부분의 인덱스 오류를 찾을 수 있습니다.

함께 연습하고 확인할 자료

Design Circular Deque: 양끝 삽입·삭제 API를 직접 설계하는 외부 연습입니다. 반환 계약은 이 글과 다르므로 공식 문제의 요구를 별도로 읽으세요.

관련 개념 참고: 위 공식 문제의 API 계약을 함께 살펴보세요. 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.