Deque의 특징
양방향 큐라고도 불리는 덱(Double-ended queue: Deque)은 맨 앞과 맨 끝, 양 쪽에서 요소의 삽입/삭제가 가능한 자료구조이다.
덱은 맨 끝으로만 요소 삽입이 가능했던 스택과 큐의 단점을 보완하고,
맨 뒤의 요소만 반환(삭제) 가능했던 스택, 맨 앞의 요소만 반환(삭제) 가능했던 큐의 기능을 통합한 자료구조이다.
Deque의 구현 방법
큐와 마찬가지로 덱도 배열 또는 연결리스트로 구현 가능하다.
주의할 점은 단방향 연결리스트가 아닌, 양방향 연결리스트로 구현한다는 것이다.
그리고 큐가 그랬던 것 처럼, 배열이 아닌 연결리스트로 구현하는 것이 더 편리하다.
- 배열로 큐를 구현할 경우, 저장될 요소의 개수에 따라 배열의 크기를 동적으로 조정해주는 작업이 필요하다.
- 요소의 추가/삭제가 반복되면 요소들의 위치가 배열의 뒤로 쏠리는 현상이 발생한다. 따라서 요소들의 위치를 조정해주기 위한 작업이 필요하다.
Deque 구현
큐를 구현할 때 사용했던 인터페이스에 기반하여 덱을 구현할 것이다.
배열과 연결리스트를 이용해서 구현할 것이며, 실제 사용 코드에서는 연결리스트로 구현한 덱을 사용할 것이다.
구현체만 다를 뿐 배열 덱, 연결리스트 덱 모두 사용법은 동일하다.
Queue 인터페이스
public interface QueueInterface<T> {
/**
* 큐의 맨 끝에 요소를 추가한다.
* @param element: 추가할 요소
* @return 추가 성공: true, 추가 실패: false
*/
boolean offer(T element);
/**
* 큐의 맨 앞 요소를 제거하고 반환한다.
* @return 큐의 맨 앞 요소
*/
T poll();
/**
* 큐의 맨 앞 요소를 반환한다.
* @return 큐의 맨 앞 요소
*/
T peek();
/**
* 큐의 맨 앞 요소를 제거하고 반환한다.
* 요소가 없을 경우 예외 발생 <- poll()과 차이점
* @return 큐의 맨 앞 요소
*/
T remove();
/**
* 큐의 맨 앞 요소를 반환한다.
* 요소가 없을 경우 예외 발생 <- peek()와 차이점
* @return 큐의 맨 앞 요소
*/
T element();
}
ArrayDeque 구현부
public class ArrayDeque<T> implements QueueInterface<T> {
private static final int DEFAULT_CAPACITY = 10; // 기본 용적 크기
private T[] array; // 저장 공간
private int size; // 요소 개수
private int front; // 시작 인덱스(항상 빈 공간 <- 큐가 비어있는지를 확인하기 위함)
private int rear; // 마지막 요소의 인덱스
// 용적 크기 0
@SuppressWarnings("unchecked")
public ArrayDeque() {
this.array = (T[]) new Object[0];
this.size = 0;
this.front = 0;
this.rear = 0;
}
// 용적 크기: capacity
@SuppressWarnings("unchecked")
public ArrayDeque(int capacity) {
this.array = (T[]) new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = 0;
}
@SuppressWarnings("unchecked")
private void resize() {
int arrayCapacity = array.length;
// 저장 공간 0
if (arrayCapacity == 0) {
array = (T[]) new Object[DEFAULT_CAPACITY];
return;
}
// 저장 공간이 가득 찬 경우
if ((rear + 1) % arrayCapacity == front) {
T[] newArray = (T[]) new Object[arrayCapacity * 2];
copyArray(arrayCapacity, newArray);
}
// 저장 공간/2 > 요소 개수
if (size < (arrayCapacity/2)) {
T[] newArray = (T[]) new Object[Math.max(arrayCapacity / 2, DEFAULT_CAPACITY)];
copyArray(arrayCapacity, newArray);
}
}
private void copyArray(int arrayCapacity, T[] newArray) {
for (int i = 1, j = front + 1; i <= size; i++, j++) {
newArray[i] = array[j % arrayCapacity];
}
this.array = newArray;
front = 0;
rear = size;
}
// 덱 맨 끝에 요소를 추가한다.
// offer는 기본적으로 offerLast와 동일하게 작동한다.
@Override
public boolean offer(T element) {
return offerLast(element);
}
// 덱 맨 끝에 요소를 추가한다.
public boolean offerLast(T element) {
// 요소 삽입 전에 용적 크기 재조정
resize();
// 요소가 저장될 인덱스
rear = (rear + 1) % array.length;
array[rear] = element;
size++;
return true;
}
// 덱 맨 앞에 요소를 추가한다.
public boolean offerFirst(T element) {
// 요소 삽입 전에 용적 크기를 재조정
resize();
// 현재 front 인덱스(빈 공간)에 요소 삽입
array[front] = element;
// 새로운 front 지정
front = (front - 1 + array.length) % array.length;
size++;
return true;
}
// 덱 맨 앞의 요소를 제거하고 반환
// poll은 기본적으로 pollFirst와 동일하게 작동한다.
@Override
public T poll() {
return pollFirst();
}
// 덱 맨 앞의 요소를 제거하고 반환
public T pollFirst() {
// 삭제할 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
front = (front + 1) % array.length;
// 삭제하고 반환할 요소
T element = array[front];
array[front] = null;
size--;
resize();
return element;
}
// 덱 맨 끝의 요소를 제거하고 반환
public T pollLast() {
// 삭제할 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
// 삭제하고 반환할 요소
T element = array[rear];
array[rear] = null;
// 새로운 rear
rear = (rear - 1 + array.length) % array.length;
size--;
resize();
return element;
}
// 맨 앞 요소를 반환
@Override
public T peek() {
return peekFirst();
}
// 맨 앞 요소를 반환
public T peekFirst() {
// 삭제할 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
return array[(front + 1) % array.length];
}
// 맨 끝 요소를 반환
public T peekLast() {
// 삭제할 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
return array[rear];
}
// 맨 앞 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- pollFirst()와 차이
@Override
public T remove() {
return removeFirst();
}
// 맨 앞 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- pollFirst()와 차이
public T removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return pollFirst();
}
// 맨 끝 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- pollLast()와 차이
public T removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return pollLast();
}
// 맨 앞 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peek()와 차이
@Override
public T element() {
return peekFirst();
}
// 맨 앞 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peekFirst()와 차이
public T getFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return peekFirst();
}
// 맨 끝 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peekLast()와 차이
public T getLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return peekLast();
}
// 요소 개수 반환
public int size() {
return size;
}
// 덱이 비어있는 지 여부 반환
public boolean isEmpty() {
return size == 0;
}
// 목표 요소의 저장 여부 반환
public boolean contains(T element) {
int start = (front + 1) % array.length;
for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
if(array[idx].equals(element)) {
return true;
}
}
return false;
}
// 덱의 모든 요소 제거
@SuppressWarnings("unchecked")
public void clear() {
this.array = (T[]) new Object[array.length];
size = 0;
front = 0;
rear = 0;
resize();
}
@Override
public String toString() {
int start = (front + 1) % array.length;
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
stringBuilder.append(" ").append(array[idx]);
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
}
NodeBi 구현부(LinkedListDeque의 요소)
public class NodeBi<T> {
T element; // 요소
NodeBi<T> next; // 다음 노드 참조
NodeBi<T> prev; // 이전 노드 참조
public NodeBi(T element) {
this.element = element;
this.next = null;
this.prev = null;
}
}
LinkedListDeqeue 구현부
public class LinkedListDeque<T> implements QueueInterface<T> {
private NodeBi<T> head; // 첫 번째 노드에 대한 참조
private NodeBi<T> tail; // 마지막 노드에 대한 참조
private int size; // 요소 개수(= head~tail의 노드 개수)
public LinkedListDeque() {
head = null;
tail = null;
size = 0;
}
// 덱 맨 끝에 요소를 추가한다.
// offer는 기본적으로 offerLast와 동일하게 작동한다.
@Override
public boolean offer(T element) {
return offerLast(element);
}
// 덱 맨 끝에 요소를 추가한다.
public boolean offerLast(T element) {
// 기존에 노드가 없었을 경우
if (size == 0) {
return offerFirst(element);
}
// 추가할 새로운 노드 생성
NodeBi<T> newNode = new NodeBi<>(element);
tail.next = newNode; // 기존 tail이 다음 노드로 새로운 노드를 참조
newNode.prev = tail; // 새로운 노드가 이전 노드로 기존 tail을 참조
tail = newNode; // tail이 새로운 노드를 참조
size++;
return true;
}
// 덱 맨 앞에 요소를 추가한다.
public boolean offerFirst(T element) {
// 추가할 새로운 노드 생성
NodeBi<T> newNode = new NodeBi<>(element);
// 새로운 노드의 next가 기존 head를 참조
newNode.next = head;
if (head != null) { // 기존에 노드가 있었을 경우
head.prev = newNode;
head = newNode;
} else { // 기존에 노드가 없었을 경우
head = newNode;
tail = newNode;
}
size++;
return true;
}
// 덱 맨 앞의 요소를 제거하고 반환
// poll은 기본적으로 pollFirst와 동일하게 작동한다.
@Override
public T poll() {
return pollFirst();
}
// 덱 맨 앞의 요소를 제거하고 반환
public T pollFirst() {
// 삭제할 요소가 없는 경우, null
if (size == 0) {
return null;
}
T element = head.element; // 삭제하고 반환하려는 요소
NodeBi<T> nextNode = head.next; // 삭제할 노드의 다음 노드
if (nextNode != null) { // 기존 노드가 두 개 이상
nextNode.prev = null;
head = null;
head = nextNode;
} else { // 기존 노드가 한 개
head = null;
tail = null;
}
size--;
return element;
}
// 덱 맨 끝의 요소를 제거하고 반환
public T pollLast() {
// 삭제할 요소가 없는 경우, null
if (size == 0) {
return null;
}
T element = tail.element; // 삭제하고 반환하려는 요소
NodeBi<T> prevNode = tail.prev; // 삭제할 노드의 이전 노드
if (prevNode != null) { // 기존 노드가 두 개 이상
prevNode.next = null;
tail = null;
tail = prevNode;
} else { // 기존 노드가 한 개
head = null;
tail = null;
}
size--;
return element;
}
// 맨 앞 요소를 반환
@Override
public T peek() {
return peekFirst();
}
// 맨 앞 요소를 반환
public T peekFirst() {
// 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
return head.element;
}
// 맨 끝 요소를 반환
public T peekLast() {
// 요소가 없을 경우 null 반환
if (size == 0) {
return null;
}
return tail.element;
}
// 맨 앞 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- pollFirst()와 차이
@Override
public T remove() {
return removeFirst();
}
// 맨 앞 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- pollFirst()와 차이
public T removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return pollFirst();
}
// 맨 끝 요소를 제거하고 반환
// 요소가 없을 경우, 예외 발생 <- pollLast()와 차이
public T removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return pollLast();
}
// 맨 앞 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peek()와 차이
@Override
public T element() {
return peekFirst();
}
// 맨 앞 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peekFirst()와 차이
public T getFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
return peekFirst();
}
// 맨 끝 요소를 반환
// 요소가 없을 경우, 예외 발생 <- peekLast()와 차이
public T getLast() {
if (size == 0) {
throw new NoSuchElementException();
}
return peekLast();
}
// 요소 개수 반환
public int size() {
return size;
}
// 덱이 비어있는 지 여부 반환
public boolean isEmpty() {
return size == 0;
}
// 목표 요소의 저장 여부 반환
public boolean contains(T element) {
for (NodeBi<T> x = head; x != null; x = x.next) {
if (element.equals(x.element)) {
return true;
}
}
return false;
}
// 덱의 모든 요소 제거
public void clear() {
for (NodeBi<T> x = head; x != null; ) {
NodeBi<T> next = x.next;
x.element = null;
x.next = null;
x = next;
}
size = 0;
head = null;
tail = null;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (NodeBi<T> x = head; x != null; x = x.next) {
stringBuilder.append(" ").append(x.element);
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
}
실제 사용
public class Main {
public static void main(String[] args) {
LinkedListDeque<Integer> linkedListDeque = new LinkedListDeque<>();
for (int i = 0; i < 10; i++) {
linkedListDeque.offer(i + 1);
}
for (int i = 10; i < 20; i++) {
linkedListDeque.offerLast(i + 1);
}
System.out.println("linkedListDeque = " + linkedListDeque);
// linkedListDeque = [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]
/////////////////////////////////////////////////////////////////////////
System.out.println("linkedListDeque.peekFirst() = " + linkedListDeque.peekFirst());
// linkedListDeque.peekFirst() = 1
System.out.println("linkedListDeque.peekLast() = " + linkedListDeque.peekLast());
// linkedListDeque.peekLast() = 20
System.out.println("linkedListDeque = " + linkedListDeque);
// linkedListDeque = [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]
System.out.println("linkedListDeque.pollFirst() = " + linkedListDeque.pollFirst());
// linkedListDeque.pollFirst() = 1
System.out.println("linkedListDeque.pollLast() = " + linkedListDeque.pollLast());
// linkedListDeque.pollLast() = 20
System.out.println("linkedListDeque = " + linkedListDeque);
// linkedListDeque = [ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ]
/////////////////////////////////////////////////////////////////////////
System.out.println("linkedListDeque.isEmpty() = " + linkedListDeque.isEmpty());
// linkedListDeque.isEmpty() = false
linkedListDeque.clear();
System.out.println("linkedListDeque.isEmpty() = " + linkedListDeque.isEmpty());
// linkedListDeque.isEmpty() = true
}
}