스택(Stack)

1. 스택(Stack)이란?

- 스택은 데이터를 저장하는 자료구조 중 하나로 마지막에 추가된 데이터가 가장 먼저 꺼내지는 후입선출(LIFO: Last In First Out) 방식을 사용한다.

- 주로 괄호검사, 후위표기식, 재귀, 백트래킹 등의 알고리즘에 활용된다.

- 자바에서는 Vector를 상속받아 구현되어 있으므로 동기화 등에서 불필요한 오버헤드가 발생할 수 있어 Deque 인터페이스를 사용하는 ArrayDeque를 스택처럼 사용할 수도 있다.

 

2. 주요 메소드

- push(E item): 스택의 가장 위에 요소를 추가한다.

Stack<String> stack = new Stack<>();

stack.push("Apple"); // 스택에 "Apple" 추가

 

- pop(): 스택의 가장 위에 있는 요소를 제거한다.

Stack<String> stack = new Stack<>();

stack.push("Apple");
stack.push("Banana");

stack.pop(); // 가장 위에 있는 "Banana"을 스택에서 제거

 

- peek(): 스택의 가장 위에 있는 요소를 제거하지 않고 조회한다.

Stack<String> stack = new Stack<>();

stack.push("Apple");
stack.push("Banana");

stack.peek(); // 가장 위에 있는 "Banana" 조회

 

- isEmpty(): 스택이 비어있는지 확인한다.

Stack<String> stack = new Stack<>();

stack.isEmpty(); // 스택이 비어있으므로 true 반환

stack.push("Apple");

stack.isEmpty(); // 스택에 "Apple"이 존재하므로 false 반환

 

3. ArrayDeque를 스택으로 활용하기

- Deque 인터페이스를 사용하므로 스택/큐 원하는대로 활용이 가능하다.

public class ArrayDequeStackExample {
	public static void main(String[] args) {
    
    	Deque<String> stack = new ArrayDeque<>();
    
    	// push: 요소 추가
    	stack.push("Apple");
    	stack.push("Banana");
    	stack.push("Cherry");
            
        // peek: 최상단 요소 조회
        System.out.println(stack.peek()); // 출력: Cherry

        // pop: 최상단 요소 제거
        System.out.println(stack.pop()); // 출력: Cherry
        System.out.println(stack.peek()); // 출력: Banana
        
    }
}

 

4. 스택 활용 알고리즘

4-1. 괄호 검사

- 문자열 내의 괄호들이 올바르게 짝지어졌는지 확인하기 위해서 스택을 사용한다. 여는 괄호가 있으면 push, 닫는 괄호가 나오면 pop하여 짝이 맞는지 검사한다.

public class BracketChecker {
	public static boolean isValidBracket(String s) {
    	Stack<Character> stack = new Stack<>();
        
        for(char c : s.toCharArray()) {
            // 여는 괄호라면 스택에 push한다.
            if(c == '(' || c == '{' || c == '[') {
            	stack.push(c);
            }
            
            // 닫는 괄호라면 pop해서 짝을 맞춘다. 
            else if(c == ')' || c == '}' || c == ']') {
            	// 스택이 비어있다면 올바르지 않은 문자열
                if (stack.isEmpty()) {
                    return false;
                }
                
                char top = stack.pop();
                
                // 괄호끼리 짝이 맞는지 확인
                if((c == ')' && top != '(') ||
                   (c == '}' && top != '{') ||
                   (c == ']' && top != '[')) {
                	return false;
                }
            }
    	}
        
        // 모든 괄호가 짝지어졌다면 스택에 아무것도 남아있지 않다.
        return stack.isEmpty();
    }
	
    public static void main(String[] args) {
     	String expr1 = "([{}])";
        String expr2 = "([)]";

        System.out.println(isValidBracket(expr1)); // 출력: true
        System.out.println(isValidBracket(expr2)); // 출력: false
    }
}

 

4-2. 후위표기법(RPN: Reverse Polish Notation) 계산

- 후위표기법은 연산자가 피연산자 뒤에 위치하는 수식 표기법이다. 스택을 사용하여 숫자이면 push, 연산자가 나오면 두 개의 숫자를 pop하여 연산을 수행하고 결과를 다시 push하여 답을 도출한다.

public class PostfixEvaluator {
    public static int evaluatePostfix(String expr) {
        Stack<Integer> stack = new Stack<>();

        // 공백을 기준으로 토큰 분리
        String[] tokens = expr.split(" ");

        for (String token : tokens) {
            // 숫자라면 스택에 push
            if (token.matches("-?\\d+")) {
                stack.push(Integer.parseInt(token));
            } else {
                // 연산자라면, 스택에서 두 피연산자를 꺼내서 연산 수행
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int result = 0;
                
                switch (token) {
                    case "+":
                        result = operand1 + operand2;
                        break;
                    case "-":
                        result = operand1 - operand2;
                        break;
                    case "*":
                        result = operand1 * operand2;
                        break;
                    case "/":
                        result = operand1 / operand2;
                        break;
                }
                
                // 연산 결과를 다시 스택에 push
                stack.push(result);
            }
        }
        
        // 최종 결과는 스택에 남은 하나의 값
        return stack.pop();
    }

    public static void main(String[] args) {
        String expr = "3 4 + 2 * 7 /";
        System.out.println(evaluatePostfix(expr)); // 출력: 2
    }
}