[자료구조] 덱(Deque)

덱(Deque)

• 덱(Deque)은 Doubly-ended Queue의 약자로,
  양쪽 끝에서 추가, 삭제가 가능한 선형 구조 형태의 자료 구조이다.

• 덱(Deque)은 스택과 큐의 장점을 모아서 만들어진 형태이다.

  pushFront + popBack 또는 pushBack + popFront는 큐와 동일하게 기능한다.
  pushFront + popFront 또는 pushBack + popBack은 스택과 동일하게 기능한다.

• 입력과 출력의 순서를 마음대로 정할 수 있다.
  
  
  

Deque의 종류와 특징

1. Deque의 종류

• 스크롤(Scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 데크 (입력 제한 데크)
  (단, 삭제는 양방향 모두 가능)

  
  
  

• 셸프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 데크 (출력 제한 데크)
  (단, 추가는 양방향 모두 가능)

  
  
  

2. Deque의 특징

• 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없으며,
  보통 두 가지 이유 중 하나로 사용하게 된다. (입력과 출력을 추가하는 방식으로 사용)

• 큐(Queue)에서, 양쪽에서 출력할 수 있어야 하는 경우 (스크롤, Scroll) → 입력 제한
• 스택(Stack)에서, 양쪽에서 입력하고 싶은 경우 (셸프, Shelf) → 출력 제한

Deque의 용도

1. 스케줄링을 사용할 때

• 스케줄링이 복잡해질수록 큐(Queue)와 스택(Stack)보다 덱(Deque)이 더 효율이 잘 나오는 경우가 있다.
  
  

2. 우선순위를 조절할 때

ex) 기존에 있던 것의 우선순위를 높이기 위해서는 앞에서 빼낼 수 있어야 하는데, 스택에서는 불가능하다.
ex) 최근에 들어온 것에 우선순위를 주고 싶은데 이 역시 큐의 구조에서는 불가능하다.

→ 결국 앞, 뒤로 모두 인출이 가능한 덱(Deque)만이 이 조건을 충족시킬 수 있다.

Deque의 구현