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

덱

• Restricted Structure 
• 양쪽 끝에서 삽입, 삭제 전부 가능한 자료구조

성질

• 원소 추가 / 제거 O(1)
• 제일 앞 / 뒤의 원소 확인 O(1)
• 제일 앞 / 뒤가 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능
  • STL deque에서 인덱스로 원소에 접근 가능

구현

• 배열(더 쉬움)
• 연결리스트

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

원소를 담을 큰 배열 1개, 앞쪽, 뒤쪽을 가리킬 변수 2개 (= 큐)
head: 가장 앞에 있는 원소의 인덱스
tail: 가장 뒤에 있는 원소의 인덱스 + 1
-> 초기값 0이 아닌 MX

큐: 앞(제거), 뒤(삽입)
-> 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 R로 이동하면서 확장
덱: 양쪽 모두에서 삽입 가능 -> 양쪽으로 공간 확장
=> 시작 지점 0번지로 둘 경우 -> L으로 확장할 수 X
=> 시작 지점: 배열의 중간

#include <bits/stdc++.h>
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];
}

void test() {
	
}

int main(void) {
	test();
}

---

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 12
    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의 모든 원소 제거
    
}

 

---