[JAVA] 백준 알고리즘 10828번 (스택)

문제

---

이번에 다뤄볼 문제는 10828번 문제 '스택'입니다.

 

오늘은 가장 기본적인 자료구조인 스택에 대해 알아보는 시간을 가져보겠습니다. 이미 앞선 문제들에서 스택을 활용하여 문제를 해결한 경우들도 많이 있지만 잘 모르시는 분들을 위해 정확히 짚고 넘어가겠습니다.

 

스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있습니다. 자료를 넣는 것을 '밀어 넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸시한 자료부터 나오게 됩니다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 합니다.

 

쉬운 예로 헬스장에서 원하는 무게의 원판을 꺼내기 위해서는 그 위에 순서대로 쌓인 모든 원판을 차례로 꺼내야 하는 모습을 예로 들 수 있겠습니다.

 

문제에서는 스택이 제공하는 5가지 기능(메서드)를 입력받고 그에 맞는 행동을 하길 바라고 있으며

이 5가지 기능이 곧 스택의 기본 기능이라 생각하시면 되겠습니다.

 

5가지 기능은 아래와 같습니다.

스택에 데이터를 넣고(push) 빼고(pop)

스택이 비어있는지(empty) 아니라면 몇개의 자료가 들어있는지(size)

마지막으로 지금 스택에서 가장 위에 있는 자료는 무엇인지(top)

 

이 문제를 해결하기 위해 java에서 기본적으로 제공하는 java.util.Stack을 사용해도 무방합니다. 하지만 우리는 문제를 통해 스택을 공부하는 것이 목적이기 때문에 직접 Stack 클래스를 구현하는 방식으로 풀이해보겠습니다.

하나의 배열을 선언하고 이 배열을 스택처럼 사용하기 위해서 꼭 필요한 변수는 top변수 입니다. top은 스택의 꼭대기(제밀 마지막에 들어온)에 있는 자료의 위치(index)를 나타내는 용도라고 생각하면 됩니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.Scanner;

class Stack {
    private int top; // 스택에서 원소 위치를 나타내는 변수
    private final int[] stack;

    // 스택 생성자
    public Stack(int size) {
        this.top = -1;
        this.stack = new int[size];
    }

    public void push(int p) {
        this.stack[++top] = p;
    }

    public int pop() {
        if (top == -1) return -1;
        return this.stack[top--];
    }

    public int size() {
        return this.top + 1;
    }

    public int empty() {
        if (top == -1) return 1;
        return 0;
    }

    public int top() {
        if(top == -1) return -1;
        return this.stack[top];
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int n = sc.nextInt();
        Stack stack = new Stack(n);

        while(n --> 0) {
            String command = sc.next();

            switch (command) {
                case "push":
                    stack.push(sc.nextInt());
                    break;
                case "pop":
                    sb.append(stack.pop()).append("\n");
                    break;
                case "size":
                    sb.append(stack.size()).append("\n");
                    break;
                case "empty":
                    sb.append(stack.empty()).append("\n");
                    break;
                case "top":
                    sb.append(stack.top()).append("\n");
                    break;
                default:
                    break;
            }
        }
        System.out.println(sb);
    }
}

 

10828번: 스택