덱(deque)
: 양 쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 (double ended queue)
1. 덱의 성질
- 원소의 추가 O(1)
- 원소의 제거 O(1)
- 제일 앞/뒤 원소 확인 O(1)
- 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 => 스택, 큐와 다르게 STL deque에서는 인덱스로 원소에 접근할 수 있음.
2. 구현
배열과 연결리스트 모두로 구현 가능하지만 배열로 구현함.
덱의 push_front, push_back, pop_front, pop_back, front와 back 연산을 구현 함.
const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;
양쪽으로 확장을 해야하므로 시작 지점을 배열의 중간으로 잡는다.
큐와 마찬가지로 head가 첫번째 원소를 가리키고, tail이 마지막 원소 하나 뒤를 가리킨다.
push_front: head를 감소시키고, 해당 자리에 원소를 추가한다.
push_back: tail자리에 원소를 추가하고, tail을 증가시킨다.
pop_front: head를 1 증가시킨다.
pop_back: tail을 1 감소시킨다.
front: head의 원소를 반환한다
back: tail-1의 원소를 반환한다.
#include <iostream>
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];
}3. STL deque
위의 구현의 연산 이외에 insert, erase와 인덱스로 원소 접근 가능한 기능을 제공한다.
STL vector vs STL deque
deque은 front에 O(1)에 추가/제거가 가능하다. 따라서 앞쪽 뒤쪽 모두 추가와 제거가 필요하면 STL deque를 사용하고, 앞쪽 추가/제거가 필요없고 배열과 같은 느낌으로 사용하려면 STL vector를 사용한다.
연산측면에서는 deque이 vector를 포함한다.
그러나 deque은 원소들이 메모리상에 연속하게 배치하지 않는다.
4. 연습문제
https://www.acmicpc.net/problem/10866
i) STL deque을 이용하여 풀이
#include <iostream>
#include <deque>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
deque<int> d;
int n;
cin >> n;
while(n--) {
string op;
cin >> op;
if(op == "push_front") {
int a;
cin >> a;
d.push_front(a);
}
else if(op =="push_back") {
int a;
cin >> a;
d.push_back(a);
}
else if(op == "pop_front") {
if(d.empty()) cout << "-1" <<'\n';
else {
cout << d.front() << '\n';
d.pop_front();
}
}
else if(op == "pop_back") {
if(d.empty()) cout << "-1" << '\n';
else {
cout << d.back() << '\n';
d.pop_back();
}
}
else if(op == "size") {
cout << d.size() << '\n';
}
else if(op == "empty") {
cout << int(d.empty()) << '\n';
}
else if(op == "front") {
if(d.empty()) cout << "-1" << '\n';
else {
cout << d.front() << '\n';
}
}
else {
if(d.empty()) cout << "-1" << '\n';
else {
cout << d.back() << '\n';
}
}
}
}ii) 배열로 deque을 구현하여 풀이
#include <iostream>
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];
}
int size() {
return tail-head;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while(n--) {
string op;
cin >> op;
if(op == "push_front") {
int a;
cin >> a;
push_front(a);
}
else if(op =="push_back") {
int a;
cin >> a;
push_back(a);
}
else if(op == "pop_front") {
if(head == tail) cout << "-1" <<'\n';
else {
cout << front() << '\n';
pop_front();
}
}
else if(op == "pop_back") {
if(head == tail) cout << "-1" << '\n';
else {
cout << back() << '\n';
pop_back();
}
}
else if(op == "size") {
cout << size() << '\n';
}
else if(op == "empty") {
cout << int(head == tail) << '\n';
}
else if(op == "front") {
if(head == tail) cout << "-1" << '\n';
else {
cout << front() << '\n';
}
}
else {
if(head == tail) cout << "-1" << '\n';
else {
cout << back() << '\n';
}
}
}
}큐, 스택과 마찬가지로 pop_front, pop_back, front, back 연산시 덱이 비어있는지 확인 해줘야 한다.
큐와 마찬가지로 head == tail이면 덱이 비어있고, 사이즈는 tail-head이다.
