덱(Deque) 이란?

• Deque는 Double-ended queue의 줄임말로 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산 모두 지원한다.
  • 앞쪽, 뒤쪽 모두 삽입과 삭제가 가능한 큐
• 덱이 수용할 수 있는 크기를 넘어가는 삽입 연산을 수행 ⇒ 오버플로우 발생
• 비어있는 덱에서 삭제 연산을 수행 ⇒ 언더플로우 발생

자바에서 덱 선언, 사용

• 덱은 인터페이스로 구현되어있다. 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.
• LinkedList로 덱을 선언할 경우 크기를 미리 설정할 수 없다.

제출 결과

1. 실패(시간 초과)

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

public class Q10866 {
    public static void main(String[] args) throws IOException {
				Scanner scan = new Scanner(System.in);
        int size = Integer.parseInt(scan.nextLine());
        Deque<String> que = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            String[] order = scan.nextLine().split(" ");
            switch (order[0]) {
                case "push_front":
                    que.addFirst(order[1]);
                    break;
                case "push_back":
                    que.addLast(order[1]);
                    break;
                case "pop_front":
                    System.out.println((que.isEmpty()) ? -1 : que.pollFirst());
                    break;
                case "pop_back":
                    System.out.println((que.isEmpty()) ? -1 : que.pollLast());
                    break;
                case "size":
                    System.out.println(que.size());
                    break;
                case "empty":
                    System.out.println((que.isEmpty()) ? 1 : 0);
                    break;
                case "front":
                    System.out.println((que.isEmpty()) ? -1 : que.getFirst());
                    break;
                case "back":
                    System.out.println((que.isEmpty()) ? -1 : que.getLast());
                    break;
            }
        }
    }
}

2. 성공

• Scanner → BufferReader 로 변경하여 시간 단축
• String[] order → StringTokenizer st.nextToken() 로 변경
  • StringTokenizer : 구분자를 지정하지 않으면 스페이스, 탭, 줄바꿈 등이 기본 구분자로 적용된다.
  • 정규 표현식을 사용하지 않는 경우 이용이 가능하며 빠른 속도로 사용하기 편리하다.
  • “문자열”.split(” “)을 사용하지 않아도 된다. → 속도가 느림

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

public class Q10866 {
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(st.nextToken());
        Deque<String> que = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            switch (st.nextToken()) {
                case "push_front":
                    que.addFirst(st.nextToken());
                    break;
                case "push_back":
                    que.addLast(st.nextToken());
                    break;
                case "pop_front":
                    System.out.println((que.isEmpty()) ? -1 : que.pollFirst());
                    break;
                case "pop_back":
                    System.out.println((que.isEmpty()) ? -1 : que.pollLast());
                    break;
                case "size":
                    System.out.println(que.size());
                    break;
                case "empty":
                    System.out.println((que.isEmpty()) ? 1 : 0);
                    break;
                case "front":
                    System.out.println((que.isEmpty()) ? -1 : que.getFirst());
                    break;
                case "back":
                    System.out.println((que.isEmpty()) ? -1 : que.getLast());
                    break;
            }
        }
    }
}