[윤성우의 열혈 자료구조]덱(Double ended queue, Deque) - 자바(Java) 구현

덱(Deque)

• Double ended queue

• 양쪽 방향 어디에서든 넣고, 뺄 수 있다.(양쪽 방향으로 모두 입출력이 가능)

• 스택과 큐의 특성을 모두 지니고 있다고도 말한다.
  • 덱을 스택으로도 사용할 수 도있고, 큐로도 활용할 수도 있다는 의미.

• 덱의 구현에 가장 어울리는 자료구조는 양방향 연결리스트이다.

덱 자료구조의 추상 자료형(ADT)

	boolean DQIsEmpty(); //덱이 비어있는지 확인하는 메소드

	void DQAddFirst(T data); //덱의 머리에 데이터를 저장(앞으로 넣기)

	void DQAddLast(T data); //덱의 꼬리에 데이터를 저장(뒤로 넣기)

	T DQRemoveFirst(); //덱의 머리에 위치한 데이터를 삭제(앞에서 빼기)

	T DQRemoveLast(); //덱의 꼬리에 위치한 데이터를 삭제(뒤로 빼기)

	T DQGetFirst(); //덱의 머리에 위치한 데이터를 조회(앞에서 PEEK)

	T DQGetLast(); //덱의 꼬리에 위치한 데이터를 조회(뒤에서 PEEK)

덱

public class Deque<T> {

	//노드를 표현한 클래스
	private class Node{
		private T data;
		private Node prevLink;
		private Node nextLink;
		
		private Node(T data) {
			this.data = data;
			this.prevLink = null;
			this.nextLink = null;
		}
	}

	private Node head;					//덱의 시작 부분을 가리키는 멤버
	private Node tail;					//덱의 마지막 부분을 가리키는 멤버
	
	/**
	 * 덱이 비어있는지 확인하는 메소드
	 */
	private boolean DQIsEmpty() {
		if(head == null)
			return true;
		
		return false;
	}

	/**
	 * 덱의 앞부분에 데이터를 저장하는 메소드
	 * @param data
	 */
	private void DQAddFirst(T data) {
		Node newNode = new Node(data);
		newNode.nextLink = head;
		
		if(DQIsEmpty()) {
			tail = newNode;	
		}else {
			head.prevLink = newNode;
		}
		
		newNode.prevLink = null;
		head = newNode;
	}
	
	/**
	 * 덱의 뒷부분에 데이터를 저장하는 메소드
	 * @param data
	 */
	private void DQAddLast(T data) {
		Node newNode = new Node(data);
		newNode.prevLink = tail;
		
		if(DQIsEmpty()) {
			head = newNode;
		}else {
			tail.nextLink = newNode;
		}
		newNode.nextLink = null;
		tail = newNode;
	}

	/**
	 * 덱의 앞부분에 위치한 데이터를 삭제하는 메소드
	 * @return
	 */
	private T DQRemoveFirst() {
		if(DQIsEmpty())
			new ArrayIndexOutOfBoundsException("Queue Memory Empty!");
		
		Node rNode = head;
		head = rNode.nextLink;
		
		if(head == null) {
			tail = null;
		}else {
			head.prevLink = null;			
		}
		
		return rNode.data;
	}
	
	/**
	 * 덱의 뒷부분에 위치한 데이터를 삭제하는 메소드
	 * @return
	 */
	private T DQRemoveLast() {
		if(DQIsEmpty())
			new ArrayIndexOutOfBoundsException("Queue Memory Empty!");

		Node rNode = tail;
		tail = tail.prevLink;

		if(tail == null) {
			head = null;
		}else {
			tail.nextLink = null;		
		}
		
		return rNode.data;
	}

	/**
	 * 덱의 앞부분에 위치한 데이터를 조회하는 메소드
	 * @return
	 */
	private T DQGetFirst() {
		if(DQIsEmpty())
			new ArrayIndexOutOfBoundsException("Queue Memory Error!");
		
		return head.data;
	}
	
	/**
	 * 덱의 뒷부분에 위치한 데이터를 조회하는 메소드
	 * @return
	 */
	private T DQGetLast() {
		if(DQIsEmpty())
			new ArrayIndexOutOfBoundsException("Queue Memory Error!");
		
		return tail.data;
	}
	
	public static void main(String[] args) {
		Deque<Integer> Deque = new Deque<>();
		
		// 데이터 넣기 1차 ///////
		Deque.DQAddFirst(3); 
		Deque.DQAddFirst(2); 
		Deque.DQAddFirst(1); 

		Deque.DQAddLast(5); 
		Deque.DQAddLast(6);
		Deque.DQAddLast(4); 

		// 데이터 꺼내기 1차 ///////
		while(!Deque.DQIsEmpty())
			System.out.printf("%d ", Deque.DQRemoveFirst());

		System.out.printf("\n");

		// 데이터 넣기 2차 ///////
		Deque.DQAddFirst(3); 
		Deque.DQAddFirst(2); 
		Deque.DQAddFirst(1);
		
		Deque.DQAddLast(4); 
		Deque.DQAddLast(5); 
		Deque.DQAddLast(6);

		// 데이터 꺼내기 2차 ///////
		while(!Deque.DQIsEmpty())
			System.out.printf("%d ", Deque.DQRemoveLast());
	}
}

 

---

[참고자료]

윤성우의 열혈 자료구조