[자료구조] 스택

스택 (Stack) 이란?

• 마지막에 들어온 데이터가 먼저나가는 후입선출 자료구조 (LIFO)

• 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용

스택의 연산

• push() : 스택의 가장 윗부분에 추가한다.

• pop() : 스택에서 가장 윗부분에 있는 항목을 제거한다.

• peek() : 스택의 가장 위에 있는 항목을 출력 및 반환한다.

• isEmpty() : 스택이 비어 있을 경우, true를 반환한다.

위 메서드 뿐만 아니라, contains(), size(), empty()도 사용 가능하다.

스택의 구현

아래와 같은 과정으로 직접 push, pop, peek, contains 등 사용해보며 결과를 확인해 볼 수 있다.

스택의 경우, 괄호 짝을 검사하거나 후위표기법 연산에서 주로 활용할 수 있다.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();

        stack.push(1);
        stack.push(2);
    
        System.out.println(stack.pop());
        System.out.println(stack);

        System.out.println(stack.peek());
        System.out.println(stack);

        System.out.println(stack.contains(1));
        System.out.println(stack.size());
        System.out.println(stack.empty());

        stack.clear();
        System.out.println(stack);
        System.out.println(stack.pop());
    }
}

스택의 활용

후위 표기법은 연산자가 피연산자들 뒤에 위치한 경우이다.

컴퓨터에서 수식 계산 순서는 중위 표기식에서 후위표기식으로 걸쳐서 계산한다.

1. 수식에서 피연산자가 나오면 무조건 스택에 저장하기

2. 연산자가 나오면 스택에서 피연산자 두 개 꺼내서 연산하고, 결과값을 다시 스택에 저장하기

3. 마지막에는 최종 계산결과만 스택에 남는다.

EX 1) 2 2 + = 4
EX 2) 2 2 - =0

import java.util.Stack;

public class Practice {
    public static double calculate(String string) {
        Stack<Double> stack = new Stack<Double>();

        for (String str: string.split(" ")) {
            if (str.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (str.equals("-")) {
                stack.push(- stack.pop() + stack.pop());
            } else if (str.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (str.equals("/")) {
                stack.push(1 / stack.pop() * stack.pop());
            } else {
                stack.push(Double.parseDouble(str));
            }
        }
        return stack.pop();
    }
 }