Sign in to watch this lesson
Algorithms - Linear Data Structures · 4:14
Stacks
A stack pushes, pops and peeks at one end in constant time. We check brackets character by character on {[()()]}( and ([)], see why a stack is the memory of the most recent unfinished thing (calls, undo, depth-first search, postfix), and keep a running maximum beside every entry so an undo costs nothing. On this Mac we compare vector with std::stack and watch a recursive DFS crash at about 130,000 levels while an explicit stack visits a million nodes.
You will learn
- Implement a stack with a vector (push_back, back, pop_back) and explain why every operation is O(1)
- Check a bracket string with a stack: valid exactly when no closer mismatches the top and the stack ends empty, in O(n)
- Use an augmented stack of (value, max so far) to answer max queries in O(1) even after pops (undo)
- Recognise when recursion depth will overflow the call stack and replace it with an explicit stack