---
title: "스택: LIFO 불변식과 Java ArrayDeque의 메모리 경계를 이해하기"
slug: "java-stack"
category: "CS"
topic: "cs"
subtopic: "data-structures"
tags: ["Java","Stack","Deque","ArrayDeque","JVM Stack"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "ADT 스택과 JVM Stack을 구분하고, 괄호 검증의 LIFO 정당성·ArrayDeque 할당·재귀 대체 기준과 잘못된 사용을 실행 가능한 Java로 확인한다."
kind: "Deep Dive"
evidence: "Java SE 21 Deque/ArrayDeque API·JVMS 21 frame 정의를 대조하고 StackDemo의 정상·교차·미완료 입력을 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

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

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

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

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

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

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

| 입력 | 연산 | top → bottom |
| --- | --- | --- |
| `{` | push | `{` |
| `[` | push | `[`, `{` |
| `(` | push | `(`, `[`, `{` |
| `)` | pop/match | `[`, `{` |
| `]` | pop/match | `{` |
| `}` | pop/match | empty |

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

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

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

| 입력 prefix | stack top → bottom | 판정 |
| --- | --- | --- |
| `(` | `(` | 계속 |
| `([` | `[`, `(` | 계속 |
| `([)` | `[`, `(` | `[`와 `)` 불일치, 즉시 실패 |

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

## 실행 재현

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

```java
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");
    }
}
```

```bash
javac --release 21 StackDemo.java
java StackDemo
```

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

```text
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와 비교

| 구조 | 다음에 꺼낼 것 | 맞는 문제 |
| --- | --- | --- |
| Stack | 가장 최근 상태 | 중첩, 되돌리기, DFS |
| Queue | 가장 오래 기다린 상태 | 도착 순서, BFS |
| PriorityQueue | 우선순위 최소/최대 | scheduler, Dijkstra 후보 |
| recursion | 현재 call의 하위 문제 | 깊이가 제한된 tree 구조 |

스택의 “반대”를 억지로 하나 고르면 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](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Deque.html)
- Oracle, [ArrayDeque — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayDeque.html)
- Oracle, [Stack — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Stack.html)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — JVM Stacks and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5.2)
- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Stacks and Queues](https://algs4.cs.princeton.edu/13stacks/)