[자료구조] 덱(Deque, Double-ended Queue) 설명 및 구현

1. 덱(Deque, Double-ended Queue)

덱은 큐의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능하게 만든 큐로서, 스택과 큐의 성질을 모두 가지고 있는 자료구조입니다.

 

덱의 구조

2. 덱의 연산

덱은 양쪽 끝에서 데이터의 삽입과 삭제 연산을 모두 할 수 있기 때문에, 스택과 큐의 연산을 모두 구현할 수 있습니다.

· 스택 연산

front를 스택의 top으로 생각했을 때, 덱의 insertFront() 연산과 deleteFront() 연산은 push() 연산, pop() 연산과 같습니다.

 

rear를 스택의 top으로 생각했을 때, 덱의 insertRear() 연산과 deleteRear() 연산은 push() 연산, pop() 연산과  같습니다.

· 큐 연산

insertRear() 연산과 deleteFront() 연산은 일반 큐의 enQueue() 연산, deQueue() 연산과 같습니다.

3. 덱 구현

덱은 양쪽 끝에서 데이터의 삽입과 삭제 연산이 가능해야 하기 때문에, 왼쪽 링크 필드와 오른쪽 링크 필드를 가지는 노드를 사용하는 이중 연결 리스트를 이용하여 구현해야 합니다.

 

· DQNode

public class DQNode {
	private char data; // 데이터 필드
	public DQNode llink; // 왼쪽 링크 필드
	public DQNode rlink; // 오른쪽 링크 필드

	public DQNode(char data) {
		this.data = data;
		this.llink = null;
		this.rlink = null;
	}
	
	public char getData() {
		return this.data;
	}
}

 

· Deque

public class Deque {
	private DQNode front;
	private DQNode rear;

	// 덱 초기화
	public Deque() {
		this.front = null;
		this.rear = null;
	}

	public boolean isEmpty() {
		return (front == null); // front가 null인 경우 공백상태
	}

	public void insertFront(char data) {
		DQNode newNode = new DQNode(data);

		if (isEmpty()) { // 덱에 노드가 없을 경우
			front = newNode;
			rear = newNode;
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			front.llink = newNode;
			newNode.rlink = front;
			front = newNode;
		}
	}

	public void insertRear(char data) {
		DQNode newNode = new DQNode(data);

		if (isEmpty()) { // 덱에 노드가 없을 경우
			front = newNode;
			rear = newNode;
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			rear.rlink = newNode;
			newNode.llink = rear;
			rear = newNode;
		}
	}

	public char deleteFront() {
		if (isEmpty()) { // 덱에 노드가 없을 경우
			System.out.println("덱이 공백상태입니다.\n");
			return 0;
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			char data = front.getData();
			if (front.rlink == null) { // 덱에 노드가 한 개일 경우
				front = null;
				rear = null;
			} else { // 덱에 노드가 두 개 이상일 경우
				front = front.rlink;
				front.llink = null;
			}
			return data;
		}
	}

	public char deleteRear() {
		if (isEmpty()) { // 덱에 노드가 없을 경우
			System.out.println("덱이 공백상태입니다.\n");
			return 0;
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			char data = rear.getData();
			if (rear.llink == null) { // 덱에 노드가 한 개일 경우
				front = null;
				rear = null;
			} else { // 덱에 노드가 두 개 이상일 경우
				rear = rear.llink;
				rear.rlink = null;
			}
			return data;
		}
	}

	public void removeFront() {
		if (isEmpty()) { // 덱에 노드가 없을 경우
			System.out.println("덱이 공백상태입니다.\n");
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			if (front.rlink == null) { // 덱에 노드가 한 개일 경우
				front = null;
				rear = null;
			} else { // 덱에 노드가 두 개 이상일 경우
				front = front.rlink;
				front.llink = null;
			}
		}
	}

	public void removeRear() {
		if (isEmpty()) { // 덱에 노드가 없을 경우
			System.out.println("덱이 공백상태입니다.\n");
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			if (rear.llink == null) { // 덱에 노드가 한 개일 경우
				front = null;
				rear = null;
			} else { // 덱에 노드가 두 개 이상일 경우
				rear = rear.llink;
				rear.rlink = null;
			}
		}
	}

	public char peekFront() {
		if (isEmpty()) { // 덱에 노드가 없을 경우
			System.out.println("덱이 공백상태입니다.\n");
			return 0;
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			return front.getData();
		}
	}

	public char peekRear() {
		if (isEmpty()) { // 덱에 노드가 없을 경우
			System.out.println("덱이 공백상태입니다.\n");
			return 0;
		} else { // 덱에 노드가 한 개 이상 존재할 경우
			return rear.getData();
		}
	}

	// 덱 출력
	public void printDeque() {
		if (isEmpty()) {
			System.out.println("덱이 공백상태입니다.\n");
		} else {
			DQNode temp = front;
			System.out.printf("Deque = ");
			while (temp != null) {
				System.out.printf("%c ", temp.getData());
				temp = temp.rlink;
			}
			System.out.println("\n");
		}
	}
}

 

· MainForDeque

public class MainForDeque {
	public static void main(String[] args) {
		Deque dQ = new Deque();

		// insertRear()와 deleteRear()를 사용하여 후입선출 구조인 스택 구현
		System.out.println("***** 덱을 후입선출 구조인 스택처럼 사용하기 *****\n");
		System.out.println("1. 원소 3개 푸쉬");
		for (char c = 'A'; c <= 'C'; c++) {
			dQ.insertRear(c);
		}
		dQ.printDeque();

		System.out.println("2. 원소 2개를 팝");
		for (int i = 0; i < 2; i++) {
			System.out.printf("Deleted Data: %c\n", dQ.deleteRear());
			dQ.printDeque();
		}

		System.out.println("3. 원소 1개 삭제");
		dQ.deleteRear();
		dQ.printDeque();

		// insertRear()오 deleteFront()를 사용하여 선입선출 구조인 큐 구현하기
		System.out.println("***** 덱을 선입선출 구조인 큐처럼 사용하기 *****\n");
		System.out.println("1. 원소 3개 인큐");
		for (char c = 'A'; c <= 'C'; c++) {
			dQ.insertRear(c);
		}
		dQ.printDeque();

		System.out.println("2. 원소 2개를 디큐");
		for (int i = 0; i < 2; i++) {
			System.out.printf("Deleted Data: %c\n", dQ.deleteFront());
			dQ.printDeque();
		}

		System.out.println("3. 원소 1개 삭제");
		dQ.deleteFront();
		dQ.printDeque();
	}
}

 

 · 실행 결과