Stacks with an Array
Last in, first out. The stack ADT (push, pop, peek, isEmpty, isFull) built on a fixed array with a top index, plus overflow and underflow.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Think of a stack of plates in the cafeteria. You put a clean plate on top, and you take a plate from the top. The plate at the bottom was put there first and comes out last. That rule is LIFO: Last In, First Out.
A stack is an ADT: it is defined by its operations, not by how it is stored.
| Operation | Meaning |
|---|---|
push(x) | put x on top |
pop() | remove and return the top item |
peek() / top() | look at the top item without removing it |
isEmpty() | is there nothing on the stack? |
isFull() | no room left (array version only) |
Building it on an array
Keep an array st[MAX] and one integer top, the index of the top item. An empty stack has top = -1.
- push:
st[++top] = x;moves top up, then writes. - pop:
return st[top--];reads, then moves top down.
The old value stays in the array after a pop, but it no longer counts. Only 0..top is the stack.
Overflow and underflow
- Overflow: push when
top == MAX - 1. The array has no room. - Underflow: pop when
top == -1. There is nothing to take.
Always check before you act. These two checks are the most common exam marks on this topic.
Where stacks show up
Undo/redo, the browser back button, checking balanced brackets, evaluating postfix expressions, and the call stack that makes recursion work (Chapter 3).
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Push until isFull() is true, then push once more to see overflow. Pop everything and pop again for underflow.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
const int MAX = 5;
class Stack {
int st[MAX];
int top = -1;
public:
bool isEmpty() const { return top == -1; }
bool isFull() const { return top == MAX - 1; }
void push(int x) {
if (isFull()) { cout << "Overflow! cannot push " << x << "\n"; return; }
st[++top] = x;
}
int pop() {
if (isEmpty()) { cout << "Underflow!\n"; return -1; }
return st[top--];
}
int peek() const {
if (isEmpty()) { cout << "Empty!\n"; return -1; }
return st[top];
}
};
int main() {
Stack s;
for (int i = 1; i <= 6; i++) s.push(i * 10); // the 6th push overflows
cout << "peek: " << s.peek() << "\n";
cout << "pop: ";
while (!s.isEmpty()) cout << s.pop() << " ";
cout << "\n";
s.pop(); // underflow
}Overflow! cannot push 60 peek: 50 pop: 50 40 30 20 10 Underflow!
05Complexity
| push | O(1) |
|---|---|
| pop | O(1) |
| peek / isEmpty / isFull | O(1) |
| search for a value | O(n): not a stack operation |
| Extra space | O(MAX), fixed when the array is declared |
Every stack operation touches only st[top], so all of them are O(1). The price of an array is a fixed capacity.
06Watch
Introduction to stack
Why this one: The stack ADT and LIFO idea with everyday examples, before any code.
Array implementation of stacks
Why this one: Builds the array stack in C/C++ with a `top` index, exactly like this page.
Original class slides (Python, by the course's lecture authors):Stacks, Queues and Monotonicity
07Exam lens
Likely questions
- Define a stack. Why is it called a LIFO structure?
- Write push and pop for an array stack, including overflow and underflow checks.
- Show the stack after: push 3, push 7, pop, push 2, push 9, pop. What does peek return?
- What does
top = -1mean? What is the condition for a full stack? - Give three real applications of a stack.
Common mistakes
- Writing
st[top++] = xwithtop = -1(writes to index −1). Usest[++top] = x. - Popping without checking
isEmpty()(underflow). - Pushing without checking
isFull()(writes past the array). - Thinking
popmust erase the value. Movingtopdown is enough.
08Quick check
09Practice
🟢 Trace by hand
MAX = 3. Do push 5, push 2, push 8, push 1, pop, pop, peek, pop, pop. Write the array, top, and anything printed after each step.
Show answer
- push 5 →
[5], top 0 - push 2 →
[5,2], top 1 - push 8 →
[5,2,8], top 2 (now full) - push 1 → Overflow, nothing changes
- pop → returns 8, top 1
- pop → returns 2, top 0
- peek → 5
- pop → returns 5, top −1
- pop → Underflow
🟡 Implement it
Use your array stack to reverse a string, and to print a number in binary (push n % 2, then pop everything).
Hint
Push every character, then pop them all. The last one in is the first one out, so the order flips.
Solution
string reverseStr(const string& s) {
char st[100]; int top = -1;
for (char c : s) st[++top] = c;
string r;
while (top != -1) r += st[top--];
return r;
}🔴 Solve problems
Hint
Push opening brackets. On a closing bracket the top must be its partner. At the end the stack must be empty.
Hint
Build each string with a stack.
#means pop (if not empty). Compare the results.Hint
Numbers are pushed. An operator pops b, then a, and pushes a op b. Order matters for − and /.
Solution idea
for (auto& t : tokens) { if (t is an operator) { int b = s.top(); s.pop(); int a = s.top(); s.pop(); s.push(apply(a, t, b)); } else s.push(stoi(t)); } return s.top();
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.