Stacks in C++: Array vs Linked Implementation, Overflow, Underflow, and Balanced Parentheses

LIFO, and the restriction that buys you O(1)

A stack is a linear structure in which all insertions and deletions happen at one end, called the top. That is the whole definition. It gives you LIFO order — Last In, First Out — or equivalently FILO, First In, Last Out: the most recently added element is the first one removed, and the first one added is the last one out.

The usual picture is a stack of plates. You add a plate to the top of the pile and you take one from the top of the pile; the plate at the bottom is the one you put down first and the one you will reach last. Note what the picture does not let you do: slide a plate out of the middle. Middle elements are inaccessible. If the value you want is three down, the only way to it is to remove the two above it, and they are gone unless you kept them somewhere.

Five operations make up the interface:

The two that get confused are pop and peek, because both are about the top element. The distinguishing phrase is without removing: that is always peek/top. The other pair worth keeping apart is isEmpty and size — one answers whether, the other answers how many.

Every one of those is O(1), and that is not a coincidence you have to memorise — it is a direct consequence of the restriction. Because the only reachable position is one end, no operation ever has to shift elements along or walk the structure to find where to work. Compare an array where you may insert anywhere: inserting at the front costs O(n) because everything after it moves. Forbid that, and the cost disappears. Restricting the interface is what buys the performance.

When is a stack the right shape? Whenever the thing you need next is the thing you saw most recently:

• Function calls and recursion. Each call pushes an activation record; returning pops it. The most recent call is always the one that finishes first, which is exactly LIFO.
• Undo, and the browser Back button. Every action or visited page is pushed; undo pops the latest one.
• Bracket and tag matching. Nesting is LIFO by definition — the bracket opened most recently must be the first one closed. Covered in full below.
• Infix → postfix conversion and postfix evaluation. Operators wait on a stack until their operands are ready.
• Depth-first search, and backtracking generally. An explicit stack of unexplored branches, or the call stack doing the same job implicitly.

And the contrast that makes the definition stick: a queue is FIFO, insertions at the rear and removals at the front, two markers instead of one. Stacks reverse order; queues preserve it. Both make their middle unreachable, and both are O(1) for exactly the same reason.

The array stack: what `top` actually points at

The array implementation is a fixed buffer plus one integer. That integer is the whole design, so state precisely what it means:

top is the index of the element currently on top. An empty stack is top == -1, because > there is no valid index to point at. The stack holds top + 1 elements.

Every bug in this section comes from drifting away from that sentence. Hold it fixed and the code writes itself.

Push: advance, then write. After top = top + 1, the marker is already sitting on the slot the new element belongs in. So the store is arr[top] = value:

top = top + 1;     // move the marker to the new slot...
arr[top] = value;  // ...and write AT top, not at top + 1

Writing arr[top + 1] = value after the increment skips a slot: it leaves a hole at the real top and stores the element one place beyond where pop will look for it. The two lines compress into the idiom arr[++top] = value; — pre-increment, because the marker must move first. arr[top++] = value is the other bug in one character: it writes at the old top, overwriting the element already there.

Pop: read, then retreat — and the value must be saved first. This is the trap that costs more marks and more debugging hours than anything else on this page:

int value = arr[top];   // save the value BEFORE the marker moves
top = top - 1;
return value;           // NOT return arr[top]

By the time you reach the return, top has already moved down one. return arr[top] therefore hands back the element underneath the one you popped. Concretely: push 5, 6, 2 onto an empty stack, then run the broken version. The first pop returns 6 instead of 2, the second returns 5 instead of 6, and the third reads arr[-1] — out of bounds, undefined behaviour, and in practice no crash and no warning, just a plausible-looking number. Compiled with -Wall -Wextra it is silent. The correct version prints 2 6 5; the broken one prints 6 5 and then garbage.

The compressed idiom here is return arr[top--]; — post-decrement, because the read must happen at the old top and the decrement afterwards. So the two idioms are asymmetric on purpose: arr[++top] = value for push, return arr[top--] for pop. If you ever find yourself writing arr[top++] or arr[--top], you have them backwards.

Overflow and underflow pair one-to-one with the two boundary tests. They are not vague warnings; each is a specific condition guarding a specific operation:

Check before you act: push tests for full before incrementing, pop and peek test for empty before reading. Two spellings to get right:

• top == -1, not top = -1. The second is an assignment that empties the stack and then evaluates to -1, which is truthy — so the guard fires every time and destroys your data.
• top == MAX - 1, not top == MAX. top is an index and MAX is a count; the last valid index is one less than the count. Testing top == MAX lets one push run off the end of the array. This is the same off-by-one as writing <= where you meant < in a loop bound.

isEmpty() and the underflow test are literally the same expression, which is a useful check on your own code: if they differ, one of them is wrong.

A complete array stack in C++

Here is the whole thing, compiled and run. Two decisions in it are worth explaining before you read it.

First, pop and peek report failure through a bool return and write the value into an out-parameter, rather than returning a sentinel like -1. The textbook signature int pop() that returns -1 on an empty stack is fine right up until someone pushes -1, at which point the caller cannot distinguish a real value from a failure. If you prefer a value-returning pop, throw std::underflow_error instead — that is what the linked version below does.

Second, the guards print and return rather than crashing, which keeps the failure visible in the output. Notice in the run below that the final pop reports Stack Underflow and leaves the caller's variable untouched instead of scribbling a garbage value into it.

The program pushes 5, 6, 2, peeks, then drains. It prints:

top=2 size=3
2 6 5 Stack Underflow

2 6 5 is the push order reversed — LIFO, visible in one line of output. The loop keeps popping until pop returns false, which is why the underflow message appears at the end.

#include <iostream>

const int MAX = 100;

class ArrayStack {
public:
    ArrayStack() : top_(-1) {}

    bool isEmpty() const { return top_ == -1; }
    bool isFull()  const { return top_ == MAX - 1; }
    int  size()    const { return top_ + 1; }

    bool push(int value) {
        if (isFull()) {                       // overflow test
            std::cout << "Stack Overflow\n";
            return false;
        }
        top_ = top_ + 1;                      // move the marker first...
        data_[top_] = value;                  // ...then write AT top_, not top_ + 1
        return true;
    }

    bool pop(int& out) {
        if (isEmpty()) {                      // underflow test
            std::cout << "Stack Underflow\n";
            return false;
        }
        out = data_[top_];                    // save BEFORE moving the marker
        top_ = top_ - 1;
        return true;                          // returning data_[top_] here would be wrong
    }

    bool peek(int& out) const {
        if (isEmpty()) {
            std::cout << "Stack is empty\n";
            return false;
        }
        out = data_[top_];                    // read only; top_ does not move
        return true;
    }

private:
    int data_[MAX];
    int top_;
};

int main() {
    ArrayStack s;
    s.push(5); s.push(6); s.push(2);

    int v = 0;
    s.peek(v);
    std::cout << "top=" << v << " size=" << s.size() << "\n";   // top=2 size=3

    while (s.pop(v)) std::cout << v << ' ';                      // 2 6 5, then underflow
    std::cout << "\n";
}

The linked stack: push at the head, and free what you pop

Back the stack with a singly linked list instead and both problems with the array version go away: there is no fixed capacity, so no overflow (you are limited only by available memory), and you pay for exactly the nodes you are holding.

The design is one sentence: a linked stack is a singly linked list where insertion and deletion only ever happen at the head. top is the head pointer. Push is insert-at-beginning; pop is delete-from-beginning. Both are O(1) because the head is directly reachable — which is precisely why the head, and not the tail, is the right end to designate as the top. If you pushed at the tail of a singly linked list you would traverse the whole list on every operation.

An empty stack is top == nullptr, and that is also the underflow test.

Push, in the order that matters:

newNode->link = top;   // point the new node at the old top FIRST
top = newNode;         // then make the new node the top

Reverse those two lines and top already equals newNode when the first executes, so newNode->link = top makes the node point at itself. You get a one-element cycle, the rest of the stack is unreachable and leaked, and the next pop leaves top pointing at freed memory.

Pop, in four steps that cannot be reordered:

1. Read the value out of the top node into a local.
2. Save the node's address in a temporary (temp = top).
3. Move top down one: top = top->link.
4. delete temp.

Step 4 must come last. delete top; top = top->link; reads a member of an object that has already been destroyed — use-after-free, which in practice often returns the right answer on the first few runs and then corrupts the heap under load. That is the worst possible failure mode, and it is why the listing below is also run under AddressSanitizer. And you must actually delete: moving top without freeing leaks one node per pop, silently.

One more thing this class does that a classroom sketch usually skips. It owns raw pointers, so it needs a destructor, a copy constructor and an assignment operator. The compiler-generated copy would duplicate the top pointer, giving you two stacks sharing one chain of nodes and two destructors racing to free them. The copy constructor here rebuilds the chain in order by appending through a Node** cursor, so the copy has the same top as the original rather than a reversed one.

The program pushes 5, 6, 2, takes a copy, drains the original and shows that the copy is untouched. It prints:

top=2 size=3
265 copy_size=3
pop on empty stack

#include <iostream>
#include <stdexcept>
#include <utility>

// Invariant: top_ is the head of a singly linked list running top -> bottom.
// An empty stack is top_ == nullptr. There is no capacity, so no overflow.
class LinkedStack {
    struct Node {
        int   info;
        Node* link;
        Node(int i, Node* l) : info(i), link(l) {}
    };
    Node* top_ = nullptr;
    std::size_t count_ = 0;

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

    LinkedStack(const LinkedStack& other) {          // copy, deepest node first
        Node** tail = &top_;
        for (Node* p = other.top_; p != nullptr; p = p->link) {
            *tail = new Node(p->info, nullptr);
            tail  = &(*tail)->link;
        }
        count_ = other.count_;
    }
    LinkedStack& operator=(LinkedStack other) { swap(other); return *this; }
    LinkedStack(LinkedStack&& other) noexcept { swap(other); }

    void swap(LinkedStack& other) noexcept {
        std::swap(top_, other.top_);
        std::swap(count_, other.count_);
    }

    bool empty() const { return top_ == nullptr; }
    std::size_t size() const { return count_; }

    void push(int value) {
        Node* node = new Node(value, top_);   // link to the old top FIRST
        top_ = node;                          // then the new node becomes the top
        ++count_;
    }

    int pop() {
        if (empty()) throw std::underflow_error("pop on empty stack");
        Node* old = top_;
        int value = old->info;    // 1. read the value
        top_ = old->link;         // 2. unlink: top_ moves one node down
        delete old;               // 3. free the detached node -- never before step 2
        --count_;
        return value;
    }

    int peek() const {
        if (empty()) throw std::underflow_error("peek on empty stack");
        return top_->info;
    }

    void clear() { while (!empty()) pop(); }
};

int main() {
    LinkedStack s;
    s.push(5); s.push(6); s.push(2);
    std::cout << "top=" << s.peek() << " size=" << s.size() << "\n";  // top=2 size=3

    LinkedStack copy = s;                       // deep copy: two independent chains
    while (!s.empty()) std::cout << s.pop();    // 265
    std::cout << " copy_size=" << copy.size() << "\n";                // copy_size=3

    try { s.pop(); }
    catch (const std::underflow_error& e) { std::cout << e.what() << "\n"; }
}

Choosing between them

Every operation is O(1) in both. The table above is therefore not the interesting comparison — the constant factors and the failure modes are.

The array wins on speed. Its elements sit in one contiguous block, so the top of the stack is almost always in cache and pushing is an increment and a store. The linked stack calls new on every push and delete on every pop; allocation dominates the cost of the operation, and its nodes scatter across the heap so each pop risks a cache miss following top->link. Same O(1), routinely several times slower.

The list wins on not falling over. A fixed array turns "more input than expected" into a hard failure. If a stack overflow would be a correctness bug rather than an inconvenience, and you cannot bound the depth in advance, use the list — or use a growable array, which is the third option and usually the best one.

The third option. Back the stack with std::vector<T>: push_back and pop_back are the stack operations, capacity doubles as needed, and push becomes amortised O(1) rather than worst-case O(1) — most pushes are an increment and a store, and occasionally one copies everything into a bigger buffer. Across n pushes the copying totals O(n), so the average stays constant. You get the array's cache behaviour without the fixed ceiling. In real C++ this is what you should reach for, and std::stack gives it to you for free.

`std::stack`, and why `top()` and `pop()` are separate

For anything other than an exercise in implementing one, use the standard library. std::stack is a container adaptor: it wraps another container (a std::deque by default; std::stack<int, std::vector<int>> gives you the vector-backed version) and exposes only the stack interface — push, pop, top, empty, size, emplace. There is deliberately no way to iterate it or index into it, which is the restriction from the first section enforced by the type system.

The one thing that surprises people coming from other languages: pop() returns nothing. top() reads the top element without removing it; pop() removes it and returns void. So they always come in pairs:

int value = s.top();
s.pop();

This is not an oversight. A pop that both removed the element and returned it by value could not be exception-safe: the element has to be copied out to be returned, and if that copy throws, the element has already been removed from the container and is now lost. Splitting the operation means the read can fail without changing the container.

Two more things to know. top() on an empty stack is undefined behaviour, not an exception — std::stack does no checking, so if (!s.empty()) is your responsibility. And top() returns a reference, so s.top() = 42; legitimately modifies the top element in place.

The program below prints:

size=3 top=2
2 6 5 
empty=1

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<int> s;
    s.push(5);
    s.push(6);
    s.push(2);

    std::cout << "size=" << s.size() << " top=" << s.top() << "\n";  // size=3 top=2

    // top() reads, pop() removes and returns nothing: they always come in pairs.
    while (!s.empty()) {
        int value = s.top();
        s.pop();
        std::cout << value << ' ';
    }
    std::cout << "\nempty=" << s.empty() << "\n";                     // 2 6 5 / empty=1
}

Parentheses matching: push the index, not the bracket

Checking that brackets are balanced is the cleanest stack application there is, because the problem is LIFO: the bracket most recently opened must be the first one closed. Nesting and last-in-first-out are the same statement.

The algorithm is a single left-to-right scan:

1. Scan the expression from left to right.
2. When a left parenthesis is encountered, push its position onto the stack.
3. When a right parenthesis is encountered, pop the matching position and record the pair.
4. If a right parenthesis arrives while the stack is empty, the expression is unbalanced — there is nothing for it to close.
5. If the scan ends and the stack is not empty, the expression is unbalanced — those are opening brackets that were never closed.

Everything that is not a bracket is skipped entirely; the stack does not move. Both failure conditions are needed: check only rule 4 and ((a+b) passes; check only rule 5 and )( passes.

Why the index and not the character. For a single bracket type the character carries no information at all — anything you push is a '(', so a std::stack<char> is just an expensive counter. The position does carry information: it lets you report the pair, and more usefully it lets you point at the exact column of the bracket that has no partner. That is the difference between "unbalanced" and "unmatched ( at index 7", which is the difference between a toy and a diagnostic. So the declaration is std::stack<int>, and the push is s.push(i).

A trace. Take this expression, with indices counted from 0:

(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
0123456789...

The pairs are produced in the order the closing brackets arrive, which is not the order the opening brackets arrived:

Look at where (0, 32) lands: after (27, 31), not first. The bracket at index 0 was opened first and is therefore closed last — it sits at the bottom of the stack the whole time while five other pairs come and go above it. That ordering is the LIFO property showing up in the output, and it is the detail people get wrong when asked to list the pairs by hand: the scan is strictly left to right, and a bracket is only matched when its own closer is reached.

At the end the stack is empty, so the expression is balanced.

When a counter would do. With one bracket type you can replace the stack with an int: increment on (, decrement on ), fail if it ever goes negative, fail if it is non-zero at the end. The stack earns its place the moment you want positions, or more than one kind of bracket — with (), [] and {} a counter cannot detect ([)], because the counts balance but the nesting does not. That extension is exercise 3.

The program below prints the pair list above, then checks two broken inputs. Its output is:

pairs, in the order they close:
  (2,6)
  (1,13)
  (15,19)
  (21,25)
  (27,31)
  (0,32)
  (34,38)
balanced=1 offender=-1
(a+b)) balanced=0 offender=5
((a+b) balanced=0 offender=0

#include <iostream>
#include <stack>
#include <string>

// The plain test: is every parenthesis matched?
bool isBalanced(const std::string& expr) {
    std::stack<int> open;                       // stack<int>, not stack<char>
    for (std::size_t i = 0; i < expr.size(); ++i) {
        if (expr[i] == '(') {
            open.push(static_cast<int>(i));     // push the POSITION
        } else if (expr[i] == ')') {
            if (open.empty()) return false;     // a ')' with nothing to close
            open.pop();
        }
        // every other character is skipped; the stack does not move
    }
    return open.empty();                        // leftover '(' means unbalanced
}

// The same scan, but it prints each pair at the moment the pair closes.
void printPairs(const std::string& expr) {
    std::stack<int> open;
    for (std::size_t i = 0; i < expr.size(); ++i) {
        if (expr[i] == '(') {
            open.push(static_cast<int>(i));
        } else if (expr[i] == ')' && !open.empty()) {
            std::cout << "  (" << open.top() << "," << i << ")\n";
            open.pop();
        }
    }
}

// -1 when balanced; otherwise the index of the offending parenthesis.
int firstOffender(const std::string& expr) {
    std::stack<int> open;
    for (std::size_t i = 0; i < expr.size(); ++i) {
        if (expr[i] == '(') open.push(static_cast<int>(i));
        else if (expr[i] == ')') {
            if (open.empty()) return static_cast<int>(i);   // unmatched ')'
            open.pop();
        }
    }
    if (open.empty()) return -1;
    while (open.size() > 1) open.pop();     // the leftmost leftover sits at the bottom
    return open.top();                      // unmatched '('
}

int main() {
    const std::string expr = "(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)";
    std::cout << "pairs, in the order they close:\n";
    printPairs(expr);
    std::cout << "balanced=" << isBalanced(expr)
              << " offender=" << firstOffender(expr) << "\n";

    for (const std::string bad : {"(a+b))", "((a+b)"}) {
        std::cout << bad << " balanced=" << isBalanced(bad)
                  << " offender=" << firstOffender(bad) << "\n";
    }
}

The mistakes people actually make

Array stack

1. Writing at top + 1 after already incrementing top. Leaves a hole at the real top and stores the value where nothing will look for it. Pick one: increment then write at top, or write at top + 1 then increment. Never both.
2. return arr[top] after top-- in pop. Returns the element underneath. Save the value in a local before the decrement, or use return arr[top--];.
3. arr[top++] = value in push. Post-increment writes at the old top, overwriting the element that was already there. Push needs pre-increment; pop needs post-decrement. The asymmetry is real.
4. top == MAX as the full test. Off by one — top is an index, MAX is a count. It is top == MAX - 1, and getting it wrong writes one element past the end of the array.
5. top = -1 where you meant top == -1. Assignment inside a condition: it empties the stack, evaluates to -1, and -1 is truthy, so the guard fires unconditionally. Compilers warn about this only sometimes; write the comparison.
6. Initialising top = 0. Then an empty stack and a stack holding one element are indistinguishable. If you genuinely prefer top = 0, it has to mean "index of the next free slot", which changes push (write then increment), pop (decrement then read), size() (top, not top + 1) and both boundary tests. Both conventions work; mixing them does not. Write the one you chose in a comment above the field.
7. Returning a sentinel that is also a legal value. return -1 on underflow is unambiguous only until someone pushes -1. Use an out-parameter, an exception, or std::optional.
8. A peek() that falls off the end of the function. The common textbook version prints a message on the empty branch and then returns nothing at all — undefined behaviour. -Wall catches it (warning: control reaches end of non-void function); listen to it.

Linked stack

1. top = newNode before newNode->link = top. The new node ends up pointing at itself; the rest of the stack is orphaned. Link first, then advance.
2. delete before reading, or before moving top. delete top; top = top->link; is a use-after-free that frequently produces the correct answer in testing and corrupts the heap in production. Read, save, move, delete — in that order.
3. delete top instead of delete temp. By the time you get there, top has already moved to the next node, so this frees the node that is now the top of the stack. Every subsequent operation is undefined.
4. Moving top without deleting. One leaked node per pop, and no symptom until the process runs out of memory. A missing destructor leaks the entire remaining chain.
5. Letting the compiler copy the stack for you. The default copy duplicates one raw pointer: two objects, one node chain, double free at scope exit. Define the copy operations, or = delete them.
6. Checking for overflow in the linked version. There is no capacity to be full. If you want to be robust about allocation failure, that is a different question and new throws std::bad_alloc for it.

Parentheses matching

1. Only checking one of the two failure conditions. An empty stack on ) catches )(; a non-empty stack at the end catches ((a+b). You need both tests, and the final return s.empty() is the easiest one to leave out.
2. stack<char> where the position is what you want. Pushing '(' throws away the only useful information. Push i.
3. Popping before checking empty(). s.pop() on an empty std::stack is undefined behaviour, not an exception. The emptiness check is the unmatched-) test, so this is one line doing two jobs — do not skip it.
4. Trying to match brackets by counting when there is more than one type. ([)] has equal counts of every bracket and is still wrong. Once you have (), [] and {} you need the stack, and you need to compare the closer against the top opener rather than just popping.

Exercises with solutions

Work through each question before opening the solution below it.

#define MAX 100

class Stack {
    int arr[MAX];
    int top = 0;

public:
    bool isEmpty() { return top == -1; }
    bool isFull()  { return top == MAX; }

    void push(int value) {
        if (isFull()) { cout << "Stack Overflow"; return; }
        top = top + 1;
        arr[top + 1] = value;
    }

    int pop() {
        if (isEmpty()) { cout << "Stack Underflow"; return -1; }
        int value = arr[top];
        top = top - 1;
        return arr[top];
    }

    int peek() {
        if (!isEmpty()) return arr[top];
        cout << "Stack is empty";
    }
};

#include <iostream>
#include <stack>
#include <string>

struct Opener { char ch; int pos; };

static char closerFor(char open) {
    if (open == '(') return ')';
    if (open == '[') return ']';
    return '}';
}

// -1 when balanced; otherwise the index of the first bracket that goes wrong.
int firstError(const std::string& expr) {
    std::stack<Opener> open;
    for (std::size_t i = 0; i < expr.size(); ++i) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            open.push(Opener{c, static_cast<int>(i)});
        } else if (c == ')' || c == ']' || c == '}') {
            if (open.empty()) return static_cast<int>(i);                   // (1)
            if (closerFor(open.top().ch) != c) return static_cast<int>(i);  // (2)
            open.pop();
        }
    }
    if (open.empty()) return -1;
    while (open.size() > 1) open.pop();
    return open.top().pos;                                          // (3)
}

Related pages