덱

Deck (덱)

덱(Deque)은 Double Ended Queue의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 스택과 큐의 특성을 모두 가지고 있습니다.

핵심 요소

메서드	설명
addFirst()	덱의 앞쪽에 요소 추가
addLast()	덱의 뒤쪽에 요소 추가
removeFirst()	덱의 앞쪽 요소 제거
removeLast()	덱의 뒤쪽 요소 제거
getFirst()	덱의 앞쪽 요소 조회
getLast()	덱의 뒤쪽 요소 조회

Java 직접 구현 예시

public class Deque<T> {
    private class Node {
        T data;
        Node prev;
        Node next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    private Node front;
    private Node rear;
    private int size;
    
    public void addFirst(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            newNode.next = front;
            front.prev = newNode;
            front = newNode;
        }
        size++;
    }
    
    public void addLast(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            newNode.prev = rear;
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}
Java
복사

Java Collections Framework 사용 예시

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

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        
        // 요소 추가
        deque.addFirst("First");
        deque.addLast("Last");
        
        // 앞쪽에서 요소 확인
        System.out.println(deque.getFirst()); // "First" 출력
        
        // 뒤쪽에서 요소 확인
        System.out.println(deque.getLast());  // "Last" 출력
        
        // 요소 제거
        deque.removeFirst();
        deque.removeLast();
        
        // 비어있는지 확인
        System.out.println(deque.isEmpty());  // true 출력
    }
}
Java
복사