[자료구조] 데크 (Deque)

1. 데크 (Deque)

• 양쪽에서 삽입과 삭제가 모두 가능한 자료구조
  • Deque, Doubly-ended Queue
  • Stack과 Queue를 합친 형태

2. 데크 기본 구조

• 데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조
• 일부 기능을 제한하여 용도에 맞게 변형 가능
  

  

• add/remove vs offer/poll
  • add와 remove는 데이터가 없으면 예외를 발생시킴
  • offer과 poll은 데이터가 없으면 null이나 false를 반환하여 리턴 값을 받을 수 있음

3. 입력 제한 데크 (Scroll)

• 한 쪽의 입력을 제한한 데크
  

  

4. 출력 제한 데크 (Shelf)

• 한 쪽의 출력을 제한한 데크
  

  

5. 코드

Deque deque = new ArrayDeque();

// Front 부분 입력
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
System.out.println(deque); // [3, 2, 1]

// Rear 부분 입력
deque.addLast(10);
deque.addLast(20);
deque.addLast(30);
System.out.println(deque); // [3, 2, 1, 10, 20, 30]

// Front 부분 출력
System.out.println(deque.removeFirst()); // 3
System.out.println(deque); // [2, 1, 10, 20, 30]

// Rear 부분 출력
System.out.println(deque.removeLast()); // 30
System.out.println(deque); // [2, 1, 10, 20]

System.out.println(deque.removeLast()); // 20
System.out.println(deque.removeLast()); // 10
System.out.println(deque.removeLast()); // 1
System.out.println(deque.removeLast()); // 2
System.out.println(deque); // []

System.out.println(deque.pollLast()); // null
System.out.println(deque.removeLast()); // error