Linear Data Structures
Stacks
A Last-In-First-Out (LIFO) collection: push and pop happen only at the top.
1Introduction
A stack restricts access to a single end. That restriction is exactly what makes it useful: it naturally remembers 'the most recent unfinished thing', which is how function calls, undo and nested brackets work.
2What is it?
A stack is a linear collection with two main operations: push (add to the top) and pop (remove from the top). peek returns the top without removing it. The last element pushed is the first one popped — LIFO.
3Why do we use it?
- O(1) push, pop and peek.
- Models nested structure: function calls, parentheses, HTML tags.
- Turns recursion into iteration (explicit stack).
- Supports undo/redo and backtracking.
4Real-world examples
- A stack of plates.
- Browser back button.
- Undo in a text editor.
- The program call stack.
5Internal working
Array-based stacks keep an index `top`; push writes at top + 1, pop reads at top and decrements it.
Linked-list stacks push and pop at the head node.
With a fixed capacity, push on a full stack is an overflow; pop on an empty stack is an underflow.
6Memory representation
Array-backed stack with capacity 4 after push 10, push 20, push 30:
index value
3 | |
2 | 30 | <- top (index 2)
1 | 20 |
0 | 10 |
+-------+7Operations
| Operation | How it works |
|---|---|
| push(x) | Place x on top. |
| pop() | Remove and return the top. |
| peek() | Read the top. |
| isEmpty() | Check size = 0. |
| search(x) | Not a stack operation — needs O(n) scan. |
8Visual explanation
Size 0 / 3 · LIFO — the last value pushed is the first one popped
A stack is Last-In-First-Out (LIFO): push adds to the top, pop removes from the top. A fixed capacity shows overflow (push when full) and underflow (pop when empty).
9Code implementation
Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.
class Stack {
constructor(capacity) {
this.items = [];
this.capacity = capacity;
}
push(value) {
if (this.items.length === this.capacity) {
console.log("Stack Overflow: cannot push " + value);
return;
}
this.items.push(value);
}
pop() {
if (this.items.length === 0) {
console.log("Stack Underflow: nothing to pop");
return null;
}
return this.items.pop();
}
}
const stack = new Stack(3);
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
console.log("Popped:", stack.pop());
console.log("Popped:", stack.pop());
console.log("Popped:", stack.pop());
console.log("Popped:", stack.pop());
console.log("Final stack (bottom -> top):", stack.items);
10Time complexity
| Operation | Time |
|---|---|
| push(x) | O(1)* |
| pop() | O(1) |
| peek() | O(1) |
| isEmpty() | O(1) |
| search(x) | O(n) |
11Space complexity
A stack holding n elements uses O(n) space. *Dynamic-array stacks occasionally resize (O(n) for that push) but are O(1) amortized.
12Advantages
- Constant-time operations.
- Simple to implement with an array or a list.
- Matches recursive/nested problems perfectly.
13Disadvantages
- Only the top is accessible.
- Fixed-capacity stacks can overflow.
- Deep recursion can overflow the call stack.
14Common mistakes
- Popping or peeking without checking for empty (underflow).
- Using a queue where LIFO order is needed (or vice versa).
- In JavaScript, using shift/unshift (O(n)) instead of push/pop.
- Forgetting that recursion depth is limited (stack overflow).
15Interview questions
16Practice exercises
- Implement a min-stack with O(1) getMin.
- Evaluate a postfix (RPN) expression.
- Next greater element for every array item.
- Reverse a string using a stack.
- Convert infix to postfix (shunting-yard).
Try them in the Coding Playground.