덱(Deque)

디큐 혹은 덱이라고 부르며 쉽게 설명하면 스택(Stack) + 큐(Queue)인 구조라고 생각하면 된다.

1. 스택 + 큐 구조 (엄밀히 말하면 아님)
2. 앞과 뒤 2방향에서 원소를 삽입하거나 삭제할수 있다.
3. 여러 메모리 블록에 나뉘어 저장된다.

어떻게 사용하는가?

#include<deque> // dequeue가 포함된 헤더파일

deque<int> dq; // int형 덱 선언, 다른 자료형을 넣어도 됨

dq.push_front(x); // 덱에 데이터 x를 앞에서 입력한다.

dq.pop_front(); // 덱의 데이터를 앞에서 삭제한다.

dq.push_back(x); // 덱에 데이터 x를 뒤에서 입력한다.

dq.pop_back(); // 덱의 데이터를 뒤에서 삭제한다.

dq.size(); // 덱의 크기를 반환한다.

dq.empty(); // 덱이 비어 있는지 판단한다.

dq.front(); // 덱의 프런트값을 반환한다.

dq.back(); // 덱의 백값을 반환한다.

dq.assign(x, y); // size = x 만큼 y로 초기화

관련 문제

• BOJ 10866 덱 <https://www.acmicpc.net/problem/10866>
• BOJ 5430 AC <https://www.acmicpc.net/problem/5430>