[알고리즘/백준] 10845 큐(자바, 링 버퍼)

문제

https://www.acmicpc.net/problem/10845

풀이 코드

• 링 버퍼를 사용하여 큐 구현
• 링 버퍼 : 배열의 처음과 끝이 논리적으로 연결되어 있는 자료구조. 첫번째 요소, 마지막 요소를 식별하기 위한 front, rear 변수 필요

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

public class Main {

    static class Queue {
        private int[] arr;
        private int size = 0;
        private int front = 0; //pop할 위치
        private int rear = 0; //push할 위치

        public Queue(int n) {
            arr = new int[n];
        }

        public void push(int x) {
            arr[rear++] = x;

            //배열의 앞뒤가 이어져 있는 구조이기 떄문에
            //큐의 rear가 배열의 끝에 도달하면 앞으로 돌아온다.
            if (rear >= arr.length) {
                rear = 0;
            }

            size++;
        }

        public int pop() {
            if (rear == front) {
                return -1;
            }

            int data = arr[front++];

            /*
            배열의 앞뒤가 이어져 있는 구조이기 떄문에
            큐의 front가 배열의 끝에 도달하면 앞으로 돌아온다.
             */
            if (front >= arr.length) {
                front = 0;
            }

            size--;

            return data;
        }

        public int size() {
            return size;
        }

        public int empty() {
            return size == 0 ? 1 : 0;
        }

        public int front() {
            if (size == 0) {
                return -1;
            }

            return arr[front];
        }

        public int back() {
            if (size == 0) {
                return -1;
            }

            /*
            rear의 경우 다음 push때 삽입될 위치를 가리키고 있기 때문에
            rear가 0일 경우 배열의 끝의 원소를 반환해야한다.
             */
            if (rear == 0) {
                return arr[arr.length-1];
            } else {
                return arr[rear-1];
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Queue queue = new Queue(n);

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            String command = st.nextToken();

            if (command.equals("push")) {
                int x = Integer.parseInt(st.nextToken());
                queue.push(x);
            } else if (command.equals("pop")) {
                sb.append(queue.pop()).append("\n");
            } else if (command.equals("size")) {
                sb.append(queue.size()).append("\n");
            } else if (command.equals("empty")) {
                sb.append(queue.empty()).append("\n");
            } else if (command.equals("front")) {
                sb.append(queue.front()).append("\n");
            } else if (command.equals("back")) {
                sb.append(queue.back()).append("\n");
            }
        }

        System.out.println(sb);
    }
}