스택: LIFO 불변식과 Java ArrayDeque의 메모리 경계를 이해하기

스택은 마지막에 넣은 원소를 먼저 꺼내는 LIFO ADT다. 여기서 Deque로 만든 application stack과 method call을 저장하는 JVM Stack은 이름만 비슷한 다른 층이다. 둘을 섞으면 “스택은 heap에 있나 stack에 있나” 같은 질문에 잘못 답하게 된다.

1. 문제 계약: 가장 최근에 열린 괄호를 먼저 닫는다

문자열의 (), [], {}가 올바르게 중첩됐는지 판단한다. 일반 문자는 무시한다. 닫는 괄호가 나오면 아직 닫히지 않은 가장 최근 여는 괄호와 짝이어야 한다. 빈 문자열은 균형 잡힌 입력, null은 계약 위반이다.

([)]는 여는 괄호 수와 닫는 괄호 수가 같지만 올바르지 않다. 순서와 중첩을 기억해야 하므로 count 하나로는 부족하다.

2. 표현 불변식과 상태 추적

{a[(b+c)]}에서 일반 문자를 제외한 상태다.

불변식: index i 처리 후 stack에는 prefix [0,i]에서 아직 닫히지 않은 여는 괄호가 등장 순서의 역순으로 있다. 닫는 괄호는 top과만 짝이 될 수 있다. top이 다르거나 없으면 이후 문자를 추가해도 이미 생긴 교차를 복구할 수 없으므로 즉시 false다. 끝에서 stack이 비어야 모든 여는 괄호가 닫혔다.

실패 예시 ([)]를 끝까지 미루지 않는다

([)]를 처리하면 (, [가 차례로 쌓인 뒤 )를 만난다. 이때 top은 [다. 단순히 여는 괄호 2개와 닫는 괄호 2개라는 개수만 세면 마지막까지 가서 true로 오판할 수 있지만, LIFO 계약은 세 번째 문자에서 이미 위반을 확정한다.

같은 원리는 함수 호출, HTML/XML tag, expression parser에도 적용된다. 다만 실제 parser는 괄호 문자만 저장하는 대신 token 종류와 source position을 함께 저장해야 “몇 번째 줄에서 무엇이 닫히지 않았는지” 오류를 만들 수 있다. 상태 하나가 커지면 최대 중첩 깊이 $d$에서 메모리도 Character $d$개가 아니라 token record $d$개의 heap 비용이 된다. 그래서 공개 입력을 파싱할 때는 전체 길이와 별도로 최대 중첩 깊이를 제한해야 한다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

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

public final class StackDemo {
    static boolean isBalanced(String text) {
        if (text == null) throw new IllegalArgumentException("text must not be null");
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty() || !matches(stack.pop(), ch)) return false;
            }
        }
        return stack.isEmpty();
    }

    static boolean matches(char open, char close) {
        return open == '(' && close == ')' || open == '[' && close == ']' || open == '{' && close == '}';
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(isBalanced("{a[(b+c)]}"), "nested");
        check(!isBalanced("([)]"), "crossed");
        check(!isBalanced("("), "unclosed");
        check(isBalanced(""), "empty");
        System.out.println("balanced=true, crossed=false, unclosed=false");
    }
}

javac --release 21 StackDemo.java
java StackDemo

직접 실행한 출력은 다음과 같다.

balanced=true, crossed=false, unclosed=false

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

3. push/pop/peek와 add/remove/get 계열

Deque는 양 끝 연산을 제공하며 stack으로 쓸 때 push, pop, peek를 한쪽 끝에 일관되게 적용한다. pop은 비면 NoSuchElementException, poll 계열은 null을 반환한다. 실패 계약을 섞으면 빈 stack이 정상 종료인지 버그인지 흐려진다.

Java SE 문서는 legacy Stack보다 Deque 구현을 선호한다고 안내한다. ArrayDeque는 null을 허용하지 않으므로 null을 빈 상태 sentinel로 쓸 수 없고, 이 제약이 peek()==null을 빈 상태로 해석 가능하게 한다.

4. 시간·공간 복잡도

문자 $n$개를 한 번씩 보고 각 괄호를 최대 한 번 push/pop하므로 시간은 $\Theta(n)$이다. 모두 여는 괄호면 stack 크기가 $n$이 되어 보조 공간은 최악 $O(n)$이다. 올바른 최대 중첩 깊이가 $d$라면 실제 peak는 $O(d)$다.

ArrayDeque의 양 끝 기본 연산은 API 문서상 대부분 amortized constant time이다. backing array가 가득 차면 resize/copy가 한 호출에 집중될 수 있으므로 매 호출 최악 상수라고 바꾸어 말하지 않는다.

5. JVM Stack과 heap의 ArrayDeque를 구분한다

new ArrayDeque<>() 객체와 backing array, boxed Character reference는 heap에 있다. method의 local stack reference와 loop index는 frame local variable 관점이다. Character는 boxing이지만 cache 여부는 구현/값 범위에 의존하므로 일반적인 allocation 제거 보장으로 쓰지 않는다.

재귀 DFS에서 “stack을 쓴다”는 말은 method invocation마다 frame이 중첩된다는 뜻이다. 깊이가 허용된 JVM Stack보다 크면 JVMS가 규정한 StackOverflowError가 발생할 수 있다. 명시적 ArrayDeque로 바꾸면 상태는 heap으로 이동하고 capacity를 관찰·제어할 수 있지만 전체 메모리가 사라지는 것은 아니다.

6. Queue·재귀·priority queue와 비교

스택의 “반대”를 억지로 하나 고르면 FIFO queue가 가까우나, 선택 기준은 탐색 순서의 계약이다.

7. 실제 도메인 적용

parser의 nested scope, undo history, DFS, expression evaluation에 쓴다. parser에서는 maximum nesting depth와 malformed input rate를 관측한다. 사용자 입력이 무제한 중첩을 허용하면 heap stack이어도 memory DoS가 가능하므로 depth limit이 필요하다. transaction 보상 작업 stack은 단순 pop만으로 외부 side effect의 원자성을 보장하지 않으므로 idempotency와 retry log가 별도다.

8. 이건 피한다

• Stack과 JVM Stack을 같은 객체로 설명한다. application container와 VM runtime area의 수명·위치가 다르다. ADT/구현체/frame을 구분한다.
• 빈 상태에서 무조건 pop한다. malformed input이 예외로 터져 API 계약을 깨뜨린다. 먼저 isEmpty를 확인하거나 예외 계약을 명시한다.
• 양 끝 method를 섞는다. push 후 removeLast를 쓰면 의도한 LIFO가 깨진다. 한 용어 집합을 유지한다.
• 무제한 재귀를 신뢰한다. 외부 입력 깊이가 JVM Stack 한계를 넘을 수 있다. depth limit이나 명시적 stack으로 바꾼다.
• 중첩 깊이 상한 없이 parser를 공개한다. heap 기반이어도 memory를 소진한다. input size/depth 제한과 rejection metric을 둔다.

Reference

• Oracle, Deque — Java SE 21 API
• Oracle, ArrayDeque — Java SE 21 API
• Oracle, Stack — Java SE 21 API
• Oracle, The Java Virtual Machine Specification, Java SE 21 — JVM Stacks and Frames
• Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Stacks and Queues