덱 (deque)
정의와 성질
덱의 정의
스택, 큐, 덱 모두 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려 있어서, Restricted Structure 라고 불린다. 그 중에서 덱은 Restricted Structure의 끝판왕과 같은 자료구조인데, 양쪽 끝에서 삽입과 삭제가 모두 가능하기 때문이다. 참고로 deque은 Double Ended Queue 라는 뜻을 갖고 있다.
덱의 성질
- 맨 앞/뒤에서 원소 추가: O(1)
- 맨 앞/뒤에서 원소 삭제: O(1)
- 맨 앞/뒤에 있는 원소 확인/변경: O(1)
- 맨 앞/뒤에 있지 않은 원소의 확인/변경: 원칙적으로 불가능
STL stack, queue와 달리, 독특하게도 STL deque에서는 인덱스로 모든 원소에 접근할 수 있다.
기능과 구현
덱도 배열이나 리스트로 구현할 수 있지만, 더 쉬운 배열을 이용한 구현 방법을 소개한다. head는 맨 앞에 있는 원소 위치를, tail은 맨 뒤에 있는 원소 바로 다음 위치를 가리킨다.
const int MAX = 1000005;
int data[2 * MAX + 1];
int head = MAX, tail = MAX; 위의 코드에서 head와 tail을 0으로 잡으면 안 되는 이유를 알아보자!
큐는 앞에서는 삭제, 뒤에서는 추가만 가능하므로 원소들이 점점 오른쪽으로 밀리는 구조였다.
하지만, 덱에서는 앞과 뒤 모두에서 삽입/삭제가 가능하므로 초기 인덱스를 0으로 잡은 상태에서 삭제 연산을 하면 인덱스가 마이너스 값이 되어서 오류가 발생한다.
따라서 배열의 크기를 2*MAX + 1 로 잡고, head와 tail은 그 중간 위치를 가리키게 하면 이런 문제를 방지할 수 있다.
덱도 원형으로 구현할 수 있지만, 코딩테스트에서는 배열의 크기를 충분히 크게 잡으면 되니까 선형으로 구현하는 방법만 알아보자.
#include <iostream>
using namespace std;
const int MAX = 1000005;
int data[2 * MAX + 1];
int head = MAX, tail = MAX;
void push_front(int x){
data[--head] = x;
}
void push_back(int x){
data[tail++] = x;
}
void pop_front(){
head++;
}
void pop_back(){
tail--;
}
int front(){
return data[head];
}
int back(){
return data[tail - 1];
}STL deque
#include <iosteam>
#include <deque>
using namespace std;
int main(){
deque<int> dq;
dq.push_front(10); // 10
dq.push_back(50); // 10 50
dq.push_front(24); // 24 10 50
for(auto e: dq)
cout << e << " ";
cout << endl;
cout << dq.size() << endl; // 3
if(dq.empty()) cout << "deque is empty\n";
else cout << "deque is not empty\n";
dq.pop_front(); // 10 50
dq.pop_back(); // 10
cout << dq.back() << "\n"; // 10
dq.push_back(72); // 10 72
cout << dq.front() << "\n"; // 10
dq.push_back(12); // 10 72 12
dq[2] = 17; // 10 72 17
dq.insert(dq.begin() + 1, 33); // 10 33 72 17
dq.insert(dq.begin() + 4, 60); // 10 33 72 17 60
dq.erase(dq.begin() + 3); // 10 33 72 60
cout << dq[3] << "\n"; // 60
dq.clear(); // 모든 원소 제거
}위와 같이 deque은 앞과 뒤에서 모두 삽입/삭제가 가능하며, 심지어 인덱스로 원소에 접근하여 값을 변경할 수도 있고, 특정 위치에 원소를 삽입/삭제하는 insert(), erase() 함수도 사용할 수 있다.
이처럼 STL vector에서 제공하는 기능을 STL deque에서도 모두 제공해주며, 심지어 deque는 front에서도 O(1)에 원소 삽입/삭제가 가능하니 STL deque이 vector보다 상위 호환인 것처럼 보일 수 있다. 하지만, vector는 메모리 상에 원소들이 연속해서 배치되어 있지만, deque는 그렇지 않다.
배열의 앞과 뒤 모두에서 원소의 삽입/삭제가 필요하면 당연히 deque을 사용하는 게 효율적이지만, 굳이 앞쪽에서 원소의 삽입/삭제는 필요하지 않고 배열과 같은 느낌으로 사용하고 싶을 때는 vector를 쓰면 된다.
