C++ Stack: Overflow Checks, ASan Findings, Benchmarks

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled both C++ examples with Apple clang 21 (-Wall -Wextra, no warnings) and ran them again under AddressSanitizer and UndefinedBehaviorSanitizer. The sample main functions still print the expected output, but the classes themselves had no overflow check, no underflow check, a double free on copy, and a linked stack that leaked every node and walked the whole list on every push and pop. Below are the sanitizer reports, the fixed code, a bracket-matching example and measured timings.

This article is for anyone implementing a stack in C or C++ for a course, an interview or a parser, and for C# developers who want to know what Stack<T> does for them. In short: a stack is last in, first out (LIFO), every operation happens at one end, and the two things that go wrong are pushing onto a full stack and popping from an empty one. A preallocated array with two checks is the fastest version we measured; a linked stack is about 50 times slower and only makes sense when no upper bound exists.

What a stack is, and where it shows up

Think of a pile of plates: you add a plate on top and take the top plate off. Adding is called push, removing is pop, and reading the top without removing it is peek (the 2021 code called it getTop). Because only the top is touched, push and pop are O(1) in any reasonable implementation.

Real places you meet a stack:

• the call stack of every program (and the "stack overflow" crash when recursion goes too deep; see sorting, where quicksort crashed exactly that way),
• undo history in editors,
• bracket matching and expression parsing in compilers,
• depth-first search, which is a loop over an explicit stack.

Running the 2021 array stack under AddressSanitizer

The 2021 article showed a template class backed by new T[maxSize], with top counting the stored items. Only the #include <iostream> and using namespace std; lines were missing from the snippet; with those added, the original main (push a to e, then pop five times) compiles cleanly with clang++ -std=c++17 -Wall -Wextra and prints the same sequence as in 2021: e, d, c, b, a.

The problem is what the class does outside that happy path. push is stack[top++] = data; and pop is return stack[--top];, with no checks, and the isFull function was commented out. We wrote three small misuse tests and built them twice: plainly, and with -fsanitize=address,undefined -g.

The first two rows are the dangerous ones: without a sanitizer the program looks fine. It writes one byte past the allocation, or reads one byte before it, and carries on. The third row is the rule of three: the class owns a raw pointer but has a compiler-generated copy constructor, so two objects end up deleting the same array.

The fixed array stack

The fix adds the two checks, reports failures as a return value, and deletes copying. A peek on an empty stack throws because there is no value to return.

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;             // no double free on copy
    ArrayStack& operator=(const ArrayStack&) = delete;
    bool push(const T& v) {                              // overflow: report, don't write
        if (top_ == cap_) return false;
        data_[top_++] = v; return true;
    }
    bool pop(T& out) {                                   // underflow: report, don't read
        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_; }
};

Pushing a to f into a 5-slot stack and draining it now prints:

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

The same tests under ASan/UBSan finish without a report. Whether you return false, throw, or grow the array is a design choice; the one thing you cannot do is write anyway.

Application: bracket matching

The classic use of a stack is checking that (, [ and { are closed in the right order. Push the position of each opener; on a closer, pop and compare. A closer with nothing to pop, a wrong pair, or an opener left at the end is an error, and keeping positions lets you report where.

long check_brackets(std::string_view s) {      // -1 if balanced, else index of the problem
    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;                      // closer with no opener
        char o = s[open];
        if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{'))
            return i;                                     // wrong kind
    }
    long open;
    return st.pop(open) ? open : -1;                      // opener never closed
}

Output for five inputs:

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

Note the third case: the error points at the innermost unclosed (, because that is what is on top of the stack at the end. Sizing the stack to the input length means it can never overflow here.

The 2021 linked stack: leaks, a crash, and O(n) per operation

The second 2021 example built a stack from nodes holding a std::string. It kept a pointer to the bottom node (list) and the top node, and appended new nodes at the tail. That design has three problems we could measure.

Every node leaks. pop() unlinks the top node and returns the pointer, but nobody deletes it, and the class has no destructor. AddressSanitizer's leak checker is not supported on Apple Silicon macOS (detect_leaks is not supported on this platform), so we used the system leaks tool:

$ 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>)>'

Six pushes, six leaked nodes.

Pop on an empty stack crashes the caller. pop() prints a message and returns top, which is NULL, and the sample code immediately does ->data on the result. Adding one extra pop() to the 2021 main printed the message and then exited with code 139 (segmentation fault). Under ASan:

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

Each push and pop walks the list. To push, the code loops from the bottom node to the tail; to pop, it loops again to find the node below the top. That makes each operation O(n) and N operations O(N²). The 2021 text noted that the linked version "takes longer"; the cause is the tail insertion, not linking itself. Timings (push N, then pop N, -O2):

The fix is to make the newest node the head: head = new Node{v, head}; to push, and take head and move to head->next to pop. Both are O(1), and the destructor pops until empty so nothing is left behind. Linking nodes in general is covered in linked lists.

Measured: array vs linked vs std::stack vs C# Stack

Same workload for every version: 10 million pushes, then 10 million pops of int. C++ built with Apple clang 21 -O2, C# with .NET 10.0.14 in Release, on an Apple M1 Pro; median of three runs.

The first run of each C++ version includes page faults for fresh memory, which is why it is slower. The linked stack pays for one new and one delete per element and touches memory scattered across the heap; the array versions write consecutive addresses. std::stack<int> is only an adapter: with vector it behaves like our array (plus growth), with the default deque it allocates in blocks.

The C# equivalent, verified on .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> grows its internal array automatically, so overflow is not a concern; underflow is, and TryPop/TryPeek are the methods to use when empty is a normal case.

Which stack to use

The queue counterparts are in circular queue and linked queue, where the same two edge cases, full and empty, turn out to be harder to tell apart.

Tested with Apple clang 21.0.0 (-std=c++17/20 -Wall -Wextra, -fsanitize=address,undefined -g), macOS leaks, and .NET SDK 10.0.403 / runtime 10.0.14 on an Apple M1 Pro.