Deque(덱)은 스택(Stack)과 큐(Queue)의 장점을 모두 결합한 유연한 자료구조로 (Deque: Double-Ended Queue) 덱은 이름 그대로 ‘양방향’에서 삽입과 삭제가 가능한 자료구조이다.
스택인 “Last In First Out (LIFO)” 방식으로 한쪽(보통 top)에서만 데이터를 넣고 뺄 수 있다. 큐는 “First In First Out (FIFO)” 방식으로 한쪽(rear)에서 데이터를 넣고 다른 한쪽(front)에서 데이터를 뺄 수 있다
반면, 덱은 이러한 제약 없이 데이터의 삽입과 제거를 양쪽 끝(head와 tail)에서 모두 자유롭게 수행할 수 있는 자료구조이다. 이러한 유연성 덕분에 덱 하나로 스택과 큐의 기능을 모두 구현할 수 있다
덱의 주요 특징
- 양방향 접근: head와 tail 모두에서 삽입(addFirst, addLast)과 삭제(removeFirst, removeLast)가 가능하다
- 스택/큐 구현 가능
- 스택: addFirst와 removeFirst (또는 addLast와 removeLast)를 사용하면 스택처럼 동작한다
- 큐: addLast와 removeFirst (또는 addFirst와 removeLast)를 사용하면 큐처럼 동작한다
덱(Deque)과 추상 자료형(ADT)
- printAll(): 덱의 모든 요소를 순서대로 출력한다
- addFirst(data): 덱의 head 부분에 데이터를 삽입한다
- removeFirst(): 덱의 head 부분에서 데이터를 제거하고 반환한다
- addLast(data): 덱의 tail 부분에 데이터를 삽입한다
- removeLast(): 덱의 tail 부분에서 데이터를 제거하고 반환한다
- isEmpty(): 덱이 비어있는지 여부를 확인하여 true 또는 false를 반환한다
이중 연결 리스트(DoublyLinkedList)를 이용한 해시 테이블 구현
Deque 클래스
/**
* 이중 연결 리스트를 기반으로 구현된 Deque (Double-Ended Queue) 클래스
* 양쪽 끝에서 O(1) 시간 복잡도로 삽입 및 삭제를 지원한다
*/
public class Deque<T> {
private DoublyLinkedList<T> list; // 내부적으로 DoublyLinkedList를 사용
public Deque() {
this.list = new DoublyLinkedList<>(); // 덱 생성 시 빈 이중 연결 리스트로 초기화
}
/**
* 덱의 모든 요소를 순서대로 출력한다
* 내부 DoublyLinkedList의 printAll() 메소드를 호출한다
*/
public void printAll() {
this.list.printAll();
}
/**
* 덱의 head 부분에 데이터를 삽입한다
* DoublyLinkedList의 insertAt(0, data)를 사용하여 O(1) 시간 복잡도로 동작한다
* @param data 삽입할 데이터
*/
public void addFirst(T data) {
this.list.insertAt(0, data);
}
/**
* 덱의 head 부분에서 데이터를 제거하고 반환한다
* DoublyLinkedList의 deleteAt(0)를 사용하여 O(1) 시간 복잡도로 동작한다
* @return 제거된 노드
* @throws IndexOutOfBoundsException 덱이 비어있을 경우
*/
public Node<T> removeFirst() {
return this.list.deleteAt(0);
}
/**
* 덱의 tail 부분에 데이터를 삽입한다
* DoublyLinkedList의 insertAt(size, data) 또는 insertLast(data)를 사용하여 O(1) 시간 복잡도로 동작한다
* @param data 삽입할 데이터
*/
public void addLast(T data) {
// DoublyLinkedList의 insertLast 메서드가 이미 O(1)로 구현되어 있으므로 이를 사용
this.list.insertLast(data);
// 또는 this.list.insertAt(this.list.getSize(), data);
}
/**
* 덱의 tail 부분에서 데이터를 제거하고 반환한다
* DoublyLinkedList의 deleteLast()를 사용하여 O(1) 시간 복잡도로 동작한다
* @return 제거된 노드
* @throws IndexOutOfBoundsException 덱이 비어있을 경우
*/
public Node<T> removeLast() {
return this.list.deleteLast();
}
/**
* 덱이 비어있는지 여부를 확인한다
* @return 덱이 비어있으면 true, 그렇지 않으면 false
*/
public boolean isEmpty() {
return (this.list.getSize() == 0);
}
}
DequeMain
public class DequeMain {
public static void main(String[] args) {
Deque<Integer> deque = new Deque<>();
System.out.println("===== addFirst =====");
System.out.println("isEmpty: " + deque.isEmpty()); // isEmpty: true
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
deque.addFirst(4);
deque.addFirst(5);
deque.printAll(); // [5, 4, 3, 2, 1]
System.out.println("isEmpty: " + deque.isEmpty()); // isEmpty: false
System.out.println("\n");
System.out.println("===== removeFirst =====");
Node removedNode1 = deque.removeFirst();
System.out.println("Removed: " + removedNode1.getData()); // Removed: 5
deque.printAll(); // [4, 3, 2, 1]
Node removedNode2 = deque.removeFirst();
System.out.println("Removed: " + removedNode2.getData()); // Removed: 4
deque.printAll(); // [3, 2, 1]
Node removedNode3 = deque.removeFirst();
System.out.println("Removed: " + removedNode3.getData()); // Removed: 3
deque.printAll(); // [2, 1]
Node removedNode4 = deque.removeFirst();
System.out.println("Removed: " + removedNode4.getData()); // Removed: 2
deque.printAll(); // [1]
Node removedNode5 = deque.removeFirst();
System.out.println("Removed: " + removedNode5.getData()); // Removed: 1
deque.printAll(); // []
System.out.println("isEmpty: " + deque.isEmpty()); // isEmpty: true
System.out.println("\n");
System.out.println("===== addLast =====");
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
deque.addLast(4);
deque.addLast(5);
deque.printAll(); // [1, 2, 3, 4, 5]
System.out.println("isEmpty: " + deque.isEmpty()); // isEmpty: false
System.out.println("\n");
System.out.println("===== removeLast =====");
Node removedNode6 = deque.removeLast();
System.out.println("Removed: " + removedNode6.getData()); // Removed: 5
deque.printAll(); // [1, 2, 3, 4]
Node removedNode7 = deque.removeLast();
System.out.println("Removed: " + removedNode7.getData()); // Removed: 4
deque.printAll(); // [1, 2, 3]
Node removedNode8 = deque.removeLast();
System.out.println("Removed: " + removedNode8.getData()); // Removed: 3
deque.printAll(); // [1, 2]
Node removedNode9 = deque.removeLast();
System.out.println("Removed: " + removedNode9.getData()); // Removed: 2
deque.printAll(); // [1]
Node removedNode10 = deque.removeLast();
System.out.println("Removed: " + removedNode10.getData()); // Removed: 1
deque.printAll(); // []
System.out.println("isEmpty: " + deque.isEmpty()); // isEmpty: true
System.out.println("\n");
// 추가 테스트: 큐처럼 사용
System.out.println("===== Deque as Queue (addLast, removeFirst) =====");
deque.addLast(10);
deque.addLast(20);
deque.addLast(30);
deque.printAll(); // [10, 20, 30]
System.out.println("Removed (Queue-like): " + deque.removeFirst().getData()); // Removed: 10
deque.printAll(); // [20, 30]
System.out.println("\n");
// 추가 테스트: 스택처럼 사용
System.out.println("===== Deque as Stack (addFirst, removeFirst) =====");
deque = new Deque(); // 새 덱 생성
deque.addFirst(100);
deque.addFirst(200);
deque.addFirst(300);
deque.printAll(); // [300, 200, 100]
System.out.println("Removed (Stack-like): " + deque.removeFirst().getData()); // Removed: 300
deque.printAll(); // [200, 100]
System.out.println("\n");
}
}