[자료구조] 덱(Deque)

1. 덱(Deque)이란?

Double-Ended Queue의 줄임말이다.
Double, 양방향으로 자료를 넣고 뺄 수 있는 자료구조이다.
즉, 덱은 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있는 자료구조로 설명된다.

2. 덱(Deque)의 특징

양방향으로 삽입과 삭제가 가능한 장점이 있으며, 이러한 장점을 바탕으로 'DFS,BFS 알고리즘'이나 '슬라이딩 윈도우 알고리즘' 문제에서 유용하게 사용된다.

3. 덱(Deque)의 메서드

3-1. 덱의 주요 메서드

(1) 삽입

• addFirst() : 덱의 앞쪽에 데이터 삽입
  (Inserts the specified element at the front of this deque)
• addLast() : 덱의 뒤쪽에 데이터 삽입
  (Inserts the specified element at the end of this deque)

삽입 메서드 offerFirst(), offerLast()
삽입 메서드에는 add외에도 offer이라는 메서드가 존재한다. add와 offer 둘 다 데이터를 삽입한다는 공통점이 있지만, offer은 add와 달리 삽입에 실패하는 경우 false를 반환한다는 차이가 있다.

(2) 삭제

• pollFirst() : 덱의 앞에 있는 데이터를 삭제하고 값을 return
  (Retrieves and removes the first element of this deque,or returns null if this deque is empty)
  
  
• pollLast() : 덱의 뒤에 있는 데이터를 삭제하고 값을 return
  (Retrieves and removes the last element of this deque,or returns null if this deque is empty)

삭제 메서드 removeFirst(), removeLast()
삭제 메서드에는 poll외에도 remove 메서드도 존재한다.
remove는 덱이 null일 경우 예외를 발생시키지만, poll은 null을 return한다.

(3) 조회

• peekFirst() : 덱의 앞에 있는 데이터를 return
  (Retrieves, but does not remove, the first element of this deque,or returns null if this deque is empty.)
  
  
• peekLast() : 덱의 뒤에 있는 데이터를 return
  (Retrieves, but does not remove, the last element of this deque,or returns null if this deque is empty.)

조회 메서드 getFirst(), getLast()
조회 메서드는 peek과 get메서드가 존재한다. get과 peek모두 값을 조회해서 return한다는 공통점이 있지만, 덱이 null일 경우 차이점이 발생한다. get은 덱이 null일 경우 예외를 발생시키지만, peek은 null을 return한다.

3-2. 자바 코드

이 문제는 백준의 10866번 문제로, deque의 메소드를 파악하기 좋은 예제이다. 위에서 설명한 메서드와 isEmpty()(비어있는지 아닌지를 판단), size()(덱의 크기) 메소드들도 포함되어 있으니 덱의 메소드를 완벽하게 이해하고 싶다면 이 문제를 한 번 풀어보면 좋다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Deque<Integer> deque = new ArrayDeque<>();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i <N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command) {
                case "push_front":
                    deque.addFirst(Integer.parseInt(st.nextToken()));
                    break;
                case "push_back":
                    deque.addLast(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_front":
                    sb.append(deque.isEmpty()?-1:deque.pollFirst()).append("\n");
                    break;
                case "pop_back":
                    sb.append(deque.isEmpty()?-1:deque.pollLast()).append("\n");
                    break;
                case "size":
                    sb.append(deque.size()).append("\n");
                    break;
                case "empty":
                    sb.append(deque.isEmpty() ? 1 : 0).append("\n");
                    break;
                case "front":
                    sb.append(deque.isEmpty() ? -1 : deque.peekFirst()).append("\n");
                    break;
                case "back":
                    sb.append(deque.isEmpty() ? -1 : deque.peekLast()).append("\n");
                    break;
            }
        }
        System.out.print(sb);
    }
}