출처

---

Deque 는 양방향으로 삽입, 삭제가 가능한 자료구조이다.

Java에서 Deque는 인터페이스로 선언되어 있으며 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스로 구현되어 있다.

양방향으로 offer 연산을 해서 값을 추가할 수 있다

양방향으로 poll 연산을 해서 값을 꺼낼 수 있다

양방향으로 peek 연산을 해서 값을 확인할 수 있다

예시 코드

        Deque<Integer> deque = new LinkedList<>();
        
        deque.offerLast(2);
        deque.offerFirst(2);
        
        deque.peekFirst();
        deque.peekLast();

        deque.peekFirst();
        deque.peekLast();

다음과 같이 LinkedList로 선언하고 Deque 인터페이스의 메서드들을 활용할 수 있다.

예시 문제

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        Deque<Integer> d = new LinkedList<>();
        for (int i=1; i<=num; i++){
            d.offerLast(i);
        }
        while (d.size()!=1){
            d.pollFirst();
            d.offerLast(d.pollFirst());
        }
        System.out.println(d.poll());
    }
}

양방향으로 삽입, 삭제가 필요한 백준 2164번을 다음과 같이 dequeue를 활용해 풀 수 있다.