[자료구조] 백준 10866 덱

10866번: 덱

https://www.acmicpc.net/problem/10866

 

# 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // ArrayDeque 를 이용해 덱 구현
        ArrayDeque<Long> deque = new ArrayDeque<>();

        // 명령의 수 N
        long n = Long.parseLong(br.readLine());

        for (long i = 0; i < n; i++) {
            // 문자열 분리를 위한 StringTokenizer
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            // 각 라인의 첫 번째 토큰을 가져옴
            String token = st.nextToken();

            switch (token) {
                case "push_front":
                    deque.offerFirst(Long.parseLong(st.nextToken()));
                    break;
                case "push_back":
                    deque.offerLast(Long.parseLong(st.nextToken()));
                    break;
                case "pop_front":
                    if (deque.size() == 0) {
                        bw.write(String.valueOf(-1) + "\n");
                    } else {
                        bw.write(String.valueOf(deque.pollFirst()) + "\n");
                    }
                    break;
                case "pop_back":
                    if (deque.size() == 0) {
                        bw.write(String.valueOf(-1) + "\n");
                    } else {
                        bw.write(String.valueOf(deque.pollLast()) + "\n");
                    }
                    break;
                case "size":
                    bw.write(String.valueOf(deque.size()) + "\n");
                    break;
                case "empty":
                    if (deque.size() == 0) {
                        bw.write(String.valueOf(1) + "\n");
                    } else {
                        bw.write(String.valueOf(0) + "\n");
                    }
                    break;
                case "front":
                    if (deque.size() == 0) {
                        bw.write(String.valueOf(-1) + "\n");
                    } else {
                        bw.write(String.valueOf(deque.peekFirst()) + "\n");
                    }
                    break;
                case "back":
                    if (deque.size() == 0) {
                        bw.write(String.valueOf(-1) + "\n");
                    } else {
                        bw.write(String.valueOf(deque.peekLast()) + "\n");
                    }
                    break;
            }
        }

        // Reader 버퍼 닫기
        br.close();

        // Writer 버퍼 비운 뒤 닫기
        bw.flush();
        bw.close();
    }
}

• Deque (덱) : 한쪽에서만 요소의 삽입/삭제가 이루어지는 queue와 달리 양쪽 모두에서 요소를 삽입/삭제 할 수 있다.
• ArrayDeque를 이용해 구현할 수 있으며, 배열의 특성을 가지고 있다.
• ArrayDeque는 LinkedList를 사용하는 것과 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다고 한다.

 

다음은 ArrayDeque 를 사용해 덱을 구현했을 때 사용할 수 있는 주요 메소드이다.

• offerFirst() : 덱의 맨 앞에 요소를 추가
• offerLast() : 덱의 맨 뒤에 요소를 추가
• pollFirst() : 덱의 맨 앞 요소를 제거하고 반환 (덱이 비어있을 경우 null 반환)
• pollLast() : 덱의 맨 뒤 요소를 제거하고 반환 (덱이 비어있을 경우 null 반환)
• peekFirst() : 덱의 맨 앞 요소를 반환만 하고 제거하지는 않음 (덱이 비어있을 경우 null 반환)
• peekLast() : 덱의 맨 뒤 요소를 반환만 하고 제거하지는 않음 (덱이 비어있을 경우 null 반환)

 

추가로 사용할 수 있는 비슷한 메소드이다. 실행 실패 시 offer, poll, peek 은 null을 반환하고, add, remove, get은 예외를 발생시킨다는 차이가 있다.

• offer - add
• poll - remove
• peek - get