99클럽 코테 스터디 14일차 TIL - 큐

오늘의 문제

백준 - 10845번: 큐

문제내용과 풀이

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.

주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

내 풀이

12일차와 똑같은 유형인데, 스택에서 큐를 사용하는 것으로 바뀌었다.

Stack은 그 자체가 클래스여서 바로 인스턴스를 생성해 사용할 수 있지만, Queue는 인터페이스라 Queue 자체를 직접 사용할 수는 없다.

Queue를 구현한 클래스가 필요하고, 이에는 여러 클래스가 있지만 대표적으로 LinkedList나 ArrayDeque를 사용할 수 있다고 한다. 

Queue와 Deque은 무슨차이인지 알아봤는데, Queue는 보통 끝에서 삽입하고 앞에서 삭제하는 방식으로 동작하지만 Deque은 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 즉 Stack, Queue에 대해 모두 동작할 수 있다는 것이다.

LinkedList는 양방향 연결 리스트로 구현되어 있고, Queue, Deque 인터페이스를 모두 구현하며 Deque으로 Stack처럼 동작할 수도 있게 한다.

 

 

큐 (Queue) : FIFO (First In, First Out)이며, 먼저 들어온 요소가 먼저 나간다.

• offer() 또는 add() : 큐의 끝에 요소를 추가한다. (queue에 용량 제한 시 add는 초과하면 예외 발생, offer는 false 반환)
• poll() 또는 remove() : 큐의 앞에 있는 요소를 제거하고 반환한다. (큐가 비어있으면 null 또는 예외 발생 - remove)
• peek() 또는 element() : 큐의 앞에 있는 요소를 제거하지 않고 반환한다. (큐가 비어있으면 null 또는 예외 발생 - element)
• isEmpty() : 큐가 비어 있으면 true, 그렇지 않으면 false를 반환한다.
• size() : 큐에 들어있는 요소의 개수를 반환한다.
• front(): 큐의 맨 앞 요소를 반환한다. (큐가 비어있으면 null)
• back(): 큐의 맨 뒤 요소를 반환한다. (큐가 비어있으면 null)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> queue = new LinkedList<>();
        int last = -1;
        
        for (int i = 0; i < n; i++) {
            String command = br.readLine();

            if (command.startsWith("push")) {
                int x = Integer.parseInt(command.substring(5));
                queue.offer(x);
                last = x;
            } else if (command.equals("pop")) {
                if (queue.isEmpty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(queue.poll() + "\n");
                }
            } else if (command.equals("size")) {
                bw.write(queue.size() + "\n");
            } else if (command.equals("empty")) {
                bw.write((queue.isEmpty() ? 1 : 0) + "\n");
            } else if (command.equals("front")) {
                if (queue.isEmpty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(queue.peek() + "\n");
                }
            } else if (command.equals("back")) {
                if (queue.isEmpty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(last + "\n");
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}