0x07 덱
0x00 정의와 성질
정의
Deque ( Double Ended Queue ) 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 Restricted Structure ( 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한 )
성질
원소의 추가 / 제거 O(1) 제일 앞 / 뒤의 원소 확인 O(1) 제일 앞 / 뒤 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능 → 하지만 STL deque에서는 인덱스로 원소에 접근할 수 있다.
0x01 기능과 구현
덱도 원형으로 구현할 수 있지만, 코딩테스트에서는 그냥 배열을 충분히 크게 잡으면 된다.
구현
Push_front 함수
void push_front(int x){
dat[--head] = x;
}Push_back 함수
void push_back(int x){
dat[tail++] = x;
}Pop_front 함수
void pop_front(){
head++;
}Pop_back 함수
void pop_back(){
tail--;
}Front 함수
int front(){
return dat[head];
}Back 함수
int back(){
return dat[tail-1];
}0x02 STL deque
#include <bits/stdc++.h>
using namespace std;
int main(void){
deque<int> DQ;
DQ.push_front(10); // 10
DQ.push_back(50); // 10 50
DQ.push_front(24); // 24 10 50
for(auto x : DQ)cout<<x;
cout << DQ.size() << '\n'; // 3
if(DQ.empty()) cout << "DQ is empty\n";
else cout << "DQ is not empty\n"; // DQ is not empty
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
for(auto x : DQ) cout << x << ' ';
cout << '\n';
DQ.erase(DQ.begin()+3); // 10 33 72 60
cout << DQ[3] << '\n'; // 60
DQ.clear(); // DQ의 모든 원소 제거
}→ STL deque은 vector랑 비슷한데 front에서도 O(1)에 추가와 제거가 가능한 느낌이 강하다.
insert, erase, 인덱스로 원소에 접근할 수도 있다.
하지만 vector와 달리 deque은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다.
앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을, 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL deque말고 STL vector를 쓰면 된다.
0x03 연습문제
BOJ 10866 : 덱
// STL deque
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
deque<int> D;
cin >> n;
while(n--) {
string s;
cin >> s;
if(s == "push_front") {
int buffer;
cin >> buffer;
D.push_front(buffer);
}
else if(s == "push_back") {
int buffer;
cin >> buffer;
D.push_back(buffer);
}
else if(s == "pop_front") {
if(D.empty()) cout << -1 << "\n";
else {
cout << D.front() << "\n";
D.pop_front();
}
}
else if(s= "pop_back") {
if(D.empty()) cout << -1 << "\n";
else {
cout << D.back() << "\n";
D.pop_back();
}
}
else if(s= "size") cout << D.size() << "\n";
else if(s= "empty") cout << D.empty() << "\n";
else if(s= "front") {
if(D.empty()) cout << -1 << "\n";
else cout << D.front() << "\n";
}
else {
if(D.empty()) cout << -1 << "\n";
else cout << D.back() << "\n";
}
}
}// Array deque
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while(n--) {
string s;
cin >> s;
if(s == "push_front") {
int buffer;
cin >> buffer;
push_front(buffer);
}
else if(s == "push_back") {
int buffer;
cin >> buffer;
push_back(buffer);
}
else if(s == "pop_front") {
if(head == tail) cout << -1 << "\n";
else {
cout << front() << "\n";
pop_front();
}
}
else if(s= "pop_back") {
if(head= tail) cout << -1 << "\n";
else {
cout << back() << "\n";
pop_back();
}
}
else if(s= "size") cout << tail-head << "\n";
else if(s= "empty") cout << (head= tail) << "\n";
else if(s= "front") {
if(head= tail) cout << -1 << "\n";
else cout << front() << "\n";
}
else {
if(head= tail) cout << -1 << "\n";
else cout << back() << "\n";
}
}
}문제 풀이
이번 강의에 해당하는 문제는 총 4개였다.
연습문제는 강의를 들으면서 잠시 멈춰놓고 해결하였고, 기본문제 1개, 응용문제 2개를 풀어보려고 하였다.
Note_ 1021번 회전하는 큐 : 문제를 보자마자 양쪽으로 push, pop이 필요해서 덱으로 구현하였다. 구현 시간은 많이 걸리지 않았다.
5430번 AC : 처음에 이해한대로 제출하니 시간초과가 떴다. reverse함수를 R이 나올때마다 실행시켜서 시간초과가 난것이다. 그 후에 생각하는 시간을 많이 가졌고 reverse를해서 pop_front하는 것과 하지않고 pop_back을 하는게 가능하다는 것을 깨닫게 되었다. 생각보다 많은 에러를 봤었지만 해결해서 다행이다.
11003번 최솟값 찾기 : 처음 문제를 봤을 때 전혀 덱을 사용하는 문제라고 생각되지 않아서 한참을 고민하다 이번에는 결국 검색을 하고 정답을 먼저 확인했다. 코드를 보자마자 뒤통수를 맞은 기분이였고, 이렇게 짧은 코드로 구현할 수 있는 문제라는 것을 깨달았다 ,, 코드를 보고 이해한 것을 바탕으로 해보니 바로 맞출 수 있었다. 공부를 한 후에 한번더 풀어볼 문제중에 하나로 적어놓았다.
리뷰
덱이라는 자료구조는 처음 접하는 구조였다.
하지만 큐와 크게 다를것이 없었고 양쪽에서 push, pop이 가능하다는 것만 달라서 쉽게 이해할 수 있었다.
해당하는 문제를 풀어보고 다음 강의로 빠르게 이동해보겠다.
다음은 0x08강 스택의 활용으로 돌아오겠다.
출처: 바킹독님의 실전알고리즘 강의