덱의 정의
양쪽 끝에서 삽입과 삭제가 가능한 자료구조
삽입, 삭제, 제일 앞/뒤의 원소 확인이 모두 O(1) 시간복잡도를 가지고 있다.
제일 앞/뒤가 아닌 원소들의 확인/변경이 불가능하지만 STL Deque에서는 인덱스로 원소에 접근할 수 있다.
구현 방법
스택이나 큐처럼 배열 또는 연결 리스트로 구현할 수 있지만 배열을 이용하는 게 쉽기 때문에 배열로 구현을 했다.
- 원소를 담을 배열
- 앞쪽과 뒤쪽을 가리킬 변수 2개
초기값이 0이 아니라 설정한 배열 크기의 중간값으로 잡는다.
왜냐하면 큐에서는 배열의 앞쪽에서는 제거만 발생하고 뒤쪽에서 삽입되는 형태이기 때문에 원소들이 차지하는 공간이 오른쪽으로 이동하면서 확장되지만, 덱에서는 양쪽으로 이동하면서 확장되기 때문에 초기값을 0으로 잡거나 배열의 최대 크기로 잡으면 다른 쪽으로 확장이 불가능하다.
예를 들어, 배열에 인덱스 0, 1, 2 순서로 데이터가 삽입됬고 가장먼저 들어간 인덱스 0번에 있는 원소를 뒤에서 제거할 때 H의 위치를 한 칸 움직이고 다시 뒤쪽에서 데이터를 추가로 삽입하는 경우 공간이 없기 때문에 문제가 생김
초기값을 배열의 중간으로 둬야되고 배열의 크기는 기존에 설정한 크기의 2배로 설정해야 한다.
코드
#include <iostream>
#include <queue>
using namespace std;
const int MX = 100005;
int dat[MX*2+1];
int head = MX;
int 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];
}
head와 tail 초기값을 배열의 중간지점으로 잡고 front 쪽에서 삽입되는 방식은 초기값 이전의 공간부터 값이 들어가고 삭제되며 back 쪽에서는 초기값부터 삽입되고 빠져나오도록 설정했다.
front와 back 양쪽에서 삽입과 삭제가 일어나기 때문에 어디서부터 삽입될지의 기준을 정할 필요가 있는데 back쪽에 삽입되는 경우 초기값부터 삽입되도록 정했지만 이거는 기준을 정하기 나름이라서 반대로 바꿔도 무관하다.
STL 코드
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
deque<int> DQ;
DQ.push_front(10);
DQ.push_back(50);
DQ.push_front(24); // 24 10 50
for (auto x : DQ) {
cout << x << ' ';
}
DQ.pop_front(); // 10 50
DQ.pop_back(); // 10
DQ.push_back(72); // 10 72
DQ.push_back(12); // 10 72 12
DQ[2] = 17; // 10 72 17
DQ.insert(DQ.begin() + 1, 33); // 10 33 72 17
DQ.erase(DQ.begin() + 1); // 10 72 17
DQ.clear(); // DQ의 모든 원소제거
return 0;
}
vector랑 느낌이 비슷한데 deque의 경우는 O(1) 추가와 제거가 가능하다보니까(벡터의 경우 중간 또는 첫 번째에 데이터를 삽입하거나 데이터를 삭제하는 경우 뒤에 있는 데이터들이 한 칸씩 움직이기 때문) vector의 상위호환이 아닐까 싶은데 vector와 다르게 deque는 모든 원소들이 메모리 상에 연속해서 배치되어 있지 않는다.
상황에 따라서 앞쪽과 뒤쪽에서 추가/제거가 필요한 경우 STL deque를 사용하는게 효율적이지만 앞쪽에서 추가와 제거가 필요 없고 배열과 같은 느낌으로 쓸 때는 STL vector를 주로 사용한다.
