덱(Double-Ended Queue, Deque)은 양방향 대기열이라고도 불리는 자료구조이다. 외형적으로는 queue와 비슷한 구조를 갖고있으며, 한 방향인 queue와 stack과는 다르게 LIFO, FIFO같은 순서에 구속되지 않는다. 즉, 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하며 어떤 쪽으로 입력하고 출력하느냐에 따라서 stack과 queue로 사용할 수 있다. 이때, 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)이라고 하고 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)라고 한다. 특징 덱은 다음과 같은 특징을 갖고 있다. Stack 및 Queue를 모두 사용할 수 있다. 덱은 양쪽으로 데이터를 추가하고 삭제할 수 있기 때문에 둘 다 구현이 가능하다. 만약 양쪽 ..