문제
정수를 저장하는 큐를 직접 구현하고, push, pop, size, empty, front, back 6가지 명령을 처리하는 프로그램을 작성하라.
입력
첫째 줄에 명령 수 N (1 이상 10,000 이하)이 주어진다. 이후 N줄에 명령이 하나씩 주어진다. 정수는 1 이상 100,000 이하이다.
출력
출력이 필요한 명령마다 한 줄에 하나씩 결과를 출력한다. 큐가 비어있을 때 pop, front, back은 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
15 push 1 push 2 front back size empty pop pop pop size empty pop push 3 empty front | 1 2 2 0 1 2 -1 0 1 -1 0 3 |
풀이
배열 기반 원형 큐를 직접 구현하여 6가지 명령을 처리한다.
- 내부 클래스 Queue를 정의하고, 배열과 front/rear/size 포인터를 관리한다
- push: rear 위치에 값을 넣고 rear를 증가시킨다 (배열 끝에 도달하면 0으로 순환)
- pop: front가 rear와 같으면 -1, 아니면 front 위치 값을 반환하고 front를 증가시킨다
- front/back: 비어있으면 -1, 아니면 해당 위치의 값을 반환한다
- 명령 문자열을 파싱하여 각 명령에 맞는 메서드를 호출한다
핵심 아이디어: Java의 내장 Queue를 사용하지 않고 배열로 원형 큐를 직접 구현하여 자료구조의 동작 원리를 학습하는 문제이다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day23BOJ10845큐 { // 10845 큐
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
Queue q = new Queue(n);
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("push")) {
int x = Integer.parseInt(st.nextToken());
q.push(x);
} else if (cmd.equals("pop")) {
sb.append(q.pop()).append("\n");
} else if (cmd.equals("size")) {
sb.append(q.size()).append("\n");
} else if (cmd.equals("empty")) {
sb.append(q.empty()).append("\n");
} else if (cmd.equals("front")) {
sb.append(q.front()).append("\n");
} else if (cmd.equals("back")) {
sb.append(q.back()).append("\n");
}
}
System.out.println(sb);
}
static class Queue {
private int[] arr;
private int size = 0;
private int front = 0;
private int rear = 0;
public Queue(int n) {
arr = new int[n];
}
public void push(int x) {
arr[rear++] = x;
if (rear >= arr.length) {
rear = 0;
}
size++;
}
public int pop() {
if (rear == front) {
return -1;
}
int data = arr[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;
}
if (rear == 0) {
return arr[arr.length - 1];
} else {
return arr[rear - 1];
}
}
}
}복잡도
- 시간: O(N)
- 공간: O(N)