[바킹독 실전 알고리즘 0x07] 덱

정의와 성질

덱은 양 쪽 끝에서 삽입과 삭제가 모두 가능하다. 자료구조에서의 덱은 deque(double ended queue)이다. (deck아님)

• 원소의 삽입과 삭제를 O(1)의 시간복잡도를 가지고 구현할 수 있다.
• 가장 앞과 가장 뒤의 원소를 확인하는 데 O(1)의 시간복잡도가 소요된다.
• 가장 앞과 가장 뒤가 아닌 원소들의 확인/변경은 원칙적으로 불가능하다. 하지만 독특하게도 스택, 큐와 달리 STL deque에서는 인덱스로 원소에 접근할 수 있다.

 

기능과 구현

스택, 큐와 동일하게 배열과 연결리스트를 가지고 구현할 수 있다. 하지만 배열로 구현하는 것이 더 쉽기 때문에 이번 게시글에서는 배열로 구현하는 방법을 소개한다. 

const int MAX = 1000000;
int data[2*MAX+1];
int head = MAX, tail = MAX;

큐와 달리 덱에서는 head와 tail의 초기값이 MAX이다. 여기서 MAX는 배열의 중간 인덱스 값을 가리킨다. 덱은 양방향으로 늘어나는 성질을 가졌기 때문에, 한쪽 끝을 시작점으로 둔다면 반대쪽으로는 확장이 어려워진다. 따라서 배열의 중간 인덱스 값을 시작점으로 설정하고, 해당 위치에서부터 양옆으로 확장해야 한다. 

 

배열의 중간 인덱스 값이 MAX이므로 배열의 크기는 2*MAX+1일 것이다.

 

덱도 원형으로 구현할 수 있지만, 코딩테스트에서는 그냥 배열의 크기를 충분히 크게 만드는 것이 더 효율적이다.

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

const int MAX  = 1000000;
int data[2*MAX+1];
int head = MAX, tail = MAX;

void push_front(int x){
    head -= 1; //head값을 하나 줄이고(현재 head에는 가장 앞 원소가 저장되어 있으므로)
	data[head] = x; //head의 위치에 새 원소 삽입
}

void push_back(int x){
	data[tail] = x; //현재 tail의 위치에 새 원소 삽입
    tail += 1; //tail을 1 증가
}

void pop_front(){
	head++;
}

void pop_back(){
	tail--;
}

int front(){
	return data[head]; //현재 원소들 중 가장 앞에 오는 것의 인덱스는 head.
}

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

void test(){

}

int main(void){
	test();
}

 

STL deque

STL deque은 독특하게도 double ended queue라는 느낌보다는 vector랑 비슷하다. vector의 기능을 모두 지원할 뿐만 아니라 front에도 O(1)에 제거와 추가가 가능하다. 하지만 deque은 vector와 달리 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않는다. 

 

앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을 사용하는 것이 효율적이지만, 굳이 앞쪽에서의 추가와 제거가 필요하지 않고, 배열과 같은 느낌으로 쓰고 싶을 땐 STL deque 대신 STL vector를 쓰면 된다. 

 

레퍼런스: https://cplusplus.com/reference/deque/

https://cplusplus.com/reference/deque/