Stack이란?

개념 정리

Stack은, 가장 대표적으로 순서가 보존되는 데이터 구조로, 아래와 같은 그림으로 직관적으로 표기될 수 있다.

그림에서 표현되듯이, 가장 나중에 들어온 데이터가 가장 먼저 나가게 되며 이를 LIFO (Last in Frist Out)이라고도 부른다.

주요 기능

가장 윗단을 가리키는 커서를 top이라고 부르며 값을 넣는 행위를 push(), top의 값을 꺼내는 행위를 pop(), top의 값을 확인하는 행위를 peek()으로 표현한다. Java에서는 java.util.Stack을 통해 표현되며 함수를 사용하는 방법도 위의 함수명과 동일하다.

public class myStackStudy {
    public static void main(String args[]){
        Stack stack = new Stack();
        System.out.println("== Push ==");
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("stack = " + stack);
        System.out.println("== Pop ==");
        System.out.println(stack.pop());
        System.out.println("stack = " + stack);
        System.out.println("== Peek ==");
        System.out.println(stack.peek());
        System.out.println("stack = " + stack);
        System.out.println("== Contains ==");
        System.out.println(stack.contains(1));
        System.out.println("== Size ==");
        System.out.println(stack.size());
        System.out.println("== Clear ==");
        stack.clear();
        System.out.println(stack.size());

    }
}

어디서 사용하는가?

Stack은 주로 최근 값의 데이터를 꺼내 쓸 때 사용하며, 컴퓨터의 "실행 취소"를 생각하면 이해하기 쉬울 것 같다.

예1. reverseString()

    public static String reverseString(String str){
        Stack stack = new Stack();
        String result = "";

        for (String s: str.split("")){
            stack.push(s);
        }

        while (!stack.isEmpty()){
            result = result + stack.pop();
        }
        return result;
    }

String을 반대로 뒤집는 함수로, 끝 값부터 꺼내온다는 점에서 Stack이 적합하다.

TIP) 문자열 -> 잘라서 저장하는 법

        // 방법1. split() 활용
        for (String s: str.split("")){
            stack.push(s);
        }
        
        // 방법2. toCharArray() 활용
        for (char c: str.toCharArray()){
        	stack.push(c);
        }

예2. 전위 / 중위 / 후위 표기식

public static double calculate(String string){
        Stack<Double> stack = new Stack();
        for (String s: string.split(" ")){
            if (s.equals(("+"))){
                stack.push(stack.pop() + stack.pop());
            } else if (s.equals("-")){
                stack.push(- stack.pop() + stack.pop());
            } else if (s.equals("*")){
                stack.push( stack.pop() * stack.pop());
            } else if (s.equals("/")){
                stack.push( 1/stack.pop() * stack.pop());
            } else {
                stack.push(Double.parseDouble(s));
            }
        }
        return stack.pop();
    }

전위, 중위, 후위 표기식의 예시로, 연산을 만나면 2개의 값을 pop()하고, 그 외에는 push()를 하는 방법에 주목하자.