[Java / 자료구조] Deque 개념 및 정리

Deque 정의

Deque는 Double Ended Queue의 양방향 대기열이라고도 불리는 자료구조이다.

양방향으로 열려있는 구조로 Queue와 외형적으로 비슷한 구조이다. 그러나 Deque는 Stack과 Queue와 달리 LIFO, FIFO와 같은 순서에 구속되지 않는다.

 

 

Deque 특징

Stack 및 Queue를 모두 사용할 수 있다.

Deque는 양쪽으로 데이터를 추가하고 삭제할 수 있어서 Stack과 Queue를 구현할 수 있다. 추가와 삭제를 양쪽에서 제어할 수 있어서 여러 형태로 사용할 수 있다.

 

• 추가를 제한하는 구조

한쪽에서만 데이터 추가가 가능하고 삭제는 양방향에서 가능하게 구현한다면 아래와 같은 구조

데이터 추가의 방향이 정해진 상태가 된다. 왼쪽으로 삭제하는 형태는 Stack과 같고 오른쪽으로 삭제하는 형태는 Queue와 같다.

 

• 삭제를 제한하는 구조

데이터 추가는 양쪽에서 가능하지만, 삭제는 한 방향에서만 가능하게 구현한다면 아래와 같은 구조

왼쪽에서 추가하는 형태는 Stack과 같고 오른쪽에서 추가하는 형태는 Queue와 같다.

 

양방향 끝에서 데이터 추가, 삭제가 용이하다.

Stack과 Queue에서 추가할 데이터나 삭제할 데이터의 인덱스 정보를 가지고 있듯이 Deque도 양쪽의 추가 삭제할 데이터의 인덱스 정보를 가지고 있어서 양쪽 끝의 데이터에 접근과 추가, 삭제가 용이하다.

 

양방향 끝이 아닌 임의 데이터만 추가하거나 삭제하는 건 불가능하다.

Deque는 양방향 끝의 인덱스 정보를 가지고 있다. 따라서 양방향의 데이터가 아닌 중간에 있는 데이터에 접근하려고 하면 인덱스 정보가 없어서 접근할 수 없다. 

 

 

Deque 선언

Deque<Integer> deque = new LinkedList<>();
Deque<Integer> deque = new ArrayDeque<>();

Deque를 선언할 때 보통 LinkedList와 ArrayDeque를 사용한다.

 

 

Deque 값 삽입

add()	마지막에 원소를 삽입한다. 용량 초과 시 예외(Exception)가 발생한다.
addFirst()	맨 앞에 원소를 삽입한다. 용량 초과 시 예외(Exception)가 발생한다.
addLast()	마지막에 원소를 삽입한다. 용량 초과 시 예외(Exception)가 발생한다.
offer()	마지막에 원소를 삽입한다. 삽입 성공 시 true, 용량 제한에 걸리는 경우 false를 리턴한다.
offerFirst()	맨 앞에 원소를 삽입한다. 삽입 성공 시 true, 용량 제한에 걸리는 경우 false를 리턴한다.
offerLast()	마지막에 원소를 삽입한다. 삽입 성공 시 true, 용량 제한에 걸리는 경우 false를 리턴한다.

 

 

Deque 값 삭제

remove()	맨 앞의 원소 제거 후 해당 원소를 리턴한다. 덱이 비어있는 경우 예외(Exception)가 발생한다.
removeFirst()	맨 앞의 원소 제거 후 해당 원소를 리턴한다. 덱이 비어있는 경우 예외(Exception)가 발생한다.
removeLast()	마지막 원소 제거 후 해당 원소를 리턴한다.덱이 비어있는 경우 예외(Exception)가 발생한다.
poll	맨 앞의 원소 제거 후 해당 원소를 리턴한다. 덱이 비어있는 경우 null 리턴
pollFirst()	맨 앞의 원소 제거 후 해당 원소를 리턴한다. 덱이 비어있는 경우 null 리턴
pollLast()	마지막 원소 제거 후 해당 원소를 리턴한다. 덱이 비어있는 경우 null 리턴

 

 

Deque 값 확인

getFirst()	맨 앞의 원소를 리턴한다. 덱이 비어있는 경우 예외(Exception)가 발생한다.
getLast()	마지막 원소를 리턴한다. 덱이 비어있는 경우 예외(Exception)가 발생한다.
peek()	맨 앞의 원소를 리턴한다. 덱이 비어있는 경우 null 리턴
peekFirst()	맨 앞의 원소를 리턴한다. 덱이 비어있는 경우 null 리턴
peekLast()	마지막 원소를 리턴한다 .덱이 비어있는 경우 null 리턴

 

 

추가적인 메서드 확인하려면 아래 사이트를 참고

https://www.geeksforgeeks.org/deque-interface-java-example/

Deque interface in Java with Example - GeeksforGeeks