C++UCS301
Linear Data StructuresC++17

Stacks

A stack is a LIFO abstract data type used for recursion, parsing, undo systems, expression evaluation, and depth-first search.

Open this in the visual lab

What to understand

  • push, pop, and top
  • Array and linked implementations
  • Overflow and underflow
  • Expression applications

Remember this

  1. 1Last in, first out
  2. 2All core operations are O(1)
  3. 3Function calls use a runtime stack
  4. 4std::stack is an adaptor

Detailed notes

A stack exposes only the most recently inserted element. Restricting access creates a strong LIFO invariant that naturally mirrors nested structure and backtracking.

Array stacks track a top index and have excellent locality; linked stacks grow node by node. std::stack is an adaptor, usually over deque, and deliberately provides no iteration.

How it works

  1. 1Push at the single designated top.
  2. 2Check underflow before top or pop.
  3. 3For expression parsing, define operator precedence and associativity.
  4. 4Use a stack frame or explicit stack to replace recursion when needed.

Worked trace

Evaluate postfix 5 2 + 3 ×

Tokens: 5, 2, +, 3, ×
  1. 1Push 5, then push 2.
  2. 2Pop 2 and 5; compute 5+2=7; push 7.
  3. 3Push 3.
  4. 4Pop 3 and 7; compute 7×3=21; push 21.
Result: Top of stack = 21

Where it is used

  • Function calls and recursion
  • Balanced delimiters and expression evaluation
  • Undo, DFS, and backtracking

Common mistakes

  • Reading top after popping the final item
  • Reversing operand order for subtraction or division
  • Using recursion on depth that can overflow the call stack

Complexity analysis

OperationBestAverageWorstExtra space
pushO(1)O(1)O(1)O(1)
popO(1)O(1)O(1)O(1)
topO(1)O(1)O(1)O(1)
searchO(n)O(n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Fixed-capacity array stack

The top index denotes the next free slot, which makes size and empty checks simple.

#include <stdexcept>
using namespace std;

template <typename T, int Capacity>
class Stack {
    T data[Capacity];
    int count = 0;
public:
    bool empty() const { return count == 0; }
    int size() const { return count; }
    void push(const T& value) {
        if (count == Capacity) throw overflow_error("stack full");
        data[count++] = value;
    }
    void pop() {
        if (empty()) throw underflow_error("stack empty");
        --count;
    }
    T& top() {
        if (empty()) throw underflow_error("stack empty");
        return data[count - 1];
    }
};
23 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.