Deque 덱

1. Deque 덱이란?

: Double-Ended Queue이다. 큐의 양쪽끝에서 삽입과 삭제가 모두 발생할 수 있는 큐이다.

양방향 큐, 즉 스택으로도 사용할 수 있고 큐처럼 사용할 수 있는 자료구조이다.

 

2. 연결리스트를 이용한 Deque 구현 코드

class DequeType {
	Node head;
	Node tail;
	
	public DequeType() {
		head = null;
		tail = null;
	}
	
	//초기화 함수
	public void init() {
		head = null;
		tail = null;
	}
	
	//비어있나?
	public boolean isEmpty() {
		return head == null;
	}
	
	//전단 삽입
	public void add_head(int data) {
		Node newNode = new Node(data);
		
		if (isEmpty()) {
			head = newNode;
			tail = newNode;
		} else {
			newNode.rlink = head;
			head.llink = newNode;
			head = newNode;
		}
	}
	
	//후단 삽입
	public void add_tail(int data) {
		Node newNode = new Node(data);
		
		if (isEmpty()) {
			head = newNode;
			tail = newNode;
		} else {
			tail.rlink = newNode;
			newNode.llink = tail;
			tail = newNode;
		}
	}
	
	//전단 삭제
	public int delete_front() {
		Node removed_node;
		int item;
		
		if (isEmpty()) 
			return -1;
		else {
			removed_node = head;
			item = removed_node.data;		
			head = removed_node.rlink;
			
			if (head != null) {
				head.llink = null;
			} else {
				tail = null;
			}
			return item;
		}
	}
    
	//후단 삭제
	public int delete_tail() {
		Node removed_node;
		int item;
		
		if (isEmpty())
			return -1;
		else {
			removed_node = tail;
			item = removed_node.data;
			tail = removed_node.llink;
			
			if (tail != null) {
				tail.rlink = null;
			} else {
				head = null;
			}
			return item;
		}
	}
	//display
	public void display() {
		for (Node n = head; n != null; n = n.rlink) {
			System.out.print(n.data + " ");
		}
	}
}

class Node {
	int data;
	Node llink;
	Node rlink;
	
	public Node(int data) {
		this.data = data;
		this.llink = null;
		this.rlink = null;
	}
}

public class Deque_1 {

	public static void main(String[] args) {
		DequeType deque = new DequeType();
		
		deque.add_head(10);
		deque.add_head(20);
		deque.add_head(30);
		
		System.out.println("삽입완료");
		deque.display();
		System.out.println();
		
		System.out.println("맨앞 삭제 : " + deque.delete_front());
		deque.display();
		System.out.println();
		System.out.println("맨뒤 삭제 : " + deque.delete_tail());
		deque.display();
		System.out.println();
		
		deque.add_tail(50);
		deque.add_tail(60);
		deque.add_tail(70);
		deque.add_head(1);
		
		System.out.println("삽입완료");
		deque.display();
		System.out.println();
		
		System.out.println("맨앞 삭제 : " + deque.delete_front());
		deque.display();
		System.out.println();
		System.out.println("맨뒤 삭제 : " + deque.delete_tail());
		deque.display();
		System.out.println();

	}

}

 

3. Deque 라이브러리 사용

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class Deque_a {

	public static void main(String[] args) {
		
		Deque<Integer> LinkedDeque  = new LinkedList<Integer>();
		Deque<Integer> ArrayDeque = new ArrayDeque<Integer>();
		
		// Add at the last 
		LinkedDeque.add(1); 
        // Add at the first 
		LinkedDeque.addFirst(2); 
        // Add at the last 
		LinkedDeque.addLast(3); 
        // Add at the first 
		LinkedDeque.push(4); 
        // Add at the last 
		LinkedDeque.offer(5); 
        // Add at the first 
		LinkedDeque.offerFirst(6); 
        System.out.println(LinkedDeque + "\n"); 
  
        LinkedDeque.removeFirst(); 
        LinkedDeque.removeLast(); 
        System.out.println(LinkedDeque); 
        
		ArrayDeque.add(1); 
		ArrayDeque.addFirst(2); 
		ArrayDeque.addLast(3); 
		System.out.println(ArrayDeque);
        System.out.println(ArrayDeque.pop()); 
        System.out.println(ArrayDeque.poll()); 
        System.out.println(ArrayDeque.pollFirst()); 
        System.out.println(ArrayDeque.pollLast());
	}
}

---

라이브러리를 이용한 덱은 문서를 자세히 다시 봐야겠다.