[필수 문제] 스택 구현하기

1. 문제

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

• Push X : 스택에 정수 X를 push한다. 만약 스택이 꽉 차서 push를 할 수 없다면, “Overflow”를 출력한다.
• Pop : 스택에서 정수 하나를 pop한다. 만약 스택이 비어있어서 pop을 할 수 없다면, “Underflow”를 출력한다.
• Top : 스택의 top에 있는 정수를 출력한다. 만약 스택이 비어있다면 “NULL”을 출력한다.

 

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

---

입력

첫째 줄에 스택의 크기 n, 연산의 개수 m이 주어진다. ( 1 <= n <= 100, 1 <= m <= 1,000 ) 두 번째 줄부터 연산이 주어진다. 1은 Push, 2는 Pop, 3은 Top 연산을 의미한다.  

출력

연산의 결과를 출력한다.

예제 입력

case 1)

4 10
1 1
1 2
1 3
2
3
1 4
1 5
3
1 6
3

 

case 2)

4 11
1 1
1 2
1 4
3
2
3
2
3
2
3
2

예제 출력

case 1)

2
5
Overflow
5

 

case 2)

4
2
1
NULL
Underflow

 

 

 

2. 풀이

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

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

interface Stack {
    boolean isEmpty();
    boolean isFull();
    boolean push(int item);
    boolean pop();
    String peek();
    void clear();
}

class ArrayStack implements Stack {

    private int top;
    private int stackSize;
    private int[] stackArr;

    public ArrayStack(int stackSize) {
        top = -1;
        this.stackSize = stackSize;
        stackArr = new int[stackSize];
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }

    @Override
    public boolean isFull() {
        return top == stackSize - 1;
    }

    @Override
    public boolean push(int item) {
        if(isFull()) return false; // Overflow
        else {
            stackArr[++top] = item;
            return true;
        }
    }

    @Override
    public boolean pop() {
        if(isEmpty()) return false; // Underflow
        else {
            top--;
            return true;
        }
    }

    @Override
    public String peek() {
        if(isEmpty()) return "NULL";
        else {
            return String.valueOf(stackArr[top]);
        }
    }

    @Override
    public void clear() {
        if(isEmpty()) return;
        else {
            top = -1;
            stackArr = new int[stackSize];
        }
    }
}

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());

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

            if(action == 1) {
                int item = Integer.parseInt(st.nextToken());
                if(!stack.push(item)) bw.write("Overflow\n");
            } else if(action == 2) {
                if(!stack.pop()) bw.write("Underflow\n");
            } else {
                bw.write(stack.peek() + "\n");
            }
        }
        
        br.close();
        bw.flush();
        bw.close();
    }

}