[자료구조]Deque

이번 포스트에서는 Deque 자료구조에 대해서 살펴보자.

 

Deque

 

기본 특성

흔히 Deck으로 알려진 Deque는 Double ended Queue의 약자로 Queue인데 양쪽이 모두 뚤린 구조이다. 따라서 앞/뒤로 자료를 넣고 뺄 수 있는 기능을 갖는다.

이에따라 기본적으로 제공되는 메서드들이 방향성을 갖는다.(물론 그렇지 않은 표현도 다 제공한다. 예를 들어 offer와 offerLast는 동일하다.)

	First Element(Head)		Last Element(Tail)
문제 발생 시	예외 발생	특정 값 반환	예외 발생	특정 값 반환
insert	addFirst	offerFirst	addLast	offerLast
remove	removeFirst	pollFirst	removeLast	pollLast
examine	getFirst	peekFirst	getLast	peekLast

 

 

구현체

Deque는 Queue를 상속받은 interface로 구현체로는 ArrayDeque와 LinkedList를 제공한다.

따라서 기본적으로는 Queue의 기능을 가지고 있으며 앞/뒤로 데이터를 추가/삭제할 수 있기 때문에 Stack으로도 사용이 가능하다. 특히 ArrayDeque는 Stack, Queue 보다 성능이 뛰어나다고 알려져있기 때문에 사용을 권장한다.

 

 

Stack, Queue의 대체 메서드

Deque는 Stack과 Queue의 메서드들을 다 가지고 있다. 그런데 가끔 그 메서드들이 헷갈릴 수 있어서 방향성을 갖춘 메서드들을 함께 제공하고 있다.

Queue Method		Stack Method
offer(e)	offerLast(e)	push(e)	offerFirst(e)
poll()	pollFirst()	pop()	pollFirst()
peek()	peekFirst()	peek()	peekFirst()

 

기본적인 동작은 위와 같다. Deque 사용 시 여러 메서드가 팝업되면 헷갈리니까 Queue 는 offer, poll, peek, Stack은 push, pop, peek로 확실히 외워두자. 큐오폴, 스푸팝.

 

또는 Stack, Queue의 특성과 방향성을 잘 생각하면서 offerLast, offerFirst등을 사용하는 것도 괜찮다.

 

 

활용

 

동작 확인해보기

다음의 코드를 디버거를 통해서 돌려보면서 Deque의 동작을 살펴보자.

 

 

관련 문제

https://www.acmicpc.net/problem/10866

10866번: 덱

 

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

https://www.acmicpc.net/problem/5430

5430번: AC