스택(Stack) C++ 구현: 오버플로 검사, ASan 결과, 속도 실측

배열 스택과 연결 리스트 스택을 AddressSanitizer로 다시 돌려 찾은 오버플로·언더플로·메모리 누수와 수정 코드, 괄호 검사 예제, std::stack·C# Stack<T> 속도 비교.

2026년 11월 보강: 2021년에 쓴 스택 강좌의 C++ 예제 두 개를 Apple clang 21(-Wall -Wextra, 경고 0건)로 다시 컴파일하고, AddressSanitizer와 UndefinedBehaviorSanitizer를 켜서 다시 실행했습니다. 예제의 main은 2021년과 같은 결과를 내지만, 클래스 자체에는 오버플로 검사도 언더플로 검사도 없었고, 복사하면 이중 해제가 일어났으며, 연결 리스트 스택은 모든 노드를 누수하면서 push·pop마다 리스트 전체를 훑고 있었습니다. 새니타이저 출력, 고친 코드, 괄호 검사 예제, 속도 실측을 정리했습니다.

자료구조 수업이나 코딩 테스트, 간단한 파서 때문에 C/C++로 스택을 직접 짜야 하는 분, 그리고 C#의 Stack<T>가 무엇을 대신해 주는지 궁금한 분을 위한 글입니다. 결론부터: 스택은 나중에 들어간 것이 먼저 나오는(LIFO) 구조이고, 사고는 거의 항상 "가득 찼는데 push"와 "비었는데 pop" 두 군데서 납니다. 검사 두 줄을 넣은 배열 스택이 측정한 것 중 가장 빨랐고, 연결 스택은 약 50배 느려서 상한이 없을 때만 고를 이유가 있습니다.

스택이란, 그리고 어디에 쓰이나

책상 위에 쌓은 책을 정리할 때 맨 위의 책부터 집어 들게 됩니다. 넣는 동작을 push, 꺼내는 동작을 pop, 꺼내지 않고 맨 위만 보는 동작을 peek(2021년 코드의 getTop)이라고 합니다. 한쪽 끝만 건드리므로 제대로 만들면 push와 pop 모두 O(1)입니다.

실무에서 스택을 만나는 곳:

  • 모든 프로그램의 호출 스택(재귀가 너무 깊으면 나는 "스택 오버플로" — 정렬 글의 퀵 정렬이 정확히 이렇게 죽었습니다)
  • 편집기의 되돌리기(Undo) 기록
  • 컴파일러의 괄호 검사와 수식 파싱
  • 깊이 우선 탐색(DFS)을 반복문으로 쓸 때의 명시적 스택

2021년 배열 스택을 AddressSanitizer로 돌려 보니

2021년 글의 첫 예제는 new T[maxSize]로 배열을 잡고 top에 개수를 담는 템플릿 클래스였습니다. 조각 코드에 #include <iostream>과 using namespace std;만 빠져 있어서 이 두 줄을 넣었더니, 원래의 main(a~e를 push하고 다섯 번 pop)은 clang++ -std=c++17 -Wall -Wextra에서 경고 없이 컴파일되고 2021년과 같은 순서 e, d, c, b, a를 출력했습니다.

문제는 그 정상 경로 바깥입니다. push는 stack[top++] = data;, pop은 return stack[--top];뿐이고, isFull은 "아직 쓸 일이 없다"며 주석 처리돼 있었습니다. 잘못된 사용 세 가지를 만들어 일반 빌드와 -fsanitize=address,undefined -g 빌드로 각각 돌렸습니다.

잘못된 사용 일반 빌드 ASan/UBSan 빌드
Stack<char>(5)에 6번째 push f 출력, 종료 코드 0 heap-buffer-overflow, WRITE of size 1, "0 bytes after 5-byte region" (Stack<char>::push)
빈 스택에서 pop() 0 출력, 종료 코드 0 heap-buffer-overflow, READ of size 1, "1 bytes before 5-byte region" (Stack<char>::pop)
Stack<char> copy = s; 메시지 없이 종료 코드 133 attempting double-free (Stack<char>::~Stack())

위의 두 줄이 정말 위험한 부분입니다. 새니타이저 없이는 멀쩡해 보입니다. 할당 영역 뒤로 1바이트를 쓰거나 앞으로 1바이트를 읽고도 그냥 계속 실행됩니다. 세 번째 줄은 "3의 법칙"(rule of three) 문제입니다. 원시 포인터를 소유하면서 복사 생성자는 컴파일러가 만든 것을 그대로 쓰니, 두 객체가 같은 배열을 두 번 delete[]합니다.

고친 배열 스택

검사 두 개를 넣고, 실패는 반환값으로 알리고, 복사는 막았습니다. 빈 스택의 peek은 돌려줄 값이 없으므로 예외를 던집니다.

template <class T>
class ArrayStack {
    T* data_; int top_ = 0; int cap_;
public:
    explicit ArrayStack(int cap) : data_(new T[cap]), cap_(cap) {}
    ~ArrayStack() { delete[] data_; }
    ArrayStack(const ArrayStack&) = delete;             // 복사 금지 → 이중 해제 없음
    ArrayStack& operator=(const ArrayStack&) = delete;
    bool push(const T& v) {                              // 오버플로: 쓰지 않고 알린다
        if (top_ == cap_) return false;
        data_[top_++] = v; return true;
    }
    bool pop(T& out) {                                   // 언더플로: 읽지 않고 알린다
        if (top_ == 0) return false;
        out = data_[--top_]; return true;
    }
    const T& peek() const {
        if (top_ == 0) throw std::out_of_range("peek on empty stack");
        return data_[top_ - 1];
    }
    bool empty() const { return top_ == 0; }
    bool full()  const { return top_ == cap_; }
};
흐름도. 위: push(v) 에서 판단 top == cap 으로 가고, 거짓이면 data[top++] = v 를 쓴다. 아래: pop(out) 에서 판단 top == 0 으로 가고, 거짓이면 out = data[--top] 을 읽는다. 두 판단은 가운데의 'false 반환'을 함께 쓰며, push 는 오버플로일 때, pop 은 언더플로일 때 그쪽으로 간다.
2021년 배열 스택에 빠져 있던 두 가지 검사. 둘 다 조용히 메모리를 망가뜨리던 동작을 호출한 쪽이 확인할 수 있는 반환값으로 바꾼다.

용량 5인 스택에 a~f를 넣고 모두 꺼낸 결과입니다.

push('f') rejected: stack full
e d c b a
pop on empty -> false

같은 테스트를 ASan/UBSan 빌드로 돌려도 보고가 하나도 나오지 않습니다. 가득 찼을 때 false를 줄지, 예외를 던질지, 배열을 늘릴지는 설계의 선택이지만 "그래도 쓴다"는 선택지는 없습니다.

활용 예: 괄호 짝 검사

스택의 대표적인 쓰임은 (, [, {가 올바른 순서로 닫혔는지 확인하는 일입니다. 여는 괄호를 만나면 그 위치를 push하고, 닫는 괄호를 만나면 pop해서 짝을 비교합니다. 꺼낼 것이 없거나, 짝이 다르거나, 끝났는데 남아 있으면 오류입니다. 위치를 넣어 두면 어디가 틀렸는지도 알려 줄 수 있습니다.

long check_brackets(std::string_view s) {      // 짝이 맞으면 -1, 아니면 문제 위치
    ArrayStack<long> st(static_cast<int>(s.size()) + 1);
    for (long i = 0; i < (long)s.size(); i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') { st.push(i); continue; }
        if (c != ')' && c != ']' && c != '}') continue;
        long open;
        if (!st.pop(open)) return i;                      // 여는 괄호 없이 닫힘
        char o = s[open];
        if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{'))
            return i;                                     // 종류가 다름
    }
    long open;
    return st.pop(open) ? open : -1;                      // 닫히지 않은 괄호
}
if (a[i] == f(b)) { x(); }   OK
f(a[1)]                      error at index 5 (')')
while (x) { y(               error at index 13 ('(')
a + b) * c                   error at index 5 (')')
{[()()]}                     OK

세 번째 입력은 {와 ( 둘 다 닫히지 않았는데, 스택 맨 위에 남은 가장 안쪽 (의 위치를 가리킵니다. 스택 크기를 입력 길이로 잡았으므로 여기서는 오버플로가 날 수 없습니다.

2021년 연결 리스트 스택: 누수, 크래시, 연산마다 O(n)

2021년 글의 두 번째 예제는 std::string을 담는 노드로 스택을 만들었습니다. 맨 아래 노드(list)와 맨 위 노드(top)를 들고 있다가 새 노드를 리스트 꼬리에 붙이는 구조였는데, 측정해 보니 문제가 세 가지였습니다.

노드가 전부 누수됩니다. pop()은 맨 위 노드를 떼어 포인터를 돌려줄 뿐 아무도 delete하지 않고, 클래스에 소멸자도 없습니다. Apple Silicon macOS에서는 ASan의 누수 검사가 지원되지 않아서(detect_leaks is not supported on this platform) 시스템 도구 leaks로 확인했습니다.

$ leaks --atExit -- ./linked_stack_2021
Process 63361: 6 leaks for 288 total leaked bytes.
STACK OF 1 INSTANCE OF 'ROOT LEAK: <malloc in Stack::push(std::basic_string<char>)>'

push 6번에 누수 6건입니다.

빈 스택에서 pop하면 호출한 쪽이 죽습니다. pop()은 "스택이 비어있습니다."를 출력한 뒤 NULL인 top을 그대로 반환하고, 예제 코드는 받자마자 ->data를 읽습니다. 2021년 main 끝에 pop()을 한 번 더 넣었더니 메시지를 찍고 종료 코드 139(세그멘테이션 폴트)로 끝났습니다. ASan 출력은 이렇습니다.

ERROR: AddressSanitizer: SEGV on unknown address 0x000000000017
    #3 ... in std::operator<<(..., const std::string&) basic_ostream.h:577

push와 pop이 매번 리스트를 훑습니다. push는 맨 아래부터 꼬리까지, pop은 맨 위의 바로 아래 노드를 찾으러 다시 처음부터 돕니다. 연산 하나가 O(n)이니 N번이면 O(N²)입니다. 2021년 글은 "삽입과 제거가 복잡해져 시간이 오래 걸린다"고 했는데, 원인은 연결 리스트 자체가 아니라 꼬리에 붙이는 설계입니다. N개 push 후 N개 pop(-O2):

N 2021 꼬리 탐색 머리에 push
10,000 113.9 ms 0.218 ms
20,000 567.8 ms 0.444 ms
40,000 1,913.2 ms 0.869 ms

새 노드를 머리(head)로 만들면 됩니다. push는 head = new Node{v, head};, pop은 head를 꺼내고 head->next로 옮긴 뒤 delete. 둘 다 O(1)이고, 소멸자에서 빌 때까지 pop하면 누수도 없습니다. 노드 연결 자체는 연결 리스트 글에서 다룹니다.

실측: 배열 vs 연결 vs std::stack vs C# Stack

모든 구현에 같은 일을 시켰습니다. int 1,000만 개 push 후 1,000만 개 pop. C++는 Apple clang 21 -O2, C#은 .NET 10.0.14 Release, Apple M1 Pro, 3회 실행입니다.

막대그래프: 배열 스택 5.4ms, vector 기반 std::stack 15.6ms, deque 기반 std::stack 21.2ms, C# Stack<int> 150.4ms, 요소마다 new 와 delete 를 하는 연결 스택 260.8ms.
1,000만 번 push 한 뒤 1,000만 번 pop 한 시간, 3회 중앙값. C++ 는 Apple clang 21 -O2, C# 은 .NET 10.0.14 Release. Apple M1 Pro. 짧을수록 빠르다.
구현 1회 2회 3회
C++ ArrayStack(미리 할당) 11.1 ms 5.4 ms 5.4 ms
std::stack<int, std::vector<int>> 41.2 ms 15.6 ms 13.4 ms
std::stack<int>(deque) 26.4 ms 20.7 ms 21.2 ms
C# Stack<int> 188.7 ms 150.4 ms 136.2 ms
C++ 연결 스택(머리에 push) 353.0 ms 260.8 ms 238.7 ms

C++의 1회차가 느린 것은 새 메모리를 처음 만질 때의 페이지 폴트 때문입니다. 연결 스택은 요소마다 new와 delete를 한 번씩 하고 힙 여기저기의 메모리를 건드리지만, 배열은 연속된 주소에 씁니다. std::stack<int>는 어댑터일 뿐이라 vector를 끼우면 우리 배열 스택(+자동 확장)처럼, 기본값인 deque를 끼우면 블록 단위 할당으로 동작합니다.

C#에서는 이렇게 씁니다(.NET 10에서 실행 확인).

var s = new Stack<char>();
foreach (var c in "abcde") s.Push(c);
while (s.TryPop(out var c)) Console.Write($"{c} ");     // e d c b a
Console.WriteLine(s.TryPop(out _));                       // False
s.Pop();   // InvalidOperationException: Stack empty.

Stack<T>는 내부 배열을 알아서 늘리므로 오버플로 걱정은 없고, 남는 것은 언더플로입니다. 비어 있는 상황이 정상 흐름이라면 TryPop/TryPeek을 씁니다.

상황별 선택

상황 선택
C++ 일반 용도 std::stack<T> 또는 std::stack<T, std::vector<T>>
C++, 상한이 확실함(임베디드, 파서 깊이 제한) 오버플로·언더플로 검사를 넣은 고정 배열
상한이 없고 재할당 지연도 안 됨 머리에 push하는 연결 스택 + 소멸자
C# Stack<T> + TryPop / TryPeek
공부·면접용 구현 배열 버전을 짜고 -fsanitize=address,undefined로 돌려 보기

같은 "가득 참/비어 있음" 문제가 큐에서는 더 까다로워집니다. 순환 큐와 링크드 큐에서 이어집니다.

테스트 환경: Apple clang 21.0.0(-std=c++17/20 -Wall -Wextra, -fsanitize=address,undefined -g), macOS leaks, .NET SDK 10.0.403 / 런타임 10.0.14, Apple M1 Pro.

자주 묻는 질문

가득 찬 배열 스택에 검사 없이 push하면 어떻게 되나요?

배열 끝을 넘어서 씁니다. 일반 빌드에서는 용량 5인 스택에 6번째 push를 해도 아무 이상 없이 종료 코드 0으로 끝났고, AddressSanitizer 빌드에서는 heap-buffer-overflow(WRITE of size 1, 5바이트 영역 바로 뒤)로 멈췄습니다. 쓰기 전에 top == 용량인지 확인하고 false를 반환하거나 예외를 던져야 합니다.

연결 리스트 스택이 배열 스택보다 빠른가요?

아닙니다. push 1,000만 번 후 pop 1,000만 번에 미리 할당한 배열 스택은 5.4ms, vector 기반 std::stack은 15.6ms, deque 기반 std::stack은 21.2ms, 요소마다 new/delete를 하는 연결 스택은 260.8ms였습니다(Apple clang 21 -O2, Apple M1 Pro). 연결 스택은 상한을 정할 수 없고 재할당 지연도 허용되지 않을 때만 의미가 있습니다.

직접 만드는 대신 무엇을 쓰면 되나요?

C++에서는 std::stack(기본 deque) 또는 std::stack<T, std::vector<T>>, C#에서는 Stack<T>입니다. C#의 Pop()은 빈 스택에서 InvalidOperationException("Stack empty.")을 던지고, TryPop은 false를 반환하므로 비어 있는 경우가 정상 흐름이라면 TryPop/TryPeek을 씁니다.

  • #Stack
  • #스택
  • #C++
  • #자료구조
  • #AddressSanitizer

t.laboratory

직접 만들고 운영하는 앱·서버·서비스에서 겪은 문제와, 그 해결에 쓴 코드를 기록하는 기술 블로그입니다.

운영자 소개 · 앱

↑