DataslopeStacks
Learn the LIFO stack ADT, std::stack, vector-backed stacks, balanced parentheses, call stacks, and stack-based string reversal
A stack is a last in, first out data structure: the most recently pushed item is the first one popped. Think of plates in a cafeteria tray stack or browser pages in a back-button history.
The stack ADT
The abstract operations are small:
| Operation | Meaning |
|---|---|
push(x) | Add x to the top |
pop() | Remove the top item |
top() | Read the top item |
empty() | Check whether the stack has no items |
std::stack<T>
std::stack is a container adapter. By default, it uses std::deque underneath and exposes only stack operations.
top() is only valid when the stack is not empty.
Implement a stack with std::vector
A vector already has the right back operations: push_back, back, and pop_back are efficient.
Stack operation costs
For std::stack backed by std::deque, push, pop, top, and empty are O(1). A vector-backed stack also gives amortized O(1) push.
Balanced parentheses
A stack is perfect when recent history matters. For parentheses, push opening brackets; when a closing bracket appears, the top must be the matching opener.
Reversing a sequence
Pushing items and popping them reverses their order.
Function call stack
Every function call needs a place to remember local variables and where to return. Recursive calls naturally form a stack.
Expression evaluation
Many parsers use stacks for operators and operands. You will see this idea again with monotonic stacks, expression parsing, and depth-first search.
Adapters limit the interface
std::stack intentionally hides iteration and random access. If you need those, use the underlying container directly, such as std::vector or std::deque.
Practice: balanced parentheses
Implement isBalanced for () [] {}. The driver prints true or false for a test string.
Practice: reverse with a stack
Push each character into a stack, then pop characters into the output string. The driver prints the reversed string.
Check your understanding
What does LIFO mean?
Lowest input, first output
Last in, first out
Linear index, fast offset
Linked item, fixed order
What is the usual time complexity of push and pop on std::stack?
O(1)
O(log n)
O(n)
O(n^2)
Why is std::deque a good default underlying container for std::stack?
It supports efficient insertion and removal at the back without requiring contiguous reallocation like a vector.
It sorts stack values automatically.
It makes top O(n).
It forbids storing characters.
Doubly Linked Lists and std::list
Learn previous and next pointers, bidirectional traversal, std::list iterators, splicing use cases, and cycle detection patterns
Queues and Deques
Learn FIFO queues, std::queue, std::deque, producer-consumer patterns, priority queue teasers, and queue-based interview patterns