[알고리즘] 15. 스택(Stack)

지난 글에서는 예외 케이스 처리법에 대해 정리했습니다. 이번 글부터는 알고리즘 문제에서 자주 사용하는 자료구조 영역으로 들어갑니다. 그 첫 번째 주제는 스택(Stack)입니다.

스택은 데이터를 한쪽 방향으로만 넣고 빼는 자료구조입니다. 처음에는 단순해 보이지만, 괄호 검사, 되돌리기, 뒤집기, DFS, 수식 처리 같은 문제에서 매우 자주 사용됩니다.

스택은 나중에 들어온 데이터가 먼저 나가는 후입선출 구조입니다.

1. 스택이란?

스택은 데이터를 차곡차곡 쌓아두는 구조입니다. 가장 쉽게 떠올릴 수 있는 예시는 접시 더미입니다.

접시를 쌓을 때는 위에 올리고, 꺼낼 때도 가장 위에 있는 접시부터 꺼냅니다. 중간에 있는 접시를 바로 꺼내기는 어렵습니다.

접시 A를 놓는다.
접시 B를 놓는다.
접시 C를 놓는다.

꺼낼 때는 C → B → A 순서로 꺼낸다.

스택도 이와 같은 방식으로 동작합니다. 먼저 들어간 값보다 나중에 들어간 값이 먼저 나옵니다.

스택은 마지막에 넣은 값을 가장 먼저 꺼내는 구조입니다.

2. 후입선출 구조

스택의 가장 중요한 특징은 후입선출입니다. 영어로는 LIFO라고 부릅니다.

용어	의미
후입선출	나중에 들어온 값이 먼저 나감
LIFO	Last In, First Out

예를 들어 스택에 10, 20, 30을 순서대로 넣었다고 생각해보겠습니다.

push 10
push 20
push 30

이제 값을 꺼내면 가장 마지막에 들어간 30부터 나옵니다.

pop → 30
pop → 20
pop → 10

이 흐름이 스택의 핵심입니다.

3. 스택의 기본 연산

스택에서 자주 사용하는 기본 연산은 다음과 같습니다.

연산	의미
push	스택에 값을 넣는다.
pop	스택의 가장 위 값을 꺼낸다.
peek	스택의 가장 위 값을 확인만 한다.
isEmpty	스택이 비어 있는지 확인한다.
size	스택에 들어 있는 값의 개수를 확인한다.

스택 문제에서는 값을 넣고, 가장 위의 값을 확인하고, 필요하면 꺼내는 흐름이 자주 등장합니다.

4. Java에서 Stack 사용하기

Java에서는 Stack 클래스를 사용할 수 있습니다.

import java.util.Stack;

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

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

System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());

출력 결과는 다음과 같습니다.

30
20
10

10, 20, 30 순서로 넣었지만 꺼낼 때는 30, 20, 10 순서로 나옵니다. 이것이 후입선출 구조입니다.

5. push와 pop

스택에서 가장 기본이 되는 연산은 push와 pop입니다. push는 값을 넣는 연산이고, pop은 값을 꺼내는 연산입니다.

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

stack.push(1);
stack.push(2);
stack.push(3);

int value = stack.pop();

System.out.println(value);

출력 결과는 다음과 같습니다.

마지막에 넣은 값이 3이므로 pop을 하면 3이 먼저 나옵니다.

push는 넣기, pop은 꺼내기입니다.

6. peek으로 맨 위 값 확인하기

pop은 값을 꺼내면서 스택에서 제거합니다. 반면 peek은 값을 제거하지 않고 가장 위에 있는 값만 확인합니다.

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

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

System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.size());

출력 결과는 다음과 같습니다.

30
30
3

peek은 값을 확인만 하기 때문에 여러 번 호출해도 값이 제거되지 않습니다. 따라서 스택의 크기도 그대로 3입니다.

7. isEmpty로 비어 있는지 확인하기

스택에서 값을 꺼내기 전에는 스택이 비어 있는지 확인하는 것이 중요합니다. 비어 있는 스택에서 pop이나 peek을 호출하면 오류가 발생할 수 있습니다.

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

if (!stack.isEmpty()) {
    System.out.println(stack.pop());
} else {
    System.out.println("스택이 비어 있습니다.");
}

출력 결과는 다음과 같습니다.

스택이 비어 있습니다.

알고리즘 문제에서는 pop을 하기 전에 isEmpty를 확인하는 습관이 중요합니다.

스택에서 값을 꺼내기 전에는 비어 있는지 먼저 확인해야 합니다.

8. 스택으로 문자열 뒤집기

스택은 나중에 들어온 값이 먼저 나오기 때문에 데이터를 뒤집는 데 사용할 수 있습니다. 문자열을 한 글자씩 스택에 넣은 뒤 꺼내면 역순이 됩니다.

import java.util.Stack;

String word = "hello";

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

for (int i = 0; i < word.length(); i++) {
    stack.push(word.charAt(i));
}

StringBuilder sb = new StringBuilder();

while (!stack.isEmpty()) {
    sb.append(stack.pop());
}

System.out.println(sb.toString());

출력 결과는 다음과 같습니다.

olleh

h, e, l, l, o 순서로 넣었지만 꺼낼 때는 o, l, l, e, h 순서가 됩니다.

9. 스택으로 괄호 검사하기

스택이 가장 자주 사용되는 대표 문제는 괄호 검사입니다. 괄호 문자열이 올바른지 확인하는 문제입니다.

예를 들어 아래 문자열은 올바른 괄호입니다.

()()
(())

반면 아래 문자열은 올바르지 않습니다.

())(
(()

괄호 검사의 기본 규칙은 다음과 같습니다.

여는 괄호 '('가 나오면 스택에 넣는다.
닫는 괄호 ')'가 나오면 스택에서 여는 괄호 하나를 꺼낸다.
닫는 괄호가 나왔는데 스택이 비어 있으면 올바르지 않다.
모든 문자를 확인한 뒤 스택이 비어 있어야 올바르다.

import java.util.Stack;

String text = "(())";

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

boolean valid = true;

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

    if (ch == '(') {
        stack.push(ch);
    } else if (ch == ')') {
        if (stack.isEmpty()) {
            valid = false;
            break;
        }

        stack.pop();
    }
}

if (!stack.isEmpty()) {
    valid = false;
}

System.out.println(valid);

출력 결과는 다음과 같습니다.

true

괄호 검사 문제에서는 닫는 괄호가 나왔을 때 스택이 비어 있는지 확인하는 것이 매우 중요합니다.

10. 괄호 검사 흐름 예시

문자열 "(()())"를 기준으로 스택의 변화를 살펴보겠습니다.

문자	동작	스택 상태
(	push	(
(	push	((
)	pop	(
(	push	((
)	pop	(
)	pop	비어 있음

마지막까지 확인했을 때 스택이 비어 있으므로 올바른 괄호 문자열입니다.

여는 괄호는 쌓고, 닫는 괄호는 짝을 맞춰 꺼냅니다.

11. 여러 종류의 괄호 검사하기

괄호가 한 종류가 아니라 (), {}, []처럼 여러 종류라면 닫는 괄호가 나왔을 때 스택의 맨 위 값과 짝이 맞는지 확인해야 합니다.

import java.util.Stack;

String text = "{[()]}";

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

boolean valid = true;

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

    if (ch == '(' || ch == '{' || ch == '[') {
        stack.push(ch);
    } else {
        if (stack.isEmpty()) {
            valid = false;
            break;
        }

        char top = stack.pop();

        if (ch == ')' && top != '(') {
            valid = false;
            break;
        }

        if (ch == '}' && top != '{') {
            valid = false;
            break;
        }

        if (ch == ']' && top != '[') {
            valid = false;
            break;
        }
    }
}

if (!stack.isEmpty()) {
    valid = false;
}

System.out.println(valid);

출력 결과는 다음과 같습니다.

true

여러 종류의 괄호가 나오는 문제에서는 닫는 괄호가 어떤 여는 괄호와 짝이 되는지 확인해야 합니다.

12. 스택을 사용하는 대표 상황

스택은 아래와 같은 상황에서 자주 사용됩니다.

상황	이유
괄호 검사	최근에 열린 괄호부터 닫혀야 함
문자열 뒤집기	마지막에 넣은 문자가 먼저 나옴
되돌리기 기능	마지막 작업부터 되돌림
DFS	최근에 발견한 노드를 먼저 탐색할 수 있음
수식 계산	연산자와 피연산자를 순서에 맞게 처리

문제를 보고 “가장 최근에 들어온 것을 먼저 처리해야 한다”는 느낌이 들면 스택을 떠올리면 좋습니다.

13. 스택의 시간복잡도

스택의 기본 연산은 대부분 빠르게 처리됩니다.

연산	시간복잡도
push	O(1)
pop	O(1)
peek	O(1)
isEmpty	O(1)
size	O(1)

스택에 값을 넣거나 빼는 작업은 한 번에 처리되므로 O(1)입니다. 문자열 전체를 한 번 순회하면서 스택을 사용한다면 전체 시간복잡도는 보통 O(N)입니다.

스택 자체의 연산은 빠르지만, 전체 문제의 시간복잡도는 데이터를 몇 번 순회하는지에 따라 결정됩니다.

14. 스택에서 자주 하는 실수

스택 문제를 풀 때는 아래 실수를 조심해야 합니다.

비어 있는 스택에서 pop을 호출하는 경우
비어 있는 스택에서 peek을 호출하는 경우
push와 pop의 순서를 반대로 이해하는 경우
괄호 검사 후 스택이 비어 있는지 확인하지 않는 경우
여러 종류의 괄호에서 짝이 맞는지 확인하지 않는 경우
스택이 필요한 문제를 단순 반복문만으로 억지로 처리하려는 경우

특히 괄호 검사에서는 두 가지를 반드시 확인해야 합니다.

닫는 괄호가 나왔을 때 스택이 비어 있지 않은가?
모든 문자를 확인한 뒤 스택이 비어 있는가?

스택 문제의 핵심 예외 케이스는 “비어 있는데 꺼내려고 하는 상황”입니다.

15. 정리

이번 글에서는 스택에 대해 정리했습니다.

스택은 나중에 들어온 값이 먼저 나가는 후입선출 구조이다.
스택의 대표 연산은 push, pop, peek, isEmpty, size이다.
push는 값을 넣고, pop은 값을 꺼내며, peek은 맨 위 값을 확인한다.
스택에서 값을 꺼내기 전에는 비어 있는지 확인해야 한다.
문자열 뒤집기, 괄호 검사, 되돌리기, DFS 등에 스택을 사용할 수 있다.
스택의 기본 연산은 대부분 O(1)이다.
괄호 검사 문제에서는 마지막에 스택이 비어 있어야 올바른 문자열이다.

스택은 알고리즘에서 매우 중요한 기본 자료구조입니다. 문제를 보고 최근에 들어온 값을 먼저 처리해야 한다면 스택을 떠올려보면 됩니다.

스택의 핵심은 “마지막에 들어온 값이 가장 먼저 나온다”는 흐름을 이해하는 것입니다.

다음 글 예고

다음 글에서는 큐(Queue)에 대해 알아보겠습니다.

큐의 개념, 선입선출 구조, add와 poll, 대기열 문제, BFS와의 관계까지 예제로 정리해보겠습니다.

'Problem Solving > Algorithm' 카테고리의 다른 글

[알고리즘] 17. 덱(Deque) (0)	2026.06.30
[알고리즘] 16. 큐(Queue) (0)	2026.06.29
[알고리즘] 14. 예외 케이스 처리법 (0)	2026.06.27
[알고리즘] 13. 정렬 기준 만들기 (0)	2026.06.26
[알고리즘] 12. 빈도수 계산 (0)	2026.06.25