This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Stack
Knowledge Summary
Definition of a Stack
A stack is a linear data structure with the last in, first out (LIFO) property.
Insertion (push) and deletion (pop) can only be performed at the top of the stack.
Basic Operations
| Operation | Meaning | Time Complexity |
|---|---|---|
push(x) | Push into the stack | O(1) |
pop() | Pop from the stack | O(1) |
top() | View the top element | O(1) |
empty() | Whether the stack is empty | O(1) |
size() | Number of elements | O(1) |
C++ STL Stack
1#include <stack>
2stack<int> s;
3s.push(1);
4s.push(2);
5s.push(3);
6cout << s.top(); // 3
7s.pop();
8cout << s.top(); // 2Applications of Stacks
- Bracket matching: push left brackets onto the stack, and match right brackets with the top
- Expression evaluation: infix-to-postfix conversion and postfix evaluation
- Function call stack: the implementation principle of recursion
- Base conversion: use a stack to record remainders
Pop Sequence Problems (Frequently Tested)
If n elements are pushed into a stack in order, the number of valid pop sequences is the Catalan number C(2n, n) / (n+1).
For example, when 3 elements are pushed, there are 5 valid pop sequences.
How to determine whether a pop sequence is valid: simulate the push and pop process. If the process can be completed, the sequence is valid.