덱(Deque)

덱(Deque)은 double-ended queue의 줄임말로서 큐의 전단(Front)과 후단(Rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 스택(Stack)과 큐(Queue), 2개의 자료구조를 덱(Deque)을 활용하여 구현 및 사용할 수 있다.

전단 삽입(add_front), 삭제(delete_front), 후단 삽입(add_rear), 삭제(delete_rear) 총 4 가지 기본 연산을 가지고 있다.

 

덱(Deque)은 큐(Queue)를 업그레이드한 자료구조로써 JAVA에선 큐(Queue)처럼 간단하게 라이브러리를 추가하여 별다른 구현 없이 생성할 수 있다.

import java.util.Deque;
import java.util.LinkedList;
Deque<"자료형"> "덱 이름" = new LinkedList<>();

 

덱은 선형 자료구조로써 배열(선형, 원형), 연결 리스트를 이용하여 구현할 수 있다. 하지만 보통 이중 연결 리스트로 구현된다. 그 이유는 전단과 후단에서 모두 삽입, 삭제가 가능해야 하기 때문에 양쪽으로 링크를 가지고 있어야 편리하기 때문이다.

다음은 이중 연결 리스트로 간단하게 구현한 덱(Deque)이다.

class MyDeque<T> {
	private Node front, rear;
	private int size;
	
	class Node<T> {
		private T data;

		public Node(T data) {
			this.data = data;
			prev = next = null;
		}

		private Node prev, next;
	}

	public MyDeque(){
		front = rear = null;
	}

	public void add_front(T data) {
		Node node = new Node(data);
		
		if (is_Empty()) {
			front = node;
			rear = node;
		} else {
			front.prev = node;
			node.next = front;
			front = node;
		}
		size++;
	}

	public void add_rear(T data) {
		Node node = new Node(data);

		if (is_Empty()) {
			front = node;
			rear = node;
		} else {
			rear.next = node;
			node.prev = rear;
			rear = node;
		}
		size++;
	}

	public T delete_front() {
		if (is_Empty()) {
			return null;
		}

		T ret = (T)front.data;
		if (front.next == null) {
			front = rear = null;
		} else {
			front = front.next;
			front.prev = null;
		}
		size--;
		return ret;
	}

	public T delete_rear() {
		if (is_Empty()) {
			return null;
		}

		T ret = (T)rear.data;
		if (rear.prev == null) {
			front = rear = null;
		} else {
			rear = rear.prev;
			rear.next = null;
		}
		size--;
		return ret;
	}

	public int get_front() {
		return (int) front.data;
	}

	public int get_rear() {
		return (int) rear.data;
	}

	public int get_Size() {
		return size;
	}

	public boolean is_Empty() {
		if (get_Size() == 0) return true;
		return false;
	}
}

구현한 덱(Deque)으로 간단한 예제를 테스트한 결과는 다음과 같다.

MyDeque<Integer> dq = new MyDeque<>();
dq.add_front(10);
dq.add_front(3);
dq.add_rear(5);
System.out.println(dq.get_Size());
System.out.println(dq.is_Empty());
System.out.println(dq.delete_front());
System.out.println(dq.delete_rear());
System.out.println(dq.delete_rear());
System.out.println(dq.is_Empty());