[자료구조] 덱, 데크(Deque)

덱(Double-Ended Queue, Deque)은 양방향 대기열이라고도 불리는 자료구조이다. 외형적으로는 queue와 비슷한 구조를 갖고있으며, 한 방향인 queue와 stack과는 다르게 LIFO, FIFO같은 순서에 구속되지 않는다.

 

 즉, 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하며 어떤 쪽으로 입력하고 출력하느냐에 따라서 stack과 queue로 사용할 수 있다. 이때, 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)이라고 하고 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)라고 한다.

 

 

 

 

특징

 덱은 다음과 같은 특징을 갖고 있다.

 

• Stack 및 Queue를 모두 사용할 수 있다.
  
   덱은 양쪽으로 데이터를 추가하고 삭제할 수 있기 때문에 둘 다 구현이 가능하다. 만약 양쪽 다 삭제가 가능하고 왼쪽에서만 추가가 가능하게 구현한다면 왼쪽으로 삭제하는 형태는 stack과 같고 오른쪽으로 삭제하는 형태는 queue와 같아진다.
  
   마찬가지로, 양쪽 다 추가가 가능하고 오른쪽에서만 삭제가 가능하게 구현한다면 왼쪽에서는 queue와 같고 오른쪽에서는 stack과 같은 형태를 갖게 된다.
  
   이렇게 추가와 삭제의 기능을 제한해서 상황에 맞는 자료구조를 구현할 수 있다.
•  연속 메모리 공간이 아니다.
• 양방향 끝에서 데이터 추가, 삭제가 용이하다.
  
  
• 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 것은 불가능하다.