[JAVA] 백준 알고리즘 10845번 (큐)

문제

---

이번에 다뤄볼 문제는 10845번 문제 '큐'입니다.

 

지난 게시물에 이어 이번엔 기본적인 자료구조인 큐에 대해 알아보는 시간을 가져보겠습니다. 이미 앞선 문제들에서 큐를 활용하여 문제를 해결한 경우들도 많이 있지만 잘 모르시는 분들을 위해 정확히 짚고 넘어가겠습니다.

 

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말합니다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 일상생활에서 흔히 사용하는 선착순 구조라고 생각하면 됩니다.

 

문제에서는 큐를 활용하여 6가지 기능(메서드)를 입력받고 그에 맞는 행동을 하길 바라고 있습니다. 구현해야하는 메서드는 아래와 같습니다.

 

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

 

이 문제를 해결하기 위해 java에서 기본적으로 제공하는 java.util.Queue을 사용해도 무방합니다. 다만, java util.Queue에서 사용하는 메서드명과 문제에서 구현하길 바라는 메서드명이 다르니 그것만 주의해서 사용해주시면 됩니다. 우리는 문제를 통해 큐를 공부하는 것이 목적이기 때문에 직접 Queue 클래스를 구현하는 방식으로 풀이해보겠습니다.

 

아래 해답 코드를 볼때 front, back이라는 변수를 어떻게 활용하여 배열을 큐처럼 사용하는지 집중해서 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.Scanner;

class Queue {
    private int front; // 큐의 가장 앞
    private int back; // 큐의 가장 뒤
    private final int[] queue;

    // 큐 생성자
    public Queue(int size) {
        this.front = 0;
        this.back = -1;
        this.queue = new int[size];
    }

    public void push(int p) {
        this.queue[++back] = p;
    }

    public int pop() {
        if (empty()) {
            return -1;
        } else {
            return queue[front++];
        }
    }

    public int size() {
        return back - front + 1;
    }

    public boolean empty() {
        return size() == 0;
    }

    public int front() {
        if (empty()) {
            return -1;
        } else {
            return queue[front];
        }
    }

    public int back() {
        if (empty()) {
            return -1;
        } else {
            return queue[back];
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int n = sc.nextInt();
        Queue queue = new Queue(n);

        while(n --> 0) {
            String command = sc.next();

            switch (command) {
                case "push":
                    queue.push(sc.nextInt());
                    break;
                case "pop":
                    sb.append(queue.pop()).append("\n");
                    break;
                case "size":
                    sb.append(queue.size()).append("\n");
                    break;
                case "empty":
                    sb.append(queue.empty() ? 1 : 0).append("\n");
                    break;
                case "front":
                    sb.append(queue.front()).append("\n");
                    break;
                case "back":
                    sb.append(queue.back()).append("\n");
                    break;
                default:
                    break;
            }
        }
        System.out.println(sb);
    }
}

 

10845번: 큐