[자료구조] 덱 (Deque)

목차

덱(Deque)의 개념

덱 (Deque)은 Double-ended queue를 줄인 것으로, 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다. 즉, 앞쪽 front와 뒤쪽 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 따라서 스택과 큐의 특성을 모두 갖는 자료구조이다. 

 

덱이 수용할 수 있는 데이터의 크기를 넘어가는 삽입 연산을 수행할 때는 오버플로우가 (Overflow) 발생한다. 그리고 비어 있는 덱에서 삭제 연산을 수행하면 언더플로우 (Underflow)가 발생한다. 

 

덱의 핵심 기능은 앞으로 데이터 삽입, 앞으로 데이터 제거, 뒤로 데이터 삽입, 뒤로 데이터 제거이다. 밑에서 덱의 메서드들과 사용법을 알아보겠다. 

 

 

덱 (Deque) 기능 & 사용법

덱 (Deque) 선언

자바에서의 덱은 인터페이스로 구현되었다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다. 덱 또한 배열 및 연결 리스트로 구현이 가능하지만 덱의 특성상 가장 잘 어울리는 것은 양방향 연결 리스트이다. 

Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new ConcurrentLinkedDeque<>();
Deque<String> deque3 = new LinkedBlockingDeque<>();
Deque<String> deque4 = new LinkedList<>();

 

 

덱 (Deque) 값 추가

메서드	설명
void addFirst()	덱의 앞쪽에 데이터 추가 단, 저장공간이 부족하면 IllegalStateExcepetion 발생
boolean offerFirst()	덱의 앞쪽에 데이터 추가 성공하면 true, 실패하면 false 반환
void addLast()	덱의 뒷쪽에 데이터 추가 단, 저장공간이 부족하면 IllegalStateExcepetion 발생
boolean add()	덱의 뒷쪽에 데이터 추가 (addLast()와 동일) 단, 저장공간이 부족하면 IllegalStateExcepetion 발생
boolean offerLast()	덱의 뒷쪽에 데이터 추가 성공하면 true, 실패하면 false 반환
boolean offer()	덱의 뒷쪽에 데이터 추가 (offerLast()와 동일) 성공하면 true, 실패하면 false 반환

Deque<String> deque = new ConcurrentLinkedDeque<>();
deque.addFirst("Hello");
deque.addLast(" World");
// 덱에는 "Hello World" 있음

deque.offerFirst("Hello");
deque.offerLast(" World");

 

 

덱 (Deque) 값 삭제

 

 

메서드	설명
Object remove()	덱의 앞쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 NoSuchElementException 발생
Object removeFirst()	덱의 앞쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 NoSuchElementException 발생
Object poll()	덱의 앞쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 null 반환
Object pollFirst()	덱의 앞쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 null 반환
Object removeLast()	덱의 뒷쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 NoSuchElementException 발생
Object pollLast()	덱의 뒷쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 null 반환

Deque<String> deque = new ConcurrentLinkedDeque<>();
deque.addFirst("Hello");
deque.addLast(" World");
deque.removeFirst(); //"Hello" 제거
deque.removeLast();  //" World" 제거
deque.remove(); //noSuchElementException 발생

deque.offerFirst("Hello");
deque.offerLast(" World");
deque.pollFirst(); //"Hello" 제거
deque.pollLast(); //" World" 제거
deque.poll(); //null 반환

 

 

덱 (Deque) 값 출력

메서드	설명
Object getFirst()	덱의 앞쪽에 있는 데이터 가지고 옴 단, 덱이 비어 있으면 NoSuchElementException 발생
Object peek()	덱의 앞쪽에 있는 데이터 가지고 옴 단, 덱이 비어 있으면 null 반환
Object peekFirst()	덱의 앞쪽에 있는 데이터 가지고 옴 단, 덱이 비어 있으면 null 반환
Object getLast()	덱의 뒷쪽에 있는 데이터 가지고 옴 단, 덱이 비어 있으면 NoSuchElementException 발생
Object peekLast()	덱의 뒷쪽에 있는 데이터 삭제 단, 덱이 비어 있으면 null 반환

Deque<String> deque = new ConcurrentLinkedDeque<>();
deque.addFirst("Hello");
deque.addLast(" World");
deque.getFirst();  // "Hello" 
deque.getLast();  // " World"
deque.peekFirst(); // "Hello" 
deque.peekLast(); // " World"
deque.clear(); //덱 초기화
deque.getFirst(); //noSuchElementException 발생
deque.peekFirst(); //null 반환