[자료구조] 덱 Dequeue

덱은 스택과 큐에 대한 기본적인 이해가 있는 것이 좋다. 혹시 스택과 큐의 개념을 잘 모른다면 관련 내용을 먼저 확인하고 오길 바란다. (스택, 큐)

 

덱 (Dequeue, Double-ended Queue)

  덱은 스택과 큐를 합친 것이라고 보면 된다. 덱은 양쪽 끝에서 데이터를 넣고 뺄 수 있다. (큐에서 가장 앞에 위치한 데이터를 뽑아내는 연산과 표현이 같지만 동일한 개념이 아니므로 주의해야 한다.) 실제로 입출력 모두 양쪽에서 가능하도록 설정하는 덱은 별로 존재하지 않으며 기존 스택 혹은 큐에서 입력 혹은 출력 중 하나만 양쪽에서 이루어질 수 있도록 확장한 개념으로 많이 사용한다.

 

(1) 스크롤 (scroll) : 출력은 양방향이 가능하지만 입력은 한쪽 끝만 가능한 덱

(2) 쉘프 (shelf) : 입력은 양방향이 가능하지만 출력은 한쪽 끝만 가능한 덱

 

덱의 연산

(1) append( ) : 덱의 맨 뒤에 새로운 아이템을 추가한다.

(2) appendLeft( ) : 덱의 맨 앞에 새로운 아이템을 추가한다.

(3) pop( ) : 덱의 맨 뒤에 위치한 아이템을 뽑아낸다.

(4) popLeft( ) : 덱의 맨 앞에 위치한 아이템을 뽑아낸다.

 

덱의 성능

- 탐색 : 스택에서 탐색은 모든 아이템을 하나하나 훑어봐야 되기 때문에 O(n)시간이 필요하다.

- 삽입 / 제거 : O(1) (덱에서 삽입/제거 연산의 성능이 중요한 이유는 그것이 배열과 비교되기 때문이다. 배열에서 끝에 항목을 추가하는 것은 O(1)에 가능하지만 맨 앞에 아이템을 추가하게 되면 기존에 있던 아이템들이 한 칸씩 모두 옆으로 밀려나기 때문에 O(n)의 시간이 소요된다. 맨 앞에 있는 원소를 제거할 때에도 기존의 아이템들을 모두 한 칸씩 땡겨야 하기 때문에 O(n)의 시간이 소요될 것이다. 덱은 어떠한 방향에서 연산을 수행해도 O(1)의 퍼포먼스를 보여준다.)