덱

덱은 Restricted Structure의 끝판왕 같은 느낌의 자료구조 인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다.

참고로 자료구조에서의 덱은 deque고, Doble Ended Queue라는 뜻이다.

 

덱의 성질

1. 원소의 추가/ 제거 O(1)

2. 제일 앞/뒤의 원소확인 O(1)

3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

하지만 특이하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다.

#include <iostream>
#include <deque>
using namespace std;

int main() {
	deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    
    for(int i = 0; i < dq.size(); i++) {
    	cout << dq[i] << ' ';
    }
    cout << endl;
}

이렇게 사용이 가능하다는 뜻이다.

기존에 큐나 스택은 인덱스로 원소에 접근이 불가능하다.

큐에서는 앞에서는 빼는거만 가능하고 뒤에서는 더하는것만 가능했지만, 덱에서는 front 와 back으로 앞 뒤를 구분하고 둘 다 빼고 넣는 것이 가능하다.