[DS] 5. 데크

데크(Deque)?

std::deque<int> deq;

데이터의 입출력을 앞/뒤 모두에서 가능한 자료구조. (Double-Ended Queue)

덱이라고도 불린다. 여태 디큐(De-Queue)라고 읽는게 맞는 줄 알았다;;

추상 자료형

데이터 : 맨 앞/뒤 데이터들에 대한 접근이 가능한 요소들의 모음.

연산 :

함수	설명
addFront(x)	맨 앞에 데이터 x를 삽입한다.
addRear(x)	맨 뒤에 데이터 x를 삽입한다.
delFront()	맨 앞 요소를 삭제+반환. (데크가 비어있지 않으면)
delRear()	맨 뒤 요소를 삭제+반환. (데크가 비어있지 않으면)
getFront()	맨 앞 요소를 반환. (데크가 비어있지 않으면)
getRear()	맨 뒤 요소를 반환. (데크가 비어있지 않으면)
isEmpty()	데크가 비어있다면 true, 아니라면 false 반환.
isFull()	데크가 가득 찼으면 true, 아니라면 false 반환.
display()	모든 데이터들을 출력한다.

사용법(std::deque)

메서드

함수	설명
push_front(x)	맨 앞에 데이터 x를 삽입한다.
push_back(x)	맨 뒤에 데이터 x를 삽입한다.
emplace_front(x)	맨 앞에 데이터 x를 삽입한다. 단, 내부에서 객체를 생성하여 할당한다.
emplace_back(x)	맨 뒤에 데이터 x를 삽입한다. 단, 내부에서 객체를 생성하여 할당한다.
pop_front()	맨 앞의 데이터를 삭제한다. 반환 타입 void. (데크가 비어있지 않으면)
pop_back()	맨 뒤의 요소를 제거한다. 반환 타입 void. (데크가 비어있지 않으면)
front()	맨 앞의 요소를 반환. (데크가 비어있지 않으면)
back()	맨 뒤의 요소를 반환. (데크가 비어있지 않으면)
at(i)	i번째 요소를 반환한다. (범위 검사 있음)
operator[](i)	i번째 요소를 반환한다. (범위 검사 없음)
empty()	데크가 비어있다면 true, 아니라면 false 반환.
size()	데이터들의 갯수를 반환한다.
clear()	저장된 모든 데이터를 제거한다.
swap(deq)	다른 데크 deq를 받아, 서로가 가리키는 주소 정보(포인터)를 서로 맞바꾼다.

iterator(반복자) 관련 메서드

함수	설명
insert(pos, x)	지정한 iterator(pos) 위치 앞에 데이터 x를 삽입.
erase(pos) / erase(first, last)	지정한 iterator(pos) 위치의 요소 or 범위([))를 삭제한다.
resize(n) / resize(n, i)	데크의 크기를 n개로 변경하고 i로 초기화한다.
assign(n, x)	데크의 내용을 x값 n개로 완전히 덮어쓴다. 즉 assign(3, 5) 는 3 데이터 5개 들어간 데크로 바뀐다.
begin() / end()	데크의 첫 번째 요소와 마지막 다음 위치를 가리키는 iterator(반복자)를 반환한다.
rbegin() / rend()	역방향 순회를 위한 reverse_iterator(역방향 반복자)를 반환한다.

[..] [-1] [0] [1] [2] [3] [4] [..] 에서 배경색 범위가 데크라 가정, 아래와 같은 꼴이 된다. (이해를 돕기 위한 예시)

• begin() == std::deque<T>::iterator[0]
• end() == std::deque<T>::iterator[4]
• rbegin() == std::deque<T>::reverse_iterator[3]
• rend() == std::deque<T>::reverse_iterator[-1]

참고로, reverse_iterator는 ++시 앞으로 1칸 이동한다. 반대로 이동하는 셈.

예제 코드

Deque

#include <iostream>
#include <deque>

int main() {
  std::deque<int> deq;

  deq.push_back(10);          // 뒤에 삽입
  deq.push_back(20);

  deq.push_front(5);          // 앞에 삽입
  deq.push_front(1);

  std::cout << "Data : ";
  for (auto data : deq)       // 1, 5, 10, 20
    std::cout << data << " ";
  std::cout << std::endl;
  
  deq.pop_front();            // 앞(1) 제거
  deq.pop_back();             // 뒤(20) 제거

  std::cout << "Data: ";
  for (auto data : deq)       // 5, 10
    std::cout << data << " ";
  std::cout << std::endl;
}

Data : 1, 5, 10, 20
Data : 5, 10

구현

원형 데크 예제 코드

이전의 원형 큐를 상속받아 만든 데크 예제이다.

큐는 맨 뒤에 넣기, 맨 앞을 가져오기밖에 안되므로 맨 앞에 넣기, 맨 뒤를 가져오기를 추가로 구현한 모습이다.

// 원형 큐를 상속받은 원형 데크 클래스
// 기존 원형 큐는 https://sdtr.dev/posts/2026-08-17_210938/ 참고.
template <typename T>
class CircularDeque : public CircularQueue<T> {
public:
  CircularDeque() : CircularQueue<T>() {}

  // 기존 원형 큐 기반
  void addRear(T val) { this->enqueue(val); }
  T deleteFront()     { return this->dequeue(); }
  T getFront() const  { return this->peek(); }
  
  void addFront(T val)
  { // (가득 차지 않았다면) 데이터를 맨 앞에 넣는다.
    // front에 데이터를 넣고, front를 앞으로 1칸 당긴다.
    if (this->isFull()) { std::cout << "Deque is full" << std::endl; return; }
    this->data[this->front] = val;
    this->front = (this->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
  }

  T deleteRear()
  { // (비어있지 않다면) 맨 뒤의 데이터를 삭제+반환한다. 정확히는 삭제가 아닌 없는취급. 
    // rear 위치의 데이터를 꺼내고, rear를 뒤로 1칸 민다.
    if (this->isEmpty()) { std::cout << "Deque is empty" << std::endl; return T(); }
    T ret = this->data[this->rear];
    this->rear = (this->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return ret;
  }

  T getRear()
  { // (비어있지 않다면) 맨 뒤의 데이터를 반환한다.
    if (this->isEmpty()) { std::cout << "Deque is empty" << std::endl; return T(); }
    return this->data[this->rear];
  }
};

int main()
{
  CircularDeque<int> dq;

  dq.addRear(10);
  dq.addRear(20);
  dq.addFront(5);
  
  std::cout << dq.deleteFront() << " "; 
  
  dq.addRear(30);
  dq.addRear(40);
  
  std::cout << dq.deleteFront() << " ";
  
  dq.addRear(50);
  
  std::cout << dq.deleteRear() << " ";
  
  dq.addFront(15);
  
  std::cout << dq.deleteFront() << " ";
  std::cout << dq.deleteRear() << " ";
  std::cout << dq.deleteFront() << " ";
  std::cout << dq.deleteRear() << " ";
}

5 10 50 15 40 20 30

Circular Deque

데크 예제 코드 (이중 연결 리스트 기반)

이중 연결 리스트의 선행학습 이후 보기를 권장한다.

앞에서는 크기가 고정된 배열을 사용했지만, 해당 코드는 이중 연결 리스트를 통해 크기 제한 없이 이용 가능하다. 대신 노드마다 기준점 포인터를 가지므로 약간의 메모리 오버헤드가 있다.

이중 연결 리스트 구현

#include <iostream>

#pragma region 이중 연결 리스트 구현
// 이중 연결 리스트 - 노드 구조체
template <typename T>
struct Node
{
  Node* prev;    // 이전 노드의 주소값
  Node* next;    // 다음 노드의 주소값
  T data;        // 데이터

public:
  Node(T val = T(), Node<T>* p = nullptr, Node<T>* n = nullptr) 
    : data(val), prev(p), next(n) {}
  Node* getPrev()        { return prev; }
  Node* getNext()        { return next; }
  void setPrev(Node* p)  { prev = p; }
  void setNext(Node* n)  { next = n; }
  void display()         { std::cout << " <" << data << ">"; }
  bool hasData(T val)    { return data == val; } 
    
  void insertNext(Node* newNode)
  { // 자신의 다음에 새로운 노드 추가.
    if (newNode != nullptr) {
      newNode->prev = this;
      newNode->next = this->next;
      if (this->next != nullptr) this->next->prev = newNode;
      this->next = newNode;
    }
  }

  Node* remove()
  { // 현재 노드를 연결 리스트에서 제거+반환.
    if (this->prev != nullptr) this->prev->next = this->next;
    if (this->next != nullptr) this->next->prev = this->prev;
    return this;
  }
};

// 이중 연결 리스트 - 기본 클래스
template <typename T>
class DblLinkedList {
protected:
  Node<T> org; // 더미 헤드 노드
  int count;   // 현재 데이터 개수

public:
  DblLinkedList() : org(), count(0) {
    org.next = nullptr;
    org.prev = &org;                              // org.prev가 마지막 노드를 가리키게
  }
  virtual ~DblLinkedList() { clear(); }           // 소멸 시 모든 노드 메모리 해제

  Node<T>* getHead() { return org.next; }         // 맨 앞 노드 반환
  Node<T>* getTail() { return (org.prev == &org) ? nullptr : org.prev; } // 맨 뒤 노드 반환
  bool isEmpty()     { return getHead() == nullptr; }
  int size()         { return count; }
  void clear()       { while (!isEmpty()) delete remove(0); }

  Node<T>* getEntry(int pos)
  { // pos 번째 노드를 반환.
    Node<T>* n = &org;
    for (int i = -1; i < pos; ++i) {
      if (n == nullptr) break;
      n = n->next;
    }
    return n;
  }

  void insert(int pos, Node<T>* n)
  { // pos 위치에 새 노드 삽입.
    Node<T>* prevNode = getEntry(pos - 1);
    if (prevNode != nullptr && n != nullptr) {
      prevNode->insertNext(n);
      if (n->next == nullptr) org.prev = n; // 맨 끝에 추가된 경우 tail 포인터 갱신
      count++;
    }
  }

  Node<T>* remove(int pos)
  { // pos 위치의 노드 삭제+반환.
    Node<T>* n = getEntry(pos);
    if (n != nullptr && n != &org) {
      if (n == org.prev) org.prev = n->prev; // 마지막 노드 삭제 시 tail 포인터 갱신
      count--;
      return n->remove();
    }
    return nullptr;
  }

  Node* find(T val)
  { // 값이 val인 노드 탐색, 찾을 시 반환
    for (auto p = getHead(); p != nullptr; p = p->getNext())
      if (p->hasData(val)) return p;
    return nullptr;
  }

  void replace(int pos, Node* n)
  { // pos 위치의 노드 교체.
    Node* prev = getEntry(pos - 1);
    if (prev != nullptr)
    {
      delete prev->getNext()->remove();
      prev->insertNext(n);
    }
  }
  
  virtual void display()
  { // 모든 데이터를 출력한다.
    for (Node<T>* p = getHead(); p != nullptr; p = p->next)
      std::cout << "<" << p->data << "> ";
    std::cout << std::endl;
  }
};
#pragma endregion

// 이중 연결 리스트를 상속받은 데크 클래스
template <typename T>
class LinkedDeque : public DblLinkedList<T> {
public:
  void addFront(Node<T>* n)
  { // 맨 앞에 데이터 삽입
    if (n == nullptr) return;      // 예외처리
    this->org.insertNext(n);       // 맨 앞 기준 노드의 다음 칸에 삽입
    if (n->next == nullptr) this->org.prev = n; // 다음 노드 지정
    this->count++;                 // 데이터 갯수 갱신
  }

  void addRear(Node<T>* n)
  { // 맨 뒤에 데이터 삽입
    if (n == nullptr) return;      // 예외처리
    this->org.prev->insertNext(n); // 맨 뒤 기준 
    this->org.prev = n;
    this->count++;
  }

  Node<T>* deleteFront()
  { // 맨 앞 노드 삭제+반환
    if (this->isEmpty()) return nullptr;
    Node<T>* frontNode = this->org.next;
    if (frontNode == this->org.prev) this->org.prev = &this->org;
    this->count--;
    return frontNode->remove();
  }

  Node<T>* deleteRear()
  { // 맨 뒤 노드 삭제+반환
    if (this->isEmpty()) return nullptr;
    Node<T>* rearNode = this->org.prev;
    this->org.prev = rearNode->prev;
    this->count--;
    return rearNode->remove();
  }
  
  Node<T>* getFront() { return this->getHead(); }
  Node<T>* getRear()  { return this->getTail(); }

  void display() override {
    std::cout << "Data : ";
    for (auto p = this->getHead(); p != nullptr; p = p->next) {
      std::cout << "<" << p->data << "> ";
    }
    std::cout << std::endl;
  }
};

int main() {
  LinkedDeque<int> deq;

  for (int i = 1; i < 10; ++i) {
    if (i % 2) deq.addFront(new Node<int>(i));
    else deq.addRear(new Node<int>(i));
  }
  deq.display();

  delete deq.deleteFront();
  delete deq.deleteRear();
  delete deq.deleteFront();

  deq.display();

  return 0;
}

Data : <9> <7> <5> <3> <1> <2> <4> <6> <8> 
Data : <5> <3> <1> <2> <4> <6>

Doubly-Linked Deque

특징

stack, queue와 마찬가지로 앞/뒤의 삽입/반출 시간복잡도가 $O(1)$로 상당히 빠르다. 당연하게도, 삽입/반출의 기준점을 항상 알고있기 때문이다.

std::stack과 std::queue가 std::deque 기반으로 작동한다.

std::deque의 경우, 배열과 연결 리스트의 장점을 동시에 활용한다. 정확히는, 데이터를 일정 갯수만큼 배열로 묶어서 청크 형태로 관리한다. 이렇게 청크화한 데이터 블록들을 여러 개 갖되, 중앙의 인덱스 배열로 각 청크의 순서와 주소를 관리한다. 이를 통해 index를 통한 임의 접근이 빠르면서도, 양 끝에서의 삽입/반출 또한 빠르다는 특징을 가진다.

이로 인해 (중앙 index 관리로 인해) 약간의 메모리 오버헤드를 가지나, 각 청크 내에서는 내부 데이터가 연속된 메모리에 위치하게 되므로 공간 지역성에 따른 높은 캐시 효율성을 얻는다는 이점이 있다. CPU가 작업을 하기 위해서는 자료들을 CPU 캐시에 올려야 하는데, 인접 정보가 필요할 시 쓰던 걸 다시 내리고 필요한 메모리를 다시 올리는 과정이 생략되기 때문이다. (이를 캐시 히트라 한다. 반대는 캐시 미스.) 대부분의 경우 이미 들고 있던 것에 필요한 정보가 있을테니. 하드웨어 간에 데이터를 오르내리는 과정은 엄청난 오버헤드인데, 이를 대폭 줄일 수 있는 셈이다.

그림으로 나타낸다면 아래와 유사하다.

사용례

• undo 및 redo 동시 구현
• 브라우저 뒤로가기 / 앞으로가기
• 이외 stack, queue가 사용되는 곳이면 모두 사용 가능하다.