[필수 문제] 큐 구현하기

1. 문제

이 문제에서는 큐를 구현한다. 큐는 다음 세 개의 연산을 지원한다.

• Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다.
• Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다.
• Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다.

크기가 n인 배열로 만든 큐에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”, Front는 “3”으로 표현한다.

---

입력

첫째 줄에 큐를 만들 수 있는 배열의 크기 n, 연산의 개수 m이 주어진다. ( 1 ≤ n ≤ 100, 1 ≤ m ≤ 1,000 ) 두 번째 줄부터 연산이 주어진다. 1은 Push, 2는 Pop, 3은 Front 연산을 의미한다. 

출력

연산의 결과를 출력한다.

예제 입력

4 15
1 1
1 2
1 3
3
2
2
3
1 4
1 5
3
2
2
1 6
2
3

예제 출력

1
3
Overflow
3
Overflow
Underflow
NULL

 

 

 

2. 풀이

Java에서 지원하는 Queue 자료형을 사용해도 되나, 직접 구현을 하면 다음과 같다.

import java.io.*;
import java.util.StringTokenizer;

interface Queue {
    boolean isEmpty();
    boolean isFull();
    boolean enqueue(int item);
    boolean dequeue();
    int peek();
}

class ArrayQueue implements Queue {

    private int front;
    private int rear;
    private int queueSize;
    private int[] queueArr;

    public ArrayQueue(int queueSize) {
        front = 0;
        rear = 0;
        this.queueSize = queueSize;
        queueArr = new int[queueSize];
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public boolean isFull() {
        return rear == queueSize - 1;
    }

    @Override
    public boolean enqueue(int item) {
        if(isFull()) return false; // Overflow
        else {
            queueArr[rear++] = item;
            return true;
        }
    }

    @Override
    public boolean dequeue() {
        if(isEmpty()) return false; // Underflow
        else {
            front++;
            return true;
        }
    }

    @Override
    public int peek() {
        if(isEmpty()) return -1;
        else return queueArr[front];
    }
}

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        ArrayQueue queue = new ArrayQueue(n+1);
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int action = Integer.parseInt(st.nextToken());

            if(action == 1) {
                if(!queue.enqueue(Integer.parseInt(st.nextToken()))) bw.write("Overflow\n");
            } else if(action == 2) {
                if(!queue.dequeue()) bw.write("Underflow\n");
            } else {
                if(queue.peek() == -1) bw.write("NULL\n");
                else bw.write(queue.peek() + "\n");
            }
        }

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

}