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

[알고리즘/백준] 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("

"); } else if (command.equals("size")) { sb.append(queue.size()).append("

"); } else if (command.equals("empty")) { sb.append(queue.empty()).append("

"); } else if (command.equals("front")) { sb.append(queue.front()).append("

"); } else if (command.equals("back")) { sb.append(queue.back()).append("

"); } } System.out.println(sb); } }

728x90

from http://developer-hm.tistory.com/181 by ccl(A) rewrite - 2021-10-04 16:27:34