📝 문제 설명

정수를 저장하는 큐를 구현하고, 큐에서 사용 되는 5가지 커맨드를 구현하라.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

💡 아이디어

큐의 front와 back 연산을 위해서 (맨 앞/뒤 요소에 접근하는 연산) ArrayList보다 시간 복잡도면에서 효율적인 LinkedList를 사용했다.
스택 문제와 동일하게 공백이 포함되어있는 push X 커맨드에는 startsWith("push")를 사용하고, 나머지 명령어는 equals()로 정확히 비교하는 방식을 사용했다.
전체 반복문에 for 대신 while (N-- > 0)을 사용하여 가독성을 높였다.

🛠 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        LinkedList<Integer> queue = new LinkedList<>();

        while (N--> 0) {
            String command = br.readLine();

            // [1] push
            if (command.startsWith("push")) {
                int X = Integer.parseInt(command.split(" ")[1]);
                queue.add(X);
                
                // [2] pop
            } else if (command.equals("pop")) {
                if (!queue.isEmpty()) {
                    System.out.println(queue.getFirst());
                    queue.removeFirst();
                } else {
                    System.out.println(-1);
                }

                // [3] size
            } else if (command.equals("size")) {
                System.out.println(queue.size());

                // [4] empty
            } else if (command.equals("empty")) {
                System.out.println(queue.isEmpty() ? 1 : 0);
                
                // [5] front
            } else if (command.equals("front")) {
                if (!queue.isEmpty()) {
                    System.out.println(queue.getFirst());
                } else {
                    System.out.println(-1);
                }

                // [6] back
            } else if (command.equals("back")) {
                if (!queue.isEmpty()) {
                    System.out.println(queue.getLast());
                } else {
                    System.out.println(-1);
                }
            }


        }
    }
}

⏱ 시간복잡도

큐의 커맨드는 총 N개이며, 각 커맨드는 push, pop, size, empty, front, back 중 하나이다.
이때 사용한 LinkedList 내부 함수 addLast, removeFirst, getFirst, getLast 등의 시간 복잡도가 모두 O(1)이므로,
전체 연산의 시간 복잡도는 O(N)이다.

✏️ 느낀 점

스택을 구현할때도 LinkedList을 사용하는게 맞았던 것 같다. 구현-구조 상 이게 맞다.