큐는 선입선출 (FIFO)의 속성을 가지고 있다. **스택(Stack)**은 반대로 후입선출(LIFO)의 속성을 가지고 있고, 데크(dequeue) 는 양쪽 끝에서 넣고 뺄 수 있는 자료 구조를 말한다.
이 자료 구조는 동적 배열, 혹은 연결 리스트로 구현할 수 있다
(1) 연결리스트로 구현 시 양쪽 끝에서 상수 시간에 추가와 삭제가 가능하다.
(2) 동적 배열을 이용한 구현 시, 배열의 맨 앞에서 원소 삭제 시 O(n)의 시간이 걸린다는 단점이 있다 → head와 tail을 이용해서 이 점을 보완할 수 있다.
즉 배열 전체가 아닌 head부터 tail까지만 자료구조로 사용하겠다는 건데, 버려지는 공간이 많다는 단점이 있다. 이는 **환형 버퍼 (circular buffer)**의 개념으로 해결할 수 있는데, 동적 배열이 끝까지 사용되면 다시 앞으로 돌아와 처음부터 할당하는 것이다.