Deque (덱)

Deque 란?

 

Restricted Structure의 끝판왕 느낌의 자료구조
양쪽 끝에서 삽입과 삭제가 전부 가능하다.
Stack과 Queue를 Deque의 특별한 예시라고 생각해도 무방하다.

Peek front and back

Enqueue & Dequeue

Deque의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제알 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 (STL deque에서는 index로 접근 가능)

 

Deque 구현 및 기능

배열 또는 연결 리스트로 Deque를 구현할 수 있습니다.
배열을 통한 구현은 간단하며, 시작 지점을 배열의 중간으로 두어 양쪽으로 확장할 수 있습니다.
Deque의 크기는 2 * MX + 1로 설정하고, 필요한 변수로는 큰 배열, 앞쪽과 뒤쪽을 가리키는 변수가 필요합니다.

 

Deque C++ 구현

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

void push_front(int x){
  dat[--head] = x;
}

void push_back(int x){
  dat[tail++] = x;
}

void pop_front(){
  head++;
}

void pop_back(){
  tail--;
}

int front(){
  return dat[head];
}

int back(){
  return dat[tail-1];
}

void test(){
  push_back(30); // 30
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 30
  push_front(25); // 25 30
  push_back(12); // 25 30 12
  cout << back() << '\n'; // 12
  push_back(62); // 25 30 12 62
  pop_front(); // 30 12 62
  cout << front() << '\n'; // 30
  pop_front(); // 12 62
  cout << back() << '\n'; // 62
}

int main(void){
  test();
}

• push_front(x): Deque의 앞에 원소 x를 추가합니다.
• push_back(x): Deque의 뒤에 원소 x를 추가합니다.
• pop_front(): Deque의 앞에서 원소를 제거합니다.
• pop_back(): Deque의 뒤에서 원소를 제거합니다.
• front(): Deque의 앞에 있는 원소를 반환합니다.
• back(): Deque의 뒤에 있는 원소를 반환합니다.

https://github.com/devjun63/basic-algo/commit/6a84f7d455f440553033c5787871054ab3866685

 

 

바킹독님 STL Deque 예제

STL deque는 pop_front, push_front, pop_back, push_back 함수 외에도 insert, erase, index로 원소 접근 가능
이런 점에서 STL vector와 비슷, 혹은 상위호환이라 느낄 수 있지만
vector와 다르게 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다.

정리