덱(Deque)

덱은 Double-Ended Queue의 줄임말입니다. 큐의 앞과 뒤에서 입력과 삭제가 모두 가능한 큐를 말합니다.
큐의 확장형이라는 느낌을 받을 수 있지만 스택의 성격도 갖고 있습니다. 스택과 큐는 구조의 한계를 갖고 있기 때문에 그에 맞는 용도가 있었습니다. 하지만 덱의 경우 여러가지 용도에 모두 사용이 가능합니다.

덱은 보통 이중 연결 리스트로 구현됩니다.
그 이유는 큐의 앞과 뒤에서 데이터의 입력과 삭제가 모두 이루어질 수 있어야하기 때문입니다.
덱의 앞을 가르키는 주소로 head와 뒤를 가르키는 주소로 tail을 사용합니다.

덱은 보통 스케줄링에 많이 사용되는데 우선순위를 조절하게 될 때 유용합니다. 예를들어 먼저 있던 데이터에 우선순위를 두고 싶다면 앞에서 데이터를 빼내야하는데 이는 스택에서 불가능하고 최근에 들어온 데이터에 우선순위를 두고 싶다면 큐에서 불가능합니다.

add_front, delete_front 연산은 스택의 push, pop과 같은 연산이고 add_rear, delete_front 연산은 큐의 enqueue, dequeue 연산과 같습니다. 추가로 덱은 get_front, get_rear, delete_rear를 가지고 있습니다.