덱(Deque)

덱은 무엇인가?

-양쪽 끝에서 삽입과 삭제가 가능한 자료구조

덱의 성질은?

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞뒤의 원소 확인이 O(1)
4. 제일 앞뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

덱의 용도는?

-배열을 써야하는데 앞/뒤가 모두 중요할때

 

STL

deque<int> deq;
deq.push_front(1); // 1
deq.push_back(5); // 1 5
deq.push_front(2); // 2 1 5
for(auto x : deq) cout << x << '\n';
cout << deq.size() << '\n';
if(!deq.empty()) cout << "deque isn't empty" << '\n';
deq.pop_front(); // 1 5
deq.pop_back(); // 1
deq.push_back(2); // 1 2
deq[1] = 4 // 1 4 vector처럼 인덱싱가능
deq.insert(deq.begin()+1, 7); // 1 7 4
deq.erase(deq.begin()+1); // 1 4
deq.clear();