스택은 한쪽 끝에서만, 큐는 양쪽 끝이지만 각각 다른 작업(삽입/삭제)만 가능했다.
그렇다면 양쪽 끝에서 삽입과 삭제를 모두 자유롭게 할 수 있다면 어떨까?

 

바로 그것이 덱(Deque, Double-Ended Queue)이다.

덱

덱은 Double-Ended Queue의 약자로, 데이터의 삽입과 제거를 head와 tail 두 곳 모두에서 자유롭게 할 수 있는 자료구조이다. 스택과 큐의 기능을 모두 포함하는 더 유연한 구조라고 할 수 있다.

스택, 큐, 덱 비교

  스택 (Stack) 큐 (Queue) 덱 (Deque)
삽입 위치 한쪽 끝 뒤쪽 양쪽 끝 모두
삭제 위치 한쪽 끝 (같은 곳) 앞쪽 양쪽 끝 모두
구조 LIFO FIFO 자유로움
활용 뒤로 가기, Undo 대기열, BFS 슬라이딩 윈도우 등

 

덱의 핵심 연산

덱은 다음과 같은 기본 연산을 제공한다.

  1. addFirst(): 덱의 앞쪽(head)에 데이터 추가
  2. removeFirst(): 덱의 앞쪽(head)에서 데이터 제거
  3. addLast(): 덱의 뒤쪽(tail)에 데이터 추가
  4. removeLast(): 덱의 뒤쪽(tail)에서 데이터 제거
  5. isEmpty(): 덱이 비어있는지 확인

 

양방향 연결 리스트로 덱 구현하기

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능해야 하므로, 양방향 연결 리스트를 사용하는 것이 최적이다.
양방향 연결 리스트는 head와 tail을 모두 관리하므로, 양쪽 끝에서의 모든 작업이 O(1)의 시간복잡도를 가진다.

Deque 클래스

import { DoublyLinkedList } from "../linked_list/DoublyLinkedList.mjs";

class Deque {
  constructor() {
    this.list = new DoublyLinkedList();  // 양방향 연결 리스트 사용
  }
}

 

주요 메서드

1. addFirst() - 앞쪽에 데이터 추가

addFirst(data) {
  this.list.insertAt(0, data);  // 맨 앞(head)에 삽입
}

덱의 맨 앞에 데이터를 추가한다. 스택의 push()와 동일한 동작이다.

 

2. removeFirst() - 앞쪽에서 데이터 제거

removeFirst() {
  return this.list.deleteAt(0);  // 맨 앞(head)에서 제거
}

덱의 맨 앞에서 데이터를 제거한다. 스택의 pop()과 동일한 동작이다.

 

3. addList() - 뒤쪽에 데이터 추가

addLast(data) {
  this.list.insertLast(data);  // 맨 뒤(tail)에 삽입
}

덱의 맨 뒤에 데이터를 추가한다. 큐의 enqueue()와 동일한 동작이다.

 

4. removeLast() - 뒤쪽에서 데이터 제거

removeLast() {
  return this.list.deleteLast();  // 맨 뒤(tail)에서 제거
}

덱의 맨 뒤에서 데이터를 제거한다. 큐의 dequeue()와 동일한 동작이다.

 

5. isEmpty() - 비어있는지 확인

isEmpty() {
  return this.list.count == 0;
}

 

덱 사용 예제

예제 1: addFirst()와 removeFirst() - 스택처럼 사용

let deque = new Deque();

console.log(`isEmpty: ${deque.isEmpty()}`);  // isEmpty: true

deque.addFirst(1);  // [1]
deque.addFirst(2);  // [2, 1]
deque.addFirst(3);  // [3, 2, 1]
deque.addFirst(4);  // [4, 3, 2, 1]
deque.addFirst(5);  // [5, 4, 3, 2, 1]

deque.printAll();  // [5, 4, 3, 2, 1]
console.log(`isEmpty: ${deque.isEmpty()}`);  // isEmpty: false

deque.removeFirst();  // 5 제거
deque.printAll();     // [4, 3, 2, 1]

 

예제 2: addLast()와 removeLast() - 큐처럼 사용

deque.addLast(1);  // [1]
deque.addLast(2);  // [1, 2]
deque.addLast(3);  // [1, 2, 3]
deque.addLast(4);  // [1, 2, 3, 4]
deque.addLast(5);  // [1, 2, 3, 4, 5]

deque.printAll();  // [1, 2, 3, 4, 5]
console.log(`isEmpty: ${deque.isEmpty()}`);  // isEmpty: false

deque.removeLast();  // 5 제거
deque.printAll();    // [1, 2, 3, 4]

 

예제 3: 자유로운 양방향 조작

let deque = new Deque();

deque.addFirst(3);   // [3]
deque.addFirst(2);   // [2, 3]
deque.addLast(4);    // [2, 3, 4]
deque.addFirst(1);   // [1, 2, 3, 4]
deque.addLast(5);    // [1, 2, 3, 4, 5]

deque.printAll();    // [1, 2, 3, 4, 5]

deque.removeFirst(); // 1 제거 → [2, 3, 4, 5]
deque.removeLast();  // 5 제거 → [2, 3, 4]

 

덱의 시간복잡도

양방향 연결 리스트를 사용한 덱의 모든 기본 연산은 O(1)의 시간복잡도를 가진다.

  • addFirst(): O(1)
  • removeFirst(): O(1)
  • addLast(): O(1)
  • removeLast(): O(1)
  • isEmpty(): O(1)

 

덱의 실제 활용 사례

1. 슬라이딩 윈도우 (Sliding Window)

배열에서 고정 크기의 윈도우를 이동하며 최대값/최소값을 찾는 문제에서 덱을 사용하면 효율적으로 해결할 수 있다.

// 크기 k인 윈도우의 최대값 찾기
function slidingWindowMaximum(arr, k) {
  const deque = new Deque();
  const result = [];
  
  for (let i = 0; i < arr.length; i++) {
    // 윈도우 범위를 벗어난 인덱스 제거
    if (!deque.isEmpty() && deque.front() < i - k + 1) {
      deque.removeFirst();
    }
    
    // 현재 값보다 작은 값들을 뒤에서 제거
    while (!deque.isEmpty() && arr[deque.back()] < arr[i]) {
      deque.removeLast();
    }
    
    deque.addLast(i);
    
    // 윈도우 크기에 도달하면 최대값 저장
    if (i >= k - 1) {
      result.push(arr[deque.front()]);
    }
  }
  
  return result;
}

 

2. 팰린드롬 검사

문자열이 앞에서 읽으나 뒤에서 읽으나 같은지 확인할 때, 덱의 양쪽 끝에서 하나씩 꺼내며 비교한다.

function isPalindrome(str) {
  const deque = new Deque();
  
  // 문자를 덱에 추가
  for (let char of str) {
    deque.addLast(char);
  }
  
  // 양쪽 끝에서 비교
  while (deque.list.count > 1) {
    if (deque.removeFirst().data !== deque.removeLast().data) {
      return false;
    }
  }
  
  return true;
}

console.log(isPalindrome("racecar"));  // true
console.log(isPalindrome("hello"));    // false

 

작업 스케줄러

우선순위가 높은 작업은 앞쪽에, 일반 작업은 뒤쪽에 추가하여 유연하게 작업 순서를 조정할 수 있다.

const taskQueue = new Deque();

// 일반 작업은 뒤에 추가
taskQueue.addLast("일반 작업 1");
taskQueue.addLast("일반 작업 2");

// 긴급 작업은 앞에 추가
taskQueue.addFirst("긴급 작업!");

// 처리 순서: 긴급 작업 → 일반 작업 1 → 일반 작업 2

 

4. 브라우저의 앞으로/뒤로 가기

현재 페이지를 기준으로 이전 페이지는 앞쪽에, 다음 페이지는 뒤쪽에 저장하여 양방향 탐색을 구현한다.

 

덱 vs 스택/큐

덱은 스택과 큐의 모든 기능을 포함한다.

  • 덱을 스택으로 사용: addFirst()와 removeFirst()만 사용
  • 덱을 큐로 사용: addLast()와 removeFirst()만 사용

 

그렇다면 항상 덱을 사용하면 되지 않을까? 꼭 그렇지는 않다. 

 

스택이나 큐만 필요한 상황에서는 해당 자료구조를 사용하는 것이 의도를 명확히 드러내고, 실수로 잘못된 연산을 사용하는 것을 방지할 수 있다. 

 

덱은 정말로 양방향 접근이 필요할 때 사용하는 것이 좋다. 덱은 스택과 큐의 장점을 모두 가진 강력하고 유연한 자료구조이다. 양쪽 끝에서 자유롭게 삽입과 삭제를 할 수 있어, 슬라이딩 윈도우나 팰린드롬 검사와 같은 특수한 문제를 효율적으로 해결할 수 있다.

'CS > 자료구조' 카테고리의 다른 글

셋 (Set)  (0) 2025.11.17
해시 테이블 (Hash Table)  (0) 2025.11.17
큐 (Queue)  (0) 2025.11.13
스택 (Stack)  (0) 2025.11.13
연결리스트 (Linked List)  (0) 2025.11.13

티스토리툴바