백준 18258 큐 2 Java: 배열로 Queue 직접 구현하기

백준 18258번 ‘큐 2’는 push, pop, size, empty, front, back 명령을 처리하는 문제다. Java의 ArrayDeque를 써도 되지만, 원문에서 배열과 list 중 무엇으로 직접 구현할지 고민했던 흐름을 살려 이번에는 head와 tail index를 가진 배열 queue로 정리했다.

• 백준 18258번 큐 2

Queue 상태를 두 index로 표현한다

명령 수가 N이면 실제로 저장되는 값도 최대 N개다. 크기 N의 배열을 만들고 다음처럼 관리한다.

• head: 다음에 꺼낼 원소의 index
• tail: 다음 원소를 넣을 index
• 현재 원소 수: tail - head
• 비어 있음: head == tail

push는 values[tail++]에 저장하고, pop은 비어 있지 않을 때 values[head++]를 반환한다. 이미 꺼낸 앞부분을 다시 쓰지 않지만 명령 전체에서 push 수가 배열 크기를 넘지 않으므로 circular queue가 필요하지 않다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static class IntQueue {
        private final int[] values;
        private int head;
        private int tail;

        private IntQueue(int capacity) {
            values = new int[capacity];
        }

        private void push(int value) {
            values[tail++] = value;
        }

        private int pop() {
            return isEmpty() ? -1 : values[head++];
        }

        private int size() {
            return tail - head;
        }

        private boolean isEmpty() {
            return head == tail;
        }

        private int front() {
            return isEmpty() ? -1 : values[head];
        }

        private int back() {
            return isEmpty() ? -1 : values[tail - 1];
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int commandCount = Integer.parseInt(reader.readLine());
        IntQueue queue = new IntQueue(commandCount);
        StringBuilder output = new StringBuilder();

        for (int command = 0; command < commandCount; command++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );

            switch (tokenizer.nextToken()) {
                case "push" -> queue.push(
                        Integer.parseInt(tokenizer.nextToken())
                );
                case "pop" -> output.append(queue.pop()).append('\n');
                case "size" -> output.append(queue.size()).append('\n');
                case "empty" -> output.append(
                        queue.isEmpty() ? 1 : 0
                ).append('\n');
                case "front" -> output.append(queue.front()).append('\n');
                case "back" -> output.append(queue.back()).append('\n');
                default -> throw new IllegalArgumentException(
                        "지원하지 않는 명령입니다."
                );
            }
        }

        System.out.print(output);
    }
}

위 switch expression 형태는 비교적 최근 Java syntax다. 제출 환경의 Java version이 낮다면 기존 case "push": ... break; 형태로 바꾸면 된다.

ArrayList를 queue처럼 사용할 때의 주의점

원문은 ArrayList<Integer>에 값을 계속 append하고 firstIndex만 증가시켰다. 앞 원소를 remove(0)하지 않아 각 pop이 O(1)인 점은 좋지만, 이미 꺼낸 boxed Integer가 list 안에 그대로 남고 전체 command 수만큼 object가 쌓인다.

직접 구현할 목적이라면 primitive int[]가 boxing 없이 필요한 용량만 사용한다. 실무 code에서는 직접 queue를 만들기보다 Java 표준 ArrayDeque를 우선 검토하는 편이 유지보수에 낫다. 이 글은 queue의 index invariant를 확인하는 학습 풀이로 보는 것이 맞다.

원문의 작은 초기화 오류

원문 constructor에는 lastIdx를 두 번 0으로 대입하고 firstIdx를 명시적으로 초기화하지 않았다. Java field의 기본값이 0이라 실행 결과에는 문제가 없지만, 서로 다른 두 상태를 초기화하려던 의도가 흐려진다. 새 구현에서는 field 기본값을 이용하되 이름을 head, tail로 바꿔 역할을 드러냈다.

모든 명령은 O(1), 전체 시간은 O(N), 배열 공간은 O(N)이다. 표준 deque로 같은 명령을 처리하는 version은 백준 18258 ArrayDeque 풀이에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 빈 queue의 모든 조회, push-pop 반복, duplicate와 negative value, capacity만큼 push하는 command sequence를 배열 shift 없는 reference queue와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.