8-3: 큐 구현하기

큐 구현하기

 

문제

---

이 문제에서는 큐를 구현한다. 큐는 다음 세 개의 연산을 지원한다. Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다. Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다. Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다. 크기가 n인 큐에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”, Top은 “3”으로 표현한다. 다음은 크기 4인 큐에 10개의 연산이 입력으로 주어졌을 때의 입력과 출력의 예이다. 참고로, 다음 예제는 선형 큐의 대표적인 나쁜 예이다. 다음 예제때문에 선형 큐는 쓰이지 않는다.

XYZ

 

입력

---

첫째 줄에 큐의 크기 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

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

public class QueueImpl {

    /**
     *
     * 문제:
     *
     * 이 문제에서는 큐 구현한다. 스택은 다음 세 개의 연산을 지원한다.
     * Push X : 스택에 정수 X를 push한다. 만약 스택이 꽉 차서 push를 할 수 없다면, “Overflow”를 출력한다.
     * Pop : 스택에서 정수 하나를 pop한다. 만약 스택이 비어있어서 pop을 할 수 없다면, “Underflow”를 출력한다.
     * Top : 스택의 top에 있는 정수를 출력한다. 만약 스택이 비어있다면 “NULL”을 출력한다.
     *
     * 크기가 n인 스택에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”, Top은 “3”으로 표현한다. 다음은 크기 4인 스택에 10개의 연산이 입력으로 주어졌을 때의 입력과 출력의 예이다.
     *
     * XYZ
     *
     * 입력:
     *
     * 첫째 줄에 스택의 크기 n, 연산의 개수 m이 주어진다. ( 1 <= n <= 100, 1 <= m <= 1,000 ) 두 번째 줄부터 연산이 주어진다. 1은 Push, 2는 Pop, 3은 Top 연산을 의미한다.
     *
     *
     * 출력:
     *
     * 연산의 결과를 출력한다.
     *
     *
     * 예제 입력:
     *
     * 4 10
     * 1 1
     * 1 2
     * 1 3
     * 2
     * 3
     * 1 4
     * 1 5
     * 3
     * 1 6
     * 3
     *
     *
     * 예제 출력:
     *
     * 2
     * 5
     * Overflow
     * 5
     *
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i=0; i<m; i++){
            String line = br.readLine();
            StringTokenizer opToken = new StringTokenizer(line);
            int op = Integer.parseInt(opToken.nextToken());
            if (op ==1){
                //get data info
                int data = Integer.parseInt(opToken.nextToken());
                //perform push.
                queue.enqueue(data);
            } else if (op ==2){
                //pop
                queue.dequeue();
            } else {
                //top
                queue.peek();
            }
        }
    }

    public static class Queue{
        int capacity;
        int[] data;
        int front=0, rear = 0;
        public Queue(int size){
            this.capacity = size;
            data = new int[capacity];
        }

        public void enqueue(int val){
            if (rear < capacity){
                //add to end of list.
                data[rear] = val;
//                System.out.println("Added " + val);
                rear++;
            } else{
                System.out.println("Overflow");
            }

        }

        public void dequeue(){
            if (getSize() > 0){
                int elem = data[front];
//                System.out.println("Removed " + elem);
                front++;
            } else {
                System.out.println("Underflow");
            }
        }

        private int getSize(){
            return rear - front;
        }

        public void peek(){
            if (getSize() > 0){
                System.out.println(String.valueOf(data[front]));
            } else {
                System.out.println("NULL");
            }
        }
    }
}