Stack Implementation in C, C++, Java, Python and C#: Arrays, Linked Lists and the Standard Library

Build a linked-list stack in C++ out of std::unique_ptr nodes, push a million integers, let the stack go out of scope, and the program crashes. Each node’s destructor destroys the next node, so freeing the list nests one function call per node. With g++ at -O2 and the default 8 MiB call stack on the test machine, the crash point sat between 521,962 and 522,937 nodes. A stack is one of the simplest data structures to describe, and the versions that are slightly wrong tend to pass a quick test.

This guide builds array-backed and linked-list stacks in C and C++, then in Java, Python and C#, shows each language’s standard stack, and measures what the design choices cost: memory per element, reallocations under four growth policies, and what each language does when you pop an empty stack. Every program was compiled and run for this article on Ubuntu 24.04 (x86-64): C with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17, C++ with the same compilers under -std=c++17 and -std=c++20, all with -Wall -Wextra -pedantic and no warnings; Java on OpenJDK 21 with --release 17 -Xlint:all; Python 3.11 with mypy --strict and ruff clean; and C# on the .NET 10 SDK with analyzer warnings treated as errors. The five demo programs print byte-identical output, and every output block below is captured verbatim. The code is in five GitHub repositories whose workflows run the tests on each commit, including MSVC, Windows and macOS jobs that were not run on the test machine.

What Is a Stack?

A stack is a collection that removes items in the reverse of the order they were added: last in, first out (LIFO). It has two core operations: push, which adds an item to the top, and pop, which removes and returns the top item. Most stacks also offer peek, which reads the top without removing it. All three run in O(1) time, amortized for an array that grows.

Only the top is accessible. There is no indexing into the middle and no removal from the bottom, and that restriction is the point: it makes every operation constant-time and matches problems where the most recent unfinished thing must be handled first. The stack abstract data type says nothing about storage. The two common representations are a contiguous array with a count of used slots, and a singly linked list whose head is the top.

Stack Operations and Their Time Complexity

Amortized O(1) is the one entry that needs explaining. An array stack that doubles its capacity when full does an expensive push now and then, but the expensive pushes get rarer at the same rate they get costlier. Starting from 8 slots, a million pushes trigger 17 resizes, and a copying resize moves 8 + 16 + … + 524,288 = 1,048,568 elements in total: about 1.05 moves per push. The growth program later in this guide counted exactly that figure. Growing by a fixed amount instead changes the total from linear to quadratic.

Array or Linked List: Which Should Back a Stack?

The array stores the elements themselves in one block. The linked list stores each element in its own heap node alongside a pointer to the node below. For int on x86-64 that difference is large. This is the output of src/memory.c in the C repository, which pushes a million ints into each layout and asks glibc how much heap is in use:

Output:

sizeof(Node) = 16 bytes
array stack:  4199056 bytes for 1000000 ints (capacity 1048576)
linked stack: 32000000 bytes for 1000000 ints
ratio: 7.6x

The array’s figure includes 48,576 unused slots left over from the last doubling, and the linked list still used 7.6 times as much heap. A 16-byte node became a 32-byte heap chunk because the allocator adds a header and rounds up; consecutive allocations on the test machine were 32 bytes apart. These figures belong to glibc’s allocator on one machine, not to C, which is why the build does not assert them.

For most programs the array is the better default. A linked stack earns its place when no single push may pay for a resize, when elements are large and must not move in memory, or when the nodes already exist for another reason. The comparison mirrors the wider choice between arrays in C and C++ and linked structures.

Stack Implementation in C

C has no stack type in its standard library, so both versions below are complete programs. They store int; changing the element type means changing the struct and the function signatures.

Array-Based Stack in C

/* array_stack.c - a growable array-backed stack of int, with a
 * bracket checker as a worked use case.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic array_stack.c -o array_stack
 */
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int   *items;     /* heap block holding the elements        */
    size_t size;      /* elements in use; items[size-1] is top  */
    size_t capacity;  /* elements allocated                     */
} IntStack;

void stack_init(IntStack *s)
{
    s->items = NULL;
    s->size = 0;
    s->capacity = 0;
}

void stack_free(IntStack *s)
{
    free(s->items);
    stack_init(s);
}

bool stack_is_empty(const IntStack *s)
{
    return s->size == 0;
}

/* Returns false if the stack could not grow; the stack is unchanged. */
bool stack_push(IntStack *s, int value)
{
    if (s->size == s->capacity) {
        if (s->capacity > SIZE_MAX / 2 / sizeof *s->items)
            return false;                      /* byte count would overflow */
        size_t new_cap = s->capacity ? s->capacity * 2 : 8;
        int *p = realloc(s->items, new_cap * sizeof *p);
        if (p == NULL)
            return false;                      /* old block is still valid  */
        s->items = p;
        s->capacity = new_cap;
    }
    s->items[s->size++] = value;
    return true;
}

/* Returns false on an empty stack and leaves *out untouched. */
bool stack_pop(IntStack *s, int *out)
{
    if (s->size == 0)
        return false;
    *out = s->items[--s->size];
    return true;
}

bool stack_peek(const IntStack *s, int *out)
{
    if (s->size == 0)
        return false;
    *out = s->items[s->size - 1];
    return true;
}

static int opener_for(char close)
{
    return close == ')' ? '(' : close == ']' ? '[' : '{';
}

/* Allocation failure is reported as "not balanced". */
bool balanced(const char *text)
{
    IntStack s;
    stack_init(&s);
    bool ok = true;
    for (const char *p = text; *p != '\0' && ok; ++p) {
        if (*p == '(' || *p == '[' || *p == '{') {
            ok = stack_push(&s, *p);
        } else if (*p == ')' || *p == ']' || *p == '}') {
            int open = 0;
            ok = stack_pop(&s, &open) && open == opener_for(*p);
        }
    }
    ok = ok && stack_is_empty(&s);
    stack_free(&s);
    return ok;
}

int main(void)
{
    IntStack s;
    stack_init(&s);
    int value = 0;

    printf("push 10 20 30\n");
    if (!stack_push(&s, 10) || !stack_push(&s, 20) || !stack_push(&s, 30)) {
        fputs("out of memory\n", stderr);
        stack_free(&s);
        return EXIT_FAILURE;
    }
    stack_peek(&s, &value);
    printf("size=%zu top=%d\n", s.size, value);
    while (stack_pop(&s, &value))
        printf("pop %d\n", value);
    printf("empty=%s\n", stack_is_empty(&s) ? "true" : "false");
    printf("pop on empty: %s\n",
           stack_pop(&s, &value) ? "returned a value" : "underflow reported");
    stack_free(&s);

    const char *tests[] = { "{[()()]}", "([)]", "((", "())", "" };
    for (size_t i = 0; i < sizeof tests / sizeof tests[0]; ++i)
        printf("balanced(\"%s\") = %s\n", tests[i],
               balanced(tests[i]) ? "true" : "false");
    return EXIT_SUCCESS;
}

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported
balanced("{[()()]}") = true
balanced("([)]") = false
balanced("((") = false
balanced("())") = false
balanced("") = true

Four details carry the correctness of this version:

• size and capacity are size_t, the type C uses for object sizes and counts. An int count stops at INT_MAX, well below the largest block a 64-bit allocator can return.
• The capacity check runs before the multiplication. capacity * 2 * sizeof(int) can wrap around to a small number, realloc would then succeed with a tiny block, and the next write would land far outside it. The test suite forces this case with a fake capacity near SIZE_MAX / 8.
• realloc returns into a temporary. Writing s->items = realloc(s->items, …) loses the only pointer to the old block when realloc returns NULL, leaking it along with every element on the stack.
• Empty is reported through the return value, not by returning a special int. There is no int a stack of int cannot legitimately hold, so stack_pop returns false and leaves *out untouched.

realloc(NULL, n) behaves like malloc(n), which is why a stack initialised to NULL and capacity 0 needs no separate first allocation. balanced() stores bracket characters in the same int stack; it treats an allocation failure as “not balanced”, which is the one place this program folds an error into an answer.

Linked-List Stack in C

/* linked_stack.c - a stack of int built on a singly linked list.
 * Build: gcc -std=c11 -Wall -Wextra -pedantic linked_stack.c -o linked_stack
 */
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          value;
    struct Node *next;   /* the node below this one */
} Node;

typedef struct {
    Node  *top;          /* NULL when the stack is empty */
    size_t size;
} LinkedStack;

void lstack_init(LinkedStack *s)
{
    s->top = NULL;
    s->size = 0;
}

bool lstack_is_empty(const LinkedStack *s)
{
    return s->top == NULL;
}

/* Returns false if the node could not be allocated; the stack is unchanged. */
bool lstack_push(LinkedStack *s, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return false;
    n->value = value;
    n->next = s->top;
    s->top = n;
    s->size++;
    return true;
}

/* Returns false on an empty stack and leaves *out untouched. */
bool lstack_pop(LinkedStack *s, int *out)
{
    Node *n = s->top;
    if (n == NULL)
        return false;
    *out = n->value;
    s->top = n->next;
    free(n);
    s->size--;
    return true;
}

bool lstack_peek(const LinkedStack *s, int *out)
{
    if (s->top == NULL)
        return false;
    *out = s->top->value;
    return true;
}

/* Iterative, so a million-node stack does not recurse a million deep. */
void lstack_free(LinkedStack *s)
{
    Node *n = s->top;
    while (n != NULL) {
        Node *next = n->next;
        free(n);
        n = next;
    }
    lstack_init(s);
}

int main(void)
{
    LinkedStack s;
    lstack_init(&s);
    int value = 0;

    printf("push 10 20 30\n");
    if (!lstack_push(&s, 10) || !lstack_push(&s, 20) || !lstack_push(&s, 30)) {
        fputs("out of memory\n", stderr);
        lstack_free(&s);
        return EXIT_FAILURE;
    }
    lstack_peek(&s, &value);
    printf("size=%zu top=%d\n", s.size, value);
    while (lstack_pop(&s, &value))
        printf("pop %d\n", value);
    printf("empty=%s\n", lstack_is_empty(&s) ? "true" : "false");
    printf("pop on empty: %s\n",
           lstack_pop(&s, &value) ? "returned a value" : "underflow reported");
    lstack_free(&s);
    return EXIT_SUCCESS;
}

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported

Push allocates a node, points it at the current top and makes it the new top; pop does the reverse and frees the node. That is insertion and deletion at the head of a singly linked list in C, and nothing else. lstack_free walks the list with a loop, saving next before each free, so a stack of any length is released at a fixed depth of one call. The test suite frees a million-node stack under LeakSanitizer.

Stack Implementation in C++

In C++ the growth and memory management of the C version come from the library. ArrayStack<T> keeps its elements in a std::vector, which already grows geometrically, and LinkedStack<T> owns its nodes through std::unique_ptr. Both are class templates, so they hold any element type, including move-only types such as std::unique_ptr<int>.

ArrayStack: a Class Template over std::vector

// array_stack.hpp - a stack adapter over std::vector's contiguous storage.
#ifndef MYCPLUS_ARRAY_STACK_HPP
#define MYCPLUS_ARRAY_STACK_HPP

#include <cstddef>
#include <optional>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

template <typename T>
class ArrayStack {
public:
    void push(const T& value) { items_.push_back(value); }
    void push(T&& value) { items_.push_back(std::move(value)); }

    template <typename... Args>
    T& emplace(Args&&... args)
    {
        return items_.emplace_back(std::forward<Args>(args)...);
    }

    T& top()             { require_non_empty("top"); return items_.back(); }
    const T& top() const { require_non_empty("top"); return items_.back(); }

    void pop() { require_non_empty("pop"); items_.pop_back(); }

    // Moves the top element out, or returns std::nullopt on an empty stack.
    std::optional<T> try_pop()
    {
        if (items_.empty())
            return std::nullopt;
        std::optional<T> value(std::move(items_.back()));
        items_.pop_back();
        return value;
    }

    [[nodiscard]] bool empty() const noexcept { return items_.empty(); }
    std::size_t size() const noexcept { return items_.size(); }

private:
    void require_non_empty(const char* op) const
    {
        if (items_.empty())
            throw std::out_of_range(std::string("ArrayStack::") + op +
                                    " on an empty stack");
    }

    std::vector<T> items_;
};

#endif

top() and pop() are separate, as they are in std::stack. A pop() that removed the element and then returned it by value would have nowhere to put it if the copy threw, and the element would be lost. try_pop() combines the two safely by moving the element into a std::optional before removing the slot. Unlike std::stack, both top() and pop() check for an empty stack and throw std::out_of_range; the cost is one comparison per call.

A fixed array member such as T items[10] would construct ten T objects before anything was pushed and would require T to be default-constructible. std::vector constructs an element only when it is pushed.

LinkedStack: Nodes Owned by std::unique_ptr

// linked_stack.hpp - a stack built on a singly linked list of
// std::unique_ptr-owned nodes.
#ifndef MYCPLUS_LINKED_STACK_HPP
#define MYCPLUS_LINKED_STACK_HPP

#include <cstddef>
#include <memory>
#include <optional>
#include <stdexcept>
#include <string>
#include <utility>

template <typename T>
class LinkedStack {
    struct Node {
        explicit Node(T v) : value(std::move(v)) {}
        T value;
        std::unique_ptr<Node> next;   // the node below this one
    };

public:
    LinkedStack() = default;
    ~LinkedStack() { clear(); }

    LinkedStack(const LinkedStack&) = delete;
    LinkedStack& operator=(const LinkedStack&) = delete;

    LinkedStack(LinkedStack&& other) noexcept
        : head_(std::move(other.head_)), size_(std::exchange(other.size_, 0)) {}

    LinkedStack& operator=(LinkedStack&& other) noexcept
    {
        if (this != &other) {
            clear();                  // not head_ = ...: that would recurse
            head_ = std::move(other.head_);
            size_ = std::exchange(other.size_, 0);
        }
        return *this;
    }

    void push(T value)
    {
        auto node = std::make_unique<Node>(std::move(value));  // may throw
        node->next = std::move(head_);                          // cannot throw
        head_ = std::move(node);
        ++size_;
    }

    T& top()             { require_non_empty("top"); return head_->value; }
    const T& top() const { require_non_empty("top"); return head_->value; }

    void pop()
    {
        require_non_empty("pop");
        head_ = std::move(head_->next);
        --size_;
    }

    std::optional<T> try_pop()
    {
        if (!head_)
            return std::nullopt;
        std::optional<T> value(std::move(head_->value));
        head_ = std::move(head_->next);
        --size_;
        return value;
    }

    // Unlinks one node at a time, so destroying a long stack does not
    // recurse once per node.
    void clear() noexcept
    {
        while (head_)
            head_ = std::move(head_->next);
        size_ = 0;
    }

    [[nodiscard]] bool empty() const noexcept { return !head_; }
    std::size_t size() const noexcept { return size_; }

private:
    void require_non_empty(const char* op) const
    {
        if (!head_)
            throw std::out_of_range(std::string("LinkedStack::") + op +
                                    " on an empty stack");
    }

    std::unique_ptr<Node> head_;
    std::size_t size_ = 0;
};

#endif

Three decisions in this header are easy to get wrong:

• push creates the node before touching head_. Building the node as Node{std::move(value), std::move(head_)} first moves the whole existing list into a temporary; if the allocation then throws, the temporary is destroyed and takes the list with it.
• The destructor calls clear(). Without it, the default destructor frees the list recursively, which is the crash measured in the pitfalls section below.
• Move assignment calls clear() first. A defaulted move assignment would release the old list by the same recursive path. The test suite move-assigns over a million-node stack; with = default, that test crashed.

Copying is deleted rather than implemented. A deep copy is easy to write, but a stack rarely needs one, and a deleted copy constructor turns an accidental copy into a compile error.

The C++ Demo Programs

// stack_demo.cpp - ArrayStack<int> in use, and a bracket checker on std::stack.
// Build: g++ -std=c++17 -Wall -Wextra -pedantic -Iinclude src/stack_demo.cpp -o stack_demo
#include <iostream>
#include <stack>
#include <string_view>

#include "array_stack.hpp"

bool balanced(std::string_view text)
{
    std::stack<char> open;
    for (char c : text) {
        switch (c) {
        case '(': case '[': case '{':
            open.push(c);
            break;
        case ')': case ']': case '}': {
            const char want = c == ')' ? '(' : c == ']' ? '[' : '{';
            if (open.empty() || open.top() != want)
                return false;
            open.pop();
            break;
        }
        default:
            break;
        }
    }
    return open.empty();
}

int main()
{
    ArrayStack<int> s;
    std::cout << "push 10 20 30\n";
    s.push(10);
    s.push(20);
    s.push(30);
    std::cout << "size=" << s.size() << " top=" << s.top() << '\n';
    while (auto v = s.try_pop())
        std::cout << "pop " << *v << '\n';
    std::cout << "empty=" << std::boolalpha << s.empty() << '\n';
    std::cout << "pop on empty: "
              << (s.try_pop() ? "returned a value" : "underflow reported") << '\n';

    for (std::string_view t : {"{[()()]}", "([)]", "((", "())", ""})
        std::cout << "balanced(\"" << t << "\") = " << balanced(t) << '\n';
}

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported
balanced("{[()()]}") = true
balanced("([)]") = false
balanced("((") = false
balanced("())") = false
balanced("") = true

// linked_demo.cpp - LinkedStack<int> running the same sequence.
// Build: g++ -std=c++17 -Wall -Wextra -pedantic -Iinclude src/linked_demo.cpp -o linked_demo
#include <iostream>
#include <stdexcept>

#include "linked_stack.hpp"

int main()
{
    LinkedStack<int> s;
    std::cout << "push 10 20 30\n";
    s.push(10);
    s.push(20);
    s.push(30);
    std::cout << "size=" << s.size() << " top=" << s.top() << '\n';
    while (!s.empty()) {
        std::cout << "pop " << s.top() << '\n';
        s.pop();
    }
    std::cout << "empty=" << std::boolalpha << s.empty() << '\n';
    try {
        s.pop();
        std::cout << "pop on empty: returned a value\n";
    } catch (const std::out_of_range& e) {
        std::cout << "pop on empty: underflow reported (" << e.what() << ")\n";
    }
}

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported (LinkedStack::pop on an empty stack)

std::stack, the Standard Adaptor

For production C++, use std::stack from <stack>. It is not a container of its own but an adaptor: it wraps another container and exposes only push, emplace, pop, top, empty and size. The default underlying container is std::deque; std::vector and std::list also qualify, because the adaptor needs only back(), push_back() and pop_back():

std::stack<int> a;                       // backed by std::deque<int>
std::stack<int, std::vector<int>> b;     // backed by std::vector<int>

What std::stack does not do is check for an empty stack. top() calls back() on the underlying container, and back() on an empty container is undefined behaviour. The program below pushes one value, pops it and then reads top():

// empty_top.cpp - DO NOT COPY. std::stack::top() after the last pop().
// top() calls back() on the underlying container, and back() on an empty
// container is undefined behaviour. Build with -D_GLIBCXX_ASSERTIONS to
// turn it into a checked failure on libstdc++.
#include <iostream>
#include <stack>
#include <vector>

int main()
{
    std::stack<int, std::vector<int>> s;
    s.push(42);
    s.pop();                                   // s is now empty
    std::cout << "empty() = " << std::boolalpha << s.empty()
              << ", top() = " << s.top() << '\n';
}

Output (g++ and clang++, each at -O0 and -O2, identical in all four builds, exit status 0):

empty() = true, top() = 0

The program reports that the stack is empty and then prints a value from it. AddressSanitizer shows where that value came from: READ of size 4 at an address “located 4 bytes before 4-byte region”, the slot in front of the vector’s buffer. With the default std::deque container, the same mistake on a stack that had never held anything ended in Segmentation fault (exit status 139) in the three builds tried. The same code can therefore print a plausible number or crash depending on the underlying container. libstdc++ can check the precondition for you when built with -D_GLIBCXX_ASSERTIONS:

/usr/include/c++/13/bits/stl_stack.h:234: std::stack<_Tp, _Sequence>::reference std::stack<_Tp, _Sequence>::top() [with _Tp = int; _Sequence = std::vector<int>; reference = int&]: Assertion '!this->empty()' failed.

That macro is specific to libstdc++ and adds checks throughout the library, so it belongs in debug and test builds. In release code, test empty() before calling top() or pop().

Stack Implementation in Java

Java code should reach for ArrayDeque first, but the two classes below show the mechanics and match the other languages. Both are generic and throw NoSuchElementException on an empty stack, which is what Deque.pop() throws.

import java.util.Arrays;
import java.util.NoSuchElementException;

/** A growable array-backed stack. Not thread-safe. */
public final class ArrayStack<T> {
    private static final int INITIAL_CAPACITY = 8;
    // OpenJDK's conservative "soft maximum" array length: HotSpot can refuse
    // arrays closer to Integer.MAX_VALUE even when heap is available.
    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;

    private Object[] items = new Object[INITIAL_CAPACITY];
    private int size;

    public void push(T value) {
        if (size == items.length) {
            if (size == MAX_CAPACITY) {
                throw new IllegalStateException("stack is full");
            }
            // Doubling in long arithmetic cannot wrap to a negative length.
            int newLength = (int) Math.min(2L * items.length, MAX_CAPACITY);
            items = Arrays.copyOf(items, newLength);
        }
        items[size++] = value;
    }

    public T pop() {
        T value = peek();
        items[--size] = null;   // drop the reference so the GC can reclaim it
        return value;
    }

    @SuppressWarnings("unchecked")   // only T values are ever stored
    public T peek() {
        if (size == 0) {
            throw new NoSuchElementException("pop or peek on an empty stack");
        }
        return (T) items[size - 1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}

import java.util.NoSuchElementException;

/** A stack built on a singly linked list. Not thread-safe. */
public final class LinkedStack<T> {
    private static final class Node<T> {
        final T value;
        final Node<T> next;   // the node below this one

        Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node<T> top;
    private int size;

    public void push(T value) {
        top = new Node<>(value, top);
        size++;
    }

    public T pop() {
        T value = peek();
        top = top.next;
        size--;
        return value;
    }

    public T peek() {
        if (top == null) {
            throw new NoSuchElementException("pop or peek on an empty stack");
        }
        return top.value;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

public final class StackDemo {
    static boolean balanced(String text) {
        Deque<Character> open = new ArrayDeque<>();
        for (char c : text.toCharArray()) {
            switch (c) {
                case '(', '[', '{' -> open.push(c);
                case ')', ']', '}' -> {
                    char want = c == ')' ? '(' : c == ']' ? '[' : '{';
                    if (open.isEmpty() || open.pop() != want) {
                        return false;
                    }
                }
                default -> { }
            }
        }
        return open.isEmpty();
    }

    public static void main(String[] args) {
        ArrayStack<Integer> s = new ArrayStack<>();
        System.out.println("push 10 20 30");
        s.push(10);
        s.push(20);
        s.push(30);
        System.out.println("size=" + s.size() + " top=" + s.peek());
        while (!s.isEmpty()) {
            System.out.println("pop " + s.pop());
        }
        System.out.println("empty=" + s.isEmpty());
        try {
            s.pop();
            System.out.println("pop on empty: returned a value");
        } catch (NoSuchElementException e) {
            System.out.println("pop on empty: underflow reported");
        }

        for (String t : new String[] {"{[()()]}", "([)]", "((", "())", ""}) {
            System.out.println("balanced(\"" + t + "\") = " + balanced(t));
        }
    }
}

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported
balanced("{[()()]}") = true
balanced("([)]") = false
balanced("((") = false
balanced("())") = false
balanced("") = true

ArrayStack stores its items in an Object[] and casts on the way out, because Java cannot create an array of a type parameter. The cast is safe as long as only push writes to the array, which the private field guarantees. Doubling is done in long arithmetic so that an array near 2^30 elements cannot overflow to a negative length. pop() writes null into the vacated slot; the pitfalls section shows what happens without that line.

In application code, java.util.Stack is the wrong choice. It extends Vector, whose methods are synchronized, and its own documentation says the Deque implementations “should be used in preference to this class”. Use Deque<Integer> stack = new ArrayDeque<>(); with push, pop and peek. ArrayDeque rejects null elements, so a null from peek() or poll() means the deque is empty and cannot be confused with a stored value.

Stack Implementation in Python

A Python list is already a stack: append() pushes onto the end and pop() removes from it, both amortized O(1). The Python tutorial documents exactly this use. The classes below add a named interface, a clear exception for the empty case and a linked version for comparison.

"""Two stack implementations and a bracket checker.

Run:  python3 stack.py
"""
from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


class StackUnderflowError(IndexError):
    """Raised by pop() or peek() on an empty stack."""


class ArrayStack(Generic[T]):
    """A stack backed by a Python list, whose end is the top."""

    def __init__(self) -> None:
        self._items: list[T] = []

    def push(self, value: T) -> None:
        self._items.append(value)

    def pop(self) -> T:
        if not self._items:
            raise StackUnderflowError("pop from an empty stack")
        return self._items.pop()

    def peek(self) -> T:
        if not self._items:
            raise StackUnderflowError("peek at an empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        return not self._items

    def __len__(self) -> int:
        return len(self._items)


@dataclass
class _Node(Generic[T]):
    value: T
    next: _Node[T] | None


class LinkedStack(Generic[T]):
    """A stack built on a singly linked list of nodes."""

    def __init__(self) -> None:
        self._top: _Node[T] | None = None
        self._size = 0

    def push(self, value: T) -> None:
        self._top = _Node(value, self._top)
        self._size += 1

    def pop(self) -> T:
        if self._top is None:
            raise StackUnderflowError("pop from an empty stack")
        node = self._top
        self._top = node.next
        self._size -= 1
        return node.value

    def peek(self) -> T:
        if self._top is None:
            raise StackUnderflowError("peek at an empty stack")
        return self._top.value

    def is_empty(self) -> bool:
        return self._top is None

    def __len__(self) -> int:
        return self._size


PAIRS = {")": "(", "]": "[", "}": "{"}


def balanced(text: str) -> bool:
    open_brackets: list[str] = []          # a plain list used as a stack
    for c in text:
        if c in "([{":
            open_brackets.append(c)
        elif c in PAIRS and (not open_brackets or open_brackets.pop() != PAIRS[c]):
            return False
    return not open_brackets


def main() -> None:
    s: ArrayStack[int] = ArrayStack()
    print("push 10 20 30")
    for v in (10, 20, 30):
        s.push(v)
    print(f"size={len(s)} top={s.peek()}")
    while not s.is_empty():
        print(f"pop {s.pop()}")
    print(f"empty={str(s.is_empty()).lower()}")
    try:
        s.pop()
        print("pop on empty: returned a value")
    except StackUnderflowError:
        print("pop on empty: underflow reported")

    for t in ("{[()()]}", "([)]", "((", "())", ""):
        print(f'balanced("{t}") = {str(balanced(t)).lower()}')


if __name__ == "__main__":
    main()

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported
balanced("{[()()]}") = true
balanced("([)]") = false
balanced("((") = false
balanced("())") = false
balanced("") = true

StackUnderflowError subclasses IndexError, so code that already catches IndexError from list.pop() keeps working. Keep the top at the end of the list: pop(0) and insert(0, x) shift every other element and cost O(n). collections.deque offers O(1) appends and pops at both ends, which matters only when you also need the bottom of the stack; queue.LifoQueue is the stack to use when one thread pushes and another pops, because its methods lock.

LinkedStack is here to mirror the other languages. In CPython each node is a separate object with its own header, and the list version is shorter, uses less memory and is the one to use.

Stack Implementation in C#

.NET ships System.Collections.Generic.Stack<T>, which Microsoft documents as “implemented as an array”. The versions below show the same structure written out, with TryPop following the framework’s naming pattern.

using System;

namespace MyCPlus.Stack;

/// <summary>A growable array-backed stack. Not thread-safe.</summary>
public sealed class ArrayStack<T>
{
    private T[] _items = new T[8];
    private int _size;

    public int Count => _size;
    public bool IsEmpty => _size == 0;

    public void Push(T value)
    {
        if (_size == _items.Length)
        {
            // Doubling in long arithmetic cannot wrap; Array.MaxLength caps it.
            int newLength = (int)Math.Min(2L * _items.Length, Array.MaxLength);
            if (newLength == _size)
                throw new InvalidOperationException("Stack is full.");
            Array.Resize(ref _items, newLength);
        }
        _items[_size++] = value;
    }

    public T Pop()
    {
        T value = Peek();
        _items[--_size] = default!;   // drop the reference so the GC can reclaim it
        return value;
    }

    public T Peek()
    {
        if (_size == 0)
            throw new InvalidOperationException("Pop or Peek on an empty stack.");
        return _items[_size - 1];
    }

    public bool TryPop(out T value)
    {
        if (_size == 0)
        {
            value = default!;
            return false;
        }
        value = Pop();
        return true;
    }
}

using System;

namespace MyCPlus.Stack;

/// <summary>A stack built on a singly linked list. Not thread-safe.</summary>
public sealed class LinkedStack<T>
{
    private sealed class Node(T value, Node? next)
    {
        public T Value { get; } = value;
        public Node? Next { get; } = next;   // the node below this one
    }

    private Node? _top;

    public int Count { get; private set; }
    public bool IsEmpty => _top is null;

    public void Push(T value)
    {
        _top = new Node(value, _top);
        Count++;
    }

    public T Pop()
    {
        T value = Peek();
        _top = _top!.Next;
        Count--;
        return value;
    }

    public T Peek()
    {
        if (_top is null)
            throw new InvalidOperationException("Pop or Peek on an empty stack.");
        return _top.Value;
    }
}

using System;
using System.Collections.Generic;

namespace MyCPlus.Stack;

public static class Program
{
    public static bool Balanced(string text)
    {
        var open = new Stack<char>();
        foreach (char c in text)
        {
            switch (c)
            {
                case '(' or '[' or '{':
                    open.Push(c);
                    break;
                case ')' or ']' or '}':
                    char want = c == ')' ? '(' : c == ']' ? '[' : '{';
                    if (!open.TryPop(out char top) || top != want)
                        return false;
                    break;
            }
        }
        return open.Count == 0;
    }

    public static void Main()
    {
        var s = new ArrayStack<int>();
        Console.WriteLine("push 10 20 30");
        s.Push(10);
        s.Push(20);
        s.Push(30);
        Console.WriteLine($"size={s.Count} top={s.Peek()}");
        while (s.TryPop(out int v))
            Console.WriteLine($"pop {v}");
        Console.WriteLine($"empty={(s.IsEmpty ? "true" : "false")}");
        Console.WriteLine("pop on empty: " +
            (s.TryPop(out _) ? "returned a value" : "underflow reported"));

        foreach (string t in new[] { "{[()()]}", "([)]", "((", "())", "" })
            Console.WriteLine($"balanced(\"{t}\") = {(Balanced(t) ? "true" : "false")}");
    }
}

Output:

push 10 20 30
size=3 top=30
pop 30
pop 20
pop 10
empty=true
pop on empty: underflow reported
balanced("{[()()]}") = true
balanced("([)]") = false
balanced("((") = false
balanced("())") = false
balanced("") = true

The three files build as one console project (dotnet new console, then replace Program.cs). LinkedStack‘s Node uses a primary constructor, which needs C# 12 or later; the .NET 8 SDK and newer provide it. As in Java, Pop() overwrites the vacated slot with default so the garbage collector can reclaim a popped object, and Array.MaxLength caps growth at the largest array the runtime allows. Stack<T> is not thread-safe; ConcurrentStack<T> in System.Collections.Concurrent is the shared-access version.

What Happens When You Pop an Empty Stack?

Underflow is the edge case every stack has to decide, and the languages decide it differently. Each row below was run on the test machine; the right-hand column is the program’s own output or return value.

Two designs recur. Most APIs raise an error, and most also offer a non-throwing variant (poll/peek in Java, TryPop in C#, try_pop here) for code where empty is an expected state rather than a bug. C++’s std::stack is the exception: it leaves the check to the caller, and the price of forgetting is undefined behaviour that may look like a working program.

How Growth Strategy Changes the Cost of Push

src/growth.c pushes a million ints under four growth policies, starting from 8 slots, and counts the resizes and the elements a copying reallocation must move:

Output:

policy       resizes  elements moved   per push  final cap
+16            62500     31250000000   31250.00    1000008
+1024            977       488226440     488.23    1000456
x1.5              29         2010617       2.01    1005310
x2                17         1048568       1.05    1048576

Both extremes match the arithmetic. Doubling from 8 moves 8 + 16 + … + 524,288 = 1,048,568 elements, the geometric sum. Growing by 16 slots resizes (1,000,008 − 8) / 16 = 62,500 times and moves 31,250,000,000 elements, about 31,000 per push. Growing by 1,024 slots only divides the quadratic cost by a constant. Growing by 1.5 moves roughly twice as much as doubling but leaves less unused capacity.

The C program itself is a poor timing benchmark, and the reason is worth knowing. All four policies together ran in 15 to 17 ms over two runs, because glibc’s realloc can extend or remap a large block rather than copy it: strace -c counted 912 mremap calls across the whole run. The “elements moved” column is the work done by runtimes that cannot resize in place. std::vector allocates a new buffer and moves each element, Java’s Arrays.copyOf and C#’s Array.Resize copy into a new array, and none of them can use realloc.

The standard containers choose their own policy. The same million pushes, counted with each container’s capacity:

std::vector starts at capacity 0 and Stack<int> at 4 on its first push, which accounts for the 21 and 19; both double from there. CPython’s list grows by roughly an eighth, so it reallocates more often and over-allocates less; the count came from watching sys.getsizeof() change. These are implementation details that change between versions, and the C++ standard leaves the growth factor to each library. When you know the final size, reserve it up front: reserve() for std::vector, EnsureCapacity() for Stack<T>.

Four Ways a Stack Passes a Quick Test and Still Fails

Each of these works in the demo that a first test usually runs: push a few values, pop them, print the result.

1. A Sentinel Value That Means “Empty”

Returning 0, -1 or NULL from pop() on an empty stack looks convenient until a caller pushes that value.

// null_sentinel.cpp - DO NOT COPY. A pop() that returns NULL to mean "empty".
// std::endl flushes each line so it survives the abort at the end.
#include <iostream>
#include <string>

template <typename T>
struct FixedStack {
    T items[10];
    int top = -1;
    void push(const T& v) { items[++top] = v; }
    T pop()
    {
        if (top == -1)
            return NULL;                  // the "empty" marker
        return items[top--];
    }
};

int main()
{
    FixedStack<int> a;
    a.push(0);
    std::cout << "int: pop after push(0) = " << a.pop() << std::endl;
    std::cout << "int: pop on empty      = " << a.pop() << std::endl;
    FixedStack<std::string> b;
    std::cout << "string: pop on empty   = " << b.pop() << std::endl;
}

Output (g++ 13.3, -std=c++17, exit status 134):

int: pop after push(0) = 0
int: pop on empty      = 0
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string: construction from null is not valid

For int, an empty stack and a stored zero are indistinguishable. For std::string, return NULL compiled in C++17 with no warning for that instantiation (g++ warned only about the int one) and aborted at run time. Under -std=c++23 the same file fails to compile, because C++23 deletes the std::string constructor that takes nullptr:

error: use of deleted function 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(std::nullptr_t) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::nullptr_t = std::nullptr_t]'

Report empty through a separate channel: a bool and an out-parameter in C, an exception or std::optional in C++, an exception or a Try… method in Java and C#.

2. Growth Arithmetic That Can Overflow

In C, capacity * 2 * sizeof(int) is unsigned arithmetic, and unsigned arithmetic wraps without an error. Deleting the two-line guard from stack_push and running the test suite’s overflow case under UndefinedBehaviorSanitizer produced this (line 46 is the write s->items[s->size++] = value in the file without the guard):

tests/../src/array_stack.c:46:13: runtime error: pointer index expression with base 0x502000000010 overflowed to 0x8000502000000010

The wrapped size had been passed to realloc, which succeeded with a small block, and the write then computed an address far outside it. Without the sanitizer the same test ended in Segmentation fault at both -O0 and -O2. The Java and C# versions avoid the same trap by doubling in 64-bit arithmetic and capping the result.

3. A Popped Object That Is Still Referenced

In a garbage-collected language, an array stack that only decrements its index on pop() leaves the popped object’s reference in the array. The object stays reachable and cannot be collected until that slot is overwritten. This program pushes a 64 MiB array onto each kind of stack, pops it, and asks the collector to run:

import java.lang.ref.WeakReference;
import java.util.Arrays;

/** DO NOT COPY LoiteringStack. Its pop() lowers the index but leaves the
 *  reference in the array, so a popped object stays reachable. */
public final class Loitering {
    static final class LoiteringStack<T> {
        private Object[] items = new Object[8];
        private int size;

        void push(T value) {
            if (size == items.length) {
                items = Arrays.copyOf(items, items.length * 2);
            }
            items[size++] = value;
        }

        @SuppressWarnings("unchecked")
        T pop() {
            return (T) items[--size];      // the slot still holds the reference
        }
    }

    // Each helper pushes a 64 MiB array and pops it. The array is allocated
    // here, so no local variable in the caller refers to it afterwards.
    static WeakReference<byte[]> pushAndPop(ArrayStack<byte[]> s) {
        byte[] big = new byte[64 << 20];
        s.push(big);
        s.pop();
        return new WeakReference<>(big);
    }

    static WeakReference<byte[]> pushAndPop(LoiteringStack<byte[]> s) {
        byte[] big = new byte[64 << 20];
        s.push(big);
        s.pop();
        return new WeakReference<>(big);
    }

    static boolean reclaimed(WeakReference<byte[]> watch) {
        for (int i = 0; i < 10 && watch.get() != null; i++) {
            System.gc();
        }
        return watch.get() == null;
    }

    public static void main(String[] args) {
        ArrayStack<byte[]> good = new ArrayStack<>();
        LoiteringStack<byte[]> bad = new LoiteringStack<>();
        WeakReference<byte[]> a = pushAndPop(good);
        WeakReference<byte[]> b = pushAndPop(bad);
        // Both stacks are still in use here; only the popped arrays differ.
        System.out.println("slot cleared on pop: reclaimed=" + reclaimed(a)
                + ", stack size " + good.size());
        System.out.println("slot left in array:  reclaimed=" + reclaimed(b)
                + ", stack size " + bad.size);
    }
}

Output:

slot cleared on pop: reclaimed=true, stack size 0
slot left in array:  reclaimed=false, stack size 0

Both stacks report size 0, but the one that did not clear its slot still holds 64 MiB. System.gc() is a request, not a command; the result above was the same in all ten runs made for this article, across the Serial, Parallel, G1 and ZGC collectors and the interpreter-only mode. The one-line fix is the items[--size] = null in ArrayStack.pop(), and C#’s _items[--_size] = default! does the same job. C and C++ have no equivalent problem for int, and std::vector::pop_back() destroys the element.

4. Destroying a Linked Stack Recursively

This is the crash from the introduction. A node that owns the next node through std::unique_ptr pushes and pops correctly; the problem is destruction:

// recursive_destructor.cpp - DO NOT COPY. A linked stack that relies on the
// default destructor: each unique_ptr destroys the next node from inside its
// own destructor, so freeing N nodes nests N calls deep.
#include <cstdio>
#include <cstdlib>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main(int argc, char** argv)
{
    const int n = argc > 1 ? std::atoi(argv[1]) : 1'000'000;
    std::unique_ptr<Node> head;
    for (int i = 0; i < n; ++i)
        head = std::make_unique<Node>(Node{i, std::move(head)});
    std::printf("built %d nodes; destroying\n", n);
    std::fflush(stdout);
    head.reset();                 // recursion one frame per node
    std::puts("destroyed");
    return EXIT_SUCCESS;
}

Output (g++ 13.3, -O2):

built 1000000 nodes; destroying
Segmentation fault

Under AddressSanitizer the report names the cause: ERROR: AddressSanitizer: stack-overflow. How many nodes fit before the crash depends on the size of each destructor’s stack frame, which depends on the compiler and optimization level. Bisecting the node count with the default 8 MiB stack on the test machine:

Optimization moved the limit by a factor of nine; it did not remove it. A test with a thousand nodes passes in all three builds. The fix is the loop in LinkedStack::clear(), which detaches one node at a time; the tests destroy and move-assign million-node stacks with it, and a ten-million-node stack was destroyed without error while writing this article. The C version has the same shape: lstack_free loops instead of recursing. CPython, for comparison, deleted a 3,000,000-node LinkedStack in 0.12 s without error, because the interpreter defers deeply nested deallocations instead of recursing through them.

Where Stacks Are Used

• Function calls. Each call pushes a frame holding arguments, locals and a return address, and each return pops it. That call stack is finite, which is why the recursive destructor above crashes and why unbalanced partitions can overflow it in a naive quicksort.
• Bracket and syntax matching. The balanced() function in the demos above is the core of how a parser checks that (, [ and { close in the right order: push each opener, and pop and compare on each closer.
• Expression evaluation. A postfix expression such as 3 4 + 2 * evaluates with one stack of operands. Dijkstra’s shunting-yard algorithm uses a stack of operators to convert infix to postfix first.
• Undo and redo. Each edit is pushed onto an undo stack; undoing pops it and pushes it onto a redo stack, and a new edit clears the redo stack.
• Depth-first search and backtracking. Replacing recursion with an explicit stack moves the pending work from the call stack to the heap, where its size is limited by memory rather than by the thread’s stack size.

Key Takeaways

• A stack is LIFO: push, pop and peek work only at the top, and each runs in O(1) time, amortized when an array has to grow.
• Back a stack with an array by default. For a million ints the array used 4.2 MB against the linked list’s 32 MB.
• Grow geometrically. Doubling moved 1,048,568 elements for a million pushes; growing by 16 slots would move 31.25 billion.
• Report an empty stack through a separate channel, never a sentinel value. 0 is indistinguishable from a stored zero, and NULL aborted a std::string stack at run time.
• std::stack::top() on an empty stack is undefined behaviour. It printed 0 in four builds and crashed in three others; check empty() first.
• In Java and C#, clear the slot on pop, or the popped object stays reachable.
• Free linked nodes in a loop. Recursive destruction crashed between about 58,000 and 523,000 nodes, depending on the build.

Frequently Asked Questions

Conclusion

The stack is small enough to write in an afternoon in any of these languages, and that is why it is worth writing carefully once. The interesting decisions are the ones a quick test does not exercise: what an empty pop reports, how the array grows, whether a popped object is released, and whether destruction recurses. Each of them showed up here as a measured number or a captured message rather than a warning in prose.

In production code, prefer the library: std::stack or std::vector in C++, ArrayDeque in Java, a list in Python and Stack<T> in C#, with a hand-written array stack as the reasonable choice in C. Queues, deques and priority queues build on the same ideas, and the data structures section is where the next of them will appear.

Source Code and Tests

All the code on this page, with its tests, is in one directory per language:

Language	Repository directory	Build
C	mycplus/c-examples › data-structures/stack
C++	mycplus/cpp-examples › data-structures/stack
Java	mycplus/java-examples › data-structures/stack
Python	mycplus/python-examples › data-structures/stack
C#	mycplus/csharp-examples › data-structures/stack

The C and C++ examples build with CMake:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

Java runs with javac --release 17 -Xlint:all -Werror -d build src/*.java tests/*.java pitfalls/*.java followed by java -ea -cp build StackTest; Python with python3 -m unittest discover -s tests; C# with dotnet build Stack.slnx -c Release followed by dotnet run --project tests/StackTests -c Release --no-build.

What a green badge means, exactly:

• C: compiles with GCC and Clang under C11 and C17 and with MSVC /W4 /WX, warnings as errors; both stacks agree with a reference model over 200,000 random operations; the capacity-overflow guard, empty-stack results and 100,000-deep bracket nesting are tested; the tests and demos run clean under AddressSanitizer, UndefinedBehaviorSanitizer and LeakSanitizer; each demo prints the output shown above byte for byte.
• C++: compiles with g++ and clang++ under C++17 and C++20 and with MSVC /W4 /WX /permissive-; both stacks agree with std::stack<std::string> over 100,000 random operations and hold move-only types; million-node stacks are destroyed, cleared and move-assigned; and the three pitfall programs are confirmed to fail the way this page says.
• Java: Temurin 17, 21 and 25 on Linux and Windows; tests against ArrayDeque; the demo output; and the reclaimed/not-reclaimed result above.
• Python: 3.10 to 3.14 on Linux and Windows; ruff and mypy --strict; tests against a plain list; the demo output.
• C#: .NET 10 on Linux, Windows and macOS with analyzer warnings as errors; tests against Stack<T>; the demo output.

The builds do not check the memory figures, the reallocation counts in the cross-runtime table or any timing. Those came from one machine and would vary on another, so the page states them as measured there.