스택(Stack): 마지막에 쌓은 것을 가장 먼저 꺼내는 구조

0. 글을 쓰게 된 이유

자료구조를 다시 공부하면서 스택(Stack)이 무엇인지는 알고 있었습니다.
“마지막에 들어간 데이터가 가장 먼저 나온다”라는 LIFO(Last In, First Out) 특성 정도는 익숙했습니다.

그러다가 ccommit 멘토링을 진행하면서 개념은 알고 있는데  왜 스택을 쓰는지 / 스택의 장점과 단점은 무엇인지 / 어떤 상황에서 스택이 정말로 적합한지에 대해서는 막연하게만 이해하고 있었다는 생각이 들었습니다.

예를 들어  “괄호 검사할 때 스택 쓰지” 수준에서 멈춰 있었지

• 호출 스택이 왜 그렇게 중요한지
• Undo/Redo 같은 기능이 왜 스택 없이 설계하기 어려운지
• 스택이 오히려 맞지 않는 경우가 언제인지
  이런 부분은 정리가 안 되어 있더라고요.

그래서 이번 글은 단순히 “스택이 뭔가요?”라는 설명을 넘어서
스택의 구조, 시간 복잡도, 장단점, 실제 사용 사례, 그리고 제가 생각하는 스택의 의미까지 한 번에 정리해 보려고 합니다.
이 글은 나중에 제가 복기용으로 다시 읽을 수 있도록 작성한 기록이기도 합니다.

---

1. 스택이란 무엇인가?

스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 선형 자료구조입니다.
가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조로 이를 LIFO(Last In, First Out) 구조라고 부릅니다.

예를 들어 컵을 위로 차곡차곡 쌓는다고 생각해보면 이해가 쉽습니다.

 

컵 1 올림
컵 2 올림
컵 3 올림

꺼낼 때는 역순으로 3 → 2 → 1 순서로 꺼낼 수밖에 없습니다.
중간에 있는 컵을 직접 꺼내는 것은 불가능합니다.
맨 위(top)에서만 접근할 수 있다는 것이 스택의 가장 중요한 특징입니다.

 

스택은 보통 다음과 같은 연산으로 구성됩니다.

push(x)	데이터를 스택의 맨 위에 추가합니다.
pop()	스택의 맨 위 데이터를 제거하고 반환합니다.
peek()	데이터를 제거하지 않고 맨 위 데이터를 확인합니다.
isEmpty()	스택이 비어있는지 확인합니다.
size()	스택에 몇 개의 데이터가 있는지 확인합니다.

이 간단한 규칙 하나가, 실제로는 매우 강력한 구조적 의미를 갖습니다.
가장 최근의 상태를 기억하고 필요할 때 역순으로 복원한다.”
이게 스택의 본질입니다.

---

2. 스택의 내부 구현 방식

스택은 개념적인 구조이기 때문에 구현 방식은 다양합니다.
대표적으로 두 가지 방식이 있습니다.

 

2.1 배열(Array) 기반 스택

메모리 상에 연속된 배열 공간을 확보하고, top이라는 인덱스를 관리합니다.

 

push(x) → arr[++top] = x
pop() → return arr[top--]

 

장점

• 연속된 메모리 덕분에 CPU 캐시 효율이 높습니다.
• 구현이 간단하고 연산 속도가 빠릅니다.

CPU 캐시 효율이 높다”는 말은 스택이 배열 기반으로 연속된 메모리 공간을 사용하기 때문에 CPU가 데이터를 훨씬 빠르게 읽을 수 있다는 뜻입니다.

 

단점

• 배열 크기를 미리 지정해야 합니다.
• 꽉 차면 더 큰 배열로 복사해야 하므로, 가끔 O(n) 시간이 걸릴 수 있습니다.

 

 Java에서는 Stack보다 ArrayDeque를 사용하는 것이 더 권장됩니다.
ArrayDeque는 동기화 오버헤드가 없고 내부적으로 배열 기반이라 빠르기 때문입니다.

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);
stack.push(20);
stack.push(30);

System.out.println(stack.peek()); // 30
System.out.println(stack.pop());  // 30
System.out.println(stack.pop());  // 20
System.out.println(stack.pop());  // 10

---

2.2 연결 리스트(Linked List) 기반 스택

단일 연결 리스트의 맨 앞(head)을 스택의 top으로 사용합니다.

• push(x) → head 앞에 새 노드 추가
• pop() → head 노드를 제거

장점

• 크기를 미리 지정할 필요가 없습니다.
• 노드가 필요한 만큼만 메모리를 사용합니다.

단점

• 각 노드가 포인터를 하나 더 들고 있어 메모리 오버헤드가 큽니다.
• 메모리가 분산되어 있어서 캐시 효율이 떨어집니다.

---

2.3 배열기반 스택이 캐시 효율이 높은 이유  

배열(Array) 기반 스택은 메모리에 연속된 주소 공간을 차지합니다.
예를 들어 스택 내부가 다음과 같이 생겼다고 할게요.

 

[ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]

이 데이터들은 실제 메모리 주소에서도 이렇게 붙어있습니다.

0x1000 → 10  
0x1004 → 20  
0x1008 → 30  
0x100C → 40  
0x1010 → 50

CPU는 10을 읽을 때 이 근처(0x1004~0x1010) 데이터도 같이 캐시에 올려두자고 판단합니다.
이 덕분에 이후 push나 pop, 혹은 다음 데이터 접근 시 이미 캐시에 올라와 있어서 매우 빠르게 처리됩니다.

이것을 “캐시 적중률(Cache Hit Rate)이 높다” 라고 합니다.
즉 배열 기반 스택은 캐시 효율이 높기 때문에 CPU 입장에서 “읽기/쓰기” 속도가 빠릅니다.

---

2.3 반대로 연결리스트는 (Linked List)왜 효율이 떨어진까?

 

 

연결 리스트 기반 스택은 각 노드가 메모리 여기저기 흩어져 있습니다.

Node1 → Node2 → Node3​

 

 

이렇게 보이지만 실제 메모리 주소는 다음처럼 흩어져 있을 수 있습니다.

Node1: 0x1000  
Node2: 0x3A20  
Node3: 0x7F50

 

CPU가 Node1을 캐시에 올려도 Node2는 완전히 다른 주소에 있어서 새로 메모리에 접근해야 합니다.
그 결과 캐시 적중률이 낮아지고, 성능이 떨어집니다.

요약

구조메모리 배치캐시 효율이유

배열 기반 스택	연속적	높음	연속된 주소 덕분에 캐시가 인접 데이터를 미리 올림
연결 리스트 스택	불연속적	낮음	노드들이 메모리 곳곳에 흩어져 있음

---

예를 들어 이해하기

배열 기반 스택은 책장이 깔끔하게 정리된 서재와 같습니다.
책 하나를 꺼내면 그 옆 책도 바로 손이 닿죠.

 

반면 연결 리스트는 책이 방 전체에 흩어져 있는 상태입니다.
다음 책을 찾을 때마다 방을 돌아다녀야 합니다.

 

 

CPU 입장에서도 배열 기반 구조는 “옆 데이터를 미리 읽어둘 수 있는 구조”라서 훨씬 빠릅니다.
그래서 스택처럼 순차적으로 접근이 많은 자료구조는 배열 기반으로 구현하는 편이 훨씬 효율적입니다.

 

---

3. 시간 복잡도 & 공간 복잡도

push	O(1)*	요소 추가
pop	O(1)	맨 위 요소 제거
peek	O(1)	맨 위 요소 확인
isEmpty	O(1)	비어있는지 확인
size	O(1)	크기 반환

* 배열 기반에서는 가끔 리사이징 시 O(n)이 걸리지만 평균적으로는 O(1)로 봅니다.
(이를 Amortized O(1) 이라고 합니다.)

공간 복잡도는 당연히 O(n)입니다.
즉, n개의 데이터를 저장하면 n개의 공간이 필요합니다.

---

4. 스택이 중요한 이유

4.1 함수 호출 구조(Call Stack)

우리가 메서드를 호출하면 그 메서드의 정보(매개변수, 지역변수, 복귀 주소 등)가호출 스택(Call Stack)에 저장됩니다.
함수가 끝나면 스택에서 해당 프레임이 pop됩니다. 즉 프로그램 실행 자체가 스택 위에서 이루어집니다.

재귀(Recursion)도 스택을 기반으로 작동합니다.

재귀가 너무 깊어지면 “StackOverflowError”가 발생하는 이유도 바로 이것입니다.

---

4.2 중첩 구조를 표현하기에 완벽한 자료구조

스택은 “들어갔다가 다시 나오는 구조”를 표현하기에 이상적입니다.대표적으로 다음과 같은 경우에 사용됩니다.

• 괄호 짝 맞추기
• HTML/XML 태그 유효성 검사
• DFS(깊이 우선 탐색)
• 수식 계산기
• 브라우저의 뒤로가기 / 앞으로가기 기능

이런 구조의 공통점은 “가장 마지막에 들어간 것이 가장 먼저 나와야 한다”는 점입니다.
즉 LIFO 로직이 그대로 적용됩니다.

---

5. 실전에서 스택이 사용되는 예시

5.1 괄호 유효성 검사

 

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if (!isPair(open, c)) return false;
        }
    }
    return stack.isEmpty();
}

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

여는 괄호를 push, 닫는 괄호를 만나면 pop으로 짝을 확인하는 방식입니다.
이 로직은 파서(Parser), 컴파일러, JSON/XML 처리기 등에서도 동일하게 쓰입니다.

---

5.2 깊이 우선 탐색(DFS) - 반복문으로 구현

재귀 대신 명시적인 스택을 이용하면 깊은 탐색 구조에서도 안정적으로 동작할 수 있습니다.

public void dfs(Node root) {
    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        System.out.println(cur.value);

        for (int i = cur.children.size() - 1; i >= 0; i--) {
            stack.push(cur.children.get(i));
        }
    }
}

 

이 방식은 특히 재귀 깊이가 너무 깊을 때 유용합니다.

---

5.3 브라우저의 뒤로가기/앞으로가기

• 뒤로가기: 현재 페이지를 forwardStack에 push하고 backStack.pop()으로 이동
• 앞으로가기: 현재 페이지를 backStack에 push하고 forwardStack.pop()으로 이동

이 구조 덕분에 사용자는 “이전 상태로 돌아가기”를 자연스럽게 수행할 수 있습니다.

---

5.5 수식 계산기 (후위 표기법, Postfix)

수식 평가에서도 스택은 핵심적인 역할을 합니다.
연산자 우선순위를 처리하거나 후위 표기식(postfix expression)을 계산할 때
연산자 스택과 피연산자 스택이 함께 쓰입니다.

---

6. 스택의 장점

• 연산 속도가 빠르고(O(1)) 구조가 단순합니다.
• 최근 데이터에 집중할 수 있어 “되돌리기” “복원” 등에 적합합니다.
• 호출 구조와 직결되어 있어 디버깅 시 로직 추적이 쉽습니다.
• 중첩 구조나 복귀(rollback) 흐름을 직관적으로 표현할 수 있습니다.

---

7. 스택의 단점

• 중간 요소 접근이 불가능합니다.
• 전체 탐색이 어렵습니다. (pop을 반복해야 함)
• 너무 깊은 재귀나 스택 사용은 StackOverflowError를 유발할 수 있습니다.
• FIFO(선입선출) 로직에는 부적합합니다. (이럴 땐 Queue를 사용)

---

8. 언제 스택을 떠올려야 할까?

가장 최근의 작업부터 되돌려야 할 때	스택
중첩된 구조(괄호, 태그 등)를 다룰 때	스택
깊이 우선 탐색을 구현할 때	스택
현재 상태를 잠시 저장했다가 복귀해야 할 때	스택

이 네 가지 상황이 보이면 스택을 떠올리는것이 좋습니다.

---