스택의 개념과 Java에서의 구현 방식

스택(Stack)은 후입선출(LIFO: Last In, First Out) 원칙에 따라 동작하는 자료구조로, 데이터의 추가와 제거가 한쪽 끝에서만 이루어진다. 이 구조는 함수 호출 관리, 수식 계산, 문법 분석 등 다양한 소프트웨어 설계 영역에서 핵심적인 역할을 한다.

Java에서는 java.util.Stack 클래스를 통해 기본적인 스택 기능을 제공하지만, 내부적으로 Vector를 상속받아 스레드 안전성을 보장하기 때문에 불필요한 성능 오버헤드가 발생할 수 있다. 따라서 동시성 제어가 필요하지 않은 일반적인 경우, Deque 인터페이스를 구현한 ArrayDeque를 사용하는 것이 더 효율적이다.

ArrayDeque를 이용한 스택 구현

다음 예제는 ArrayDeque를 스택처럼 사용하는 방법을 보여준다.

import java.util.ArrayDeque;
import java.util.Deque;

public class EfficientStack {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();

        // 요소 삽입
        stack.push("첫 번째");
        stack.push("두 번째");
        stack.push("세 번째");

        System.out.println("최상단 요소: " + stack.peek()); // 출력: 세 번째

        System.out.println("팝된 요소: " + stack.pop()); // 출력: 세 번째

        System.out.println("스택이 비었는가? " + stack.isEmpty()); // 출력: false
    }
}

수식 평가에서의 스택 활용

연산자 우선순위를 고려한 중위 표기식의 계산은 스택을 사용하면 간결하게 해결할 수 있다. 피연산자는 하나의 스택에, 연산자는 다른 스택에 저장하면서 우선순위에 따라 연산을 수행한다.

import java.util.Stack;

public class InfixEvaluator {
    public static int evaluateExpression(String expr) {
        Stack<Integer> operands = new Stack<>();
        Stack<Character> operators = new Stack<>();

        for (int i = 0; i < expr.length(); i++) {
            char ch = expr.charAt(i);

            if (Character.isDigit(ch)) {
                operands.push(ch - '0');
            } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                while (!operators.isEmpty() && getPriority(operators.peek()) >= getPriority(ch)) {
                    int result = compute(operands.pop(), operands.pop(), operators.pop());
                    operands.push(result);
                }
                operators.push(ch);
            }
        }

        while (!operators.isEmpty()) {
            operands.push(compute(operands.pop(), operands.pop(), operators.pop()));
        }

        return operands.pop();
    }

    private static int getPriority(char op) {
        return switch (op) {
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            default -> 0;
        };
    }

    private static int compute(int b, int a, char op) {
        return switch (op) {
            case '+' -> a + b;
            case '-' -> a - b;
            case '*' -> a * b;
            case '/' -> {
                if (b == 0) throw new ArithmeticException("0으로 나눌 수 없습니다.");
                yield a / b;
            }
            default -> 0;
        };
    }

    public static void main(String[] args) {
        System.out.println(evaluateExpression("3+5*2")); // 출력: 13
        System.out.println(evaluateExpression("10*2+7")); // 출력: 27
    }
}

괄호 유효성 검사

문자열 내 괄호 쌍의 균형 여부를 판단하는 문제는 스택의 전형적인 응용 사례다. 여는 괄호는 스택에 넣고, 닫는 괄호가 나타나면 스택 최상단과 비교하여 일치하는지 확인한다.

import java.util.Stack;

public class BracketValidator {
    public static boolean isValidPair(String input) {
        Stack<Character> bracketStack = new Stack<>();

        for (char c : input.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                bracketStack.push(c);
            } else if (c == ')' && (bracketStack.isEmpty() || bracketStack.pop() != '(')) {
                return false;
            } else if (c == ']' && (bracketStack.isEmpty() || bracketStack.pop() != '[')) {
                return false;
            } else if (c == '}' && (bracketStack.isEmpty() || bracketStack.pop() != '{')) {
                return false;
            }
        }

        return bracketStack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValidPair("{[()]}")); // true
        System.out.println(isValidPair("((("));   // false
        System.out.println(isValidPair("{[]}"));  // true
    }
}

JVM 내부의 스택 메커니즘

자바 가상 머신(JVM)은 각 스레드마다 호출 스택(call stack)을 유지하며, 메서드 실행 시마다 스택 프레임(stack frame)을 생성한다. 이 프레임에는 로컬 변수, 연산 스택, 메서드 반환 주소 등이 포함된다. 재귀 호출이 깊어질 경우 스택 공간을 초과하여 StackOverflowError가 발생할 수 있으므로, 반복문 기반의 구현이나 최적화된 알고리즘 설계가 중요하다.