선형 자료구조 - 5. 데크

데크 (Deque, Doubly-ended Queue)

 

데크는 양쪽 끝에서 삽입과 삭제가 모두 가능한, 큐와 스택을 합친 형태의 자료구조입니다.

 

 

데크의 구조

 

출처 : 파이썬 알고리즘 인터뷰

데크의 구조는 위와 같으며, 양쪽 끝에서 삽입 및 삭제가 이루어집니다.

 

양쪽 끝은 Head(Front)와 Tail(Rear)라고 부르며, 보통 이중 연결 리스트로 구현을 하게 됩니다.

 

 

데크의 종류

 

데크는 기본적인 데크 외에도 입력 제한 데크(Scroll)과 출력 제한 데크(Shelf)가 있습니다.

 

• 입력 제한 데크 : 한 쪽의 입력을 제한한 데크
• 출력 제한 데크 : 한 쪽의 출력을 제한한 데크

 

 

프로그래밍 언어에서의 구현

Java

자바에서는 Deque를 인터페이스로 제공하고 있습니다. 데크는 ArrayDeque, LinkedList 등으로 구현되어 있습니다.

Deque deque = new ArrayDeque();
deque.addFirst(1);
deque.addLast(2);

deque.pollFirst();
deque.pollLast();