UNIT 06Prerequisite: Units 02 + 0560 min read
A stack is not a new data structure built from scratch — it is an array or linked list with one strict rule imposed on top: you can only add and remove from one end. That rule — as simple as it sounds — makes stacks incredibly useful for a whole class of problems.
Every time you press Ctrl+Z to undo, every time your browser goes back a page, every time a function calls another function — a stack is working underneath. In this unit we build stacks two ways, learn all four operations, and solve the classic problems that make stacks a staple of every coding interview.
// Section 1
What is a Stack?
A stack follows the LIFO principle — Last In, First Out. The last item you put in is the first one you get out. Think of a stack of plates in a canteen: you always place a new plate on top, and you always take from the top. You never reach into the middle.
🍽️ The plate stack — LIFO in action
PUSH — add to top
← TOP 40 added
40
30
20
10
BOTTOM
POP — remove from top
← TOP 40 removed
30
20
10
BOTTOM
push(x)
Add element x to the top of the stack
O(1)pop()
Remove and return the top element
O(1)peek()
Read the top element without removing it
O(1)isEmpty()
Check if the stack has no elements
O(1)💡 Note
All four stack operations are O(1). This is the stack's biggest strength. No matter how many items are in the stack — 10 or 10 million — every push, pop, peek, and isEmpty check takes the same constant time.
// Section 2
Stack Using an Array
The simplest way to implement a stack is using an array. We keep an integer called top that always tracks the index of the topmost element. It starts at -1 (empty stack). Push increments top and places the value. Pop reads the value and decrements top.
#include <stdio.h>
#define MAX 100 /* maximum capacity of our stack */
/* stack structure — array + top index */
struct Stack {
int data[MAX];
int top;
};
typedef struct Stack Stack;
/* initialise: top = -1 means the stack is empty */
void initStack(Stack *s) {
s->top = -1;
}
/* isEmpty: true if top is still -1 */
int isEmpty(Stack *s) {
return s->top == -1;
}
/* isFull: true if top has reached the last index */
int isFull(Stack *s) {
return s->top == MAX - 1;
}
/* push: add to top */
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack overflow — cannot push %d\n", value);
return;
}
s->top++; /* move top up */
s->data[s->top] = value; /* place value at new top */
}
/* pop: remove from top */
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack underflow — nothing to pop\n");
return -1;
}
int val = s->data[s->top]; /* save top value */
s->top--; /* move top down */
return val;
}
/* peek: read top without removing */
int peek(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->data[s->top];
}
/* print all elements from top to bottom */
void printStack(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return;
}
printf("Stack (top to bottom): ");
int i;
for (i = s->top; i >= 0; i--) {
printf("%d ", s->data[i]);
}
printf("\n");
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
printStack(&s); /* Stack (top to bottom): 40 30 20 10 */
printf("Peek: %d\n", peek(&s)); /* Peek: 40 */
printf("Pop: %d\n", pop(&s)); /* Pop: 40 */
printf("Pop: %d\n", pop(&s)); /* Pop: 30 */
printStack(&s); /* Stack (top to bottom): 20 10 */
return 0;
}
🎯 Pro Tip
Stack overflow and underflow are the two error conditions you must always check. Overflow: trying to push when the stack is full. Underflow: trying to pop when the stack is empty. In real systems, unchecked stack overflow causes crashes — which is also where the name of the famous programming website comes from.
// Section 3
Stack Using a Linked List
The array-based stack has a fixed size — you must decide MAX upfront. A linked list-based stack has no size limit — it grows and shrinks dynamically. The top of the stack is always the HEAD of the list. Push = insert at head. Pop = delete head. Both are O(1).
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
typedef struct Node Node;
/* the top pointer is just our linked list head */
Node *top = NULL;
int isEmptyLL() {
return top == NULL;
}
void pushLL(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = top; /* new node points to current top */
top = newNode; /* new node becomes the new top */
}
int popLL() {
if (isEmptyLL()) {
printf("Stack underflow\n");
return -1;
}
Node *temp = top;
int val = temp->data;
top = top->next; /* move top to the next node */
free(temp); /* free the popped node */
return val;
}
int peekLL() {
if (isEmptyLL()) {
printf("Stack is empty\n");
return -1;
}
return top->data;
}
void printStackLL() {
Node *current = top;
printf("Stack (top to bottom): ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
pushLL(10);
pushLL(20);
pushLL(30);
printStackLL(); /* Stack (top to bottom): 30 20 10 */
printf("Peek: %d\n", peekLL()); /* Peek: 30 */
printf("Pop: %d\n", popLL()); /* Pop: 30 */
printStackLL(); /* Stack (top to bottom): 20 10 */
return 0;
}
Array-based stack
Fixed size. Simpler code. Better cache performance. Use when max size is known.
Linked list-based stack
Dynamic size. No overflow. Extra memory per node (the pointer). Use when size is unpredictable.
// Section 4
Classic Problem — Balanced Parentheses
This is the most famous stack problem and appears in almost every interview. Given a string of brackets like "({[]})", determine if every opening bracket has a matching closing bracket in the correct order.
Why a stack is the perfect tool here:
1
When you see an opening bracket ( [ { — push it onto the stack.
2
When you see a closing bracket ) ] } — check if the top of the stack is the matching opener.
3
If it matches — pop the opener off. If it does not match — the string is invalid.
4
At the end — if the stack is empty, all brackets were matched. If not, some opener was never closed.
// Tracing "( [ ] )" step by step
]
top=[ matches ] → pop
stack: (
✓
)
top=( matches ) → pop
stack: empty
✓
Stack is empty at end → BALANCED ✓
#include <stdio.h>
#define MAX 100
struct Stack {
char data[MAX];
int top;
};
typedef struct Stack Stack;
void initStack(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
void push(Stack *s, char c) { s->data[++(s->top)] = c; }
char pop(Stack *s) { return s->data[(s->top)--]; }
char peek(Stack *s) { return s->data[s->top]; }
int isBalanced(char *expr) {
Stack s;
initStack(&s);
int i;
for (i = 0; expr[i] != '\0'; i++) {
char c = expr[i];
/* opening bracket — push onto stack */
if (c == '(' || c == '[' || c == '{') {
push(&s, c);
}
/* closing bracket — must match the top */
else if (c == ')' || c == ']' || c == '}') {
if (isEmpty(&s)) {
return 0; /* closing with nothing open — invalid */
}
char top = pop(&s);
/* check if the popped opener matches this closer */
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return 0; /* mismatch — invalid */
}
}
}
/* valid only if all openers were matched (stack is empty) */
return isEmpty(&s);
}
int main() {
char e1[] = "({[]})";
char e2[] = "({[})";
char e3[] = "((())";
printf("'%s' → %s\n", e1, isBalanced(e1) ? "BALANCED" : "NOT BALANCED");
printf("'%s' → %s\n", e2, isBalanced(e2) ? "BALANCED" : "NOT BALANCED");
printf("'%s' → %s\n", e3, isBalanced(e3) ? "BALANCED" : "NOT BALANCED");
/* Output:
'({[]})' → BALANCED
'({[})' → NOT BALANCED
'((())' → NOT BALANCED
*/
return 0;
}
Time:O(n)Space:O(n)(worst case: all openers, none closed)
// Section 5
The Function Call Stack — What Happens Inside Your Computer
Your computer uses a stack internally every time one function calls another. This is called the call stack. Understanding it explains recursion, stack overflow errors, and how programs know where to return after a function finishes.
When main() calls funcA() which calls funcB():
call stack grows ↑
← TOP currently running
funcB()
funcA()
main()
BOTTOM
1
main() is called — pushed onto the call stack.
2
main() calls funcA() — funcA() pushed on top.
3
funcA() calls funcB() — funcB() pushed on top.
4
funcB() finishes — popped off, execution returns to funcA().
5
funcA() finishes — popped off, execution returns to main().
💡 Note
Stack overflow the error happens when the call stack grows too deep — usually from infinite recursion. Each function call pushes a frame onto the stack. If a recursive function never hits its base case, it keeps pushing until the stack runs out of memory and the OS kills the program. This is the real meaning of "stack overflow."
// Section 6
Reverse a String Using a Stack
Because a stack is LIFO, pushing all characters of a string and then popping them gives you the string in reverse — automatically. No two-pointer needed. Push every character, then pop them all back out.
#include <stdio.h>
#include <string.h>
#define MAX 100
struct Stack {
char data[MAX];
int top;
};
typedef struct Stack Stack;
void initStack(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
void push(Stack *s, char c) { s->data[++(s->top)] = c; }
char pop(Stack *s) { return s->data[(s->top)--]; }
void reverseString(char *str) {
Stack s;
initStack(&s);
int i;
int len = strlen(str);
/* push every character */
for (i = 0; i < len; i++) {
push(&s, str[i]);
}
/* pop them back — they come out in reverse order */
for (i = 0; i < len; i++) {
str[i] = pop(&s);
}
}
int main() {
char str[] = "Chaduvuko";
printf("Before: %s\n", str); /* Chaduvuko */
reverseString(str);
printf("After: %s\n", str); /* okuvadhC */
return 0;
}
// Section 7
Undo / Redo — How Real Applications Use Stacks
Every text editor, image editor, and IDE you have ever used implements undo/redo with two stacks. This is one of the most elegant real-world applications of the stack data structure.
Undo Stack
Every action you perform gets pushed onto the undo stack.
When you press Ctrl+Z — pop from undo stack, reverse the action, push it onto the redo stack.
Redo Stack
When you press Ctrl+Y — pop from redo stack, redo the action, push it back onto the undo stack.
If you perform a new action — the redo stack is cleared entirely.
#include <stdio.h>
#include <string.h>
#define MAX 50
/* simple demo — tracking text changes as strings */
struct StrStack {
char data[MAX][100];
int top;
};
typedef struct StrStack StrStack;
void initSS(StrStack *s) { s->top = -1; }
int isEmptySS(StrStack *s) { return s->top == -1; }
void pushSS(StrStack *s, char *val) { strcpy(s->data[++(s->top)], val); }
void popSS(StrStack *s, char *out) { strcpy(out, s->data[(s->top)--]); }
void peekSS(StrStack *s, char *out) { strcpy(out, s->data[s->top]); }
int main() {
StrStack undoStack, redoStack;
initSS(&undoStack);
initSS(&redoStack);
char buf[100];
/* simulate three actions */
pushSS(&undoStack, "Typed: Hello");
pushSS(&undoStack, "Typed: World");
pushSS(&undoStack, "Bold applied");
printf("--- Undo ---\n");
popSS(&undoStack, buf);
printf("Undid: %s\n", buf); /* Undid: Bold applied */
pushSS(&redoStack, buf);
popSS(&undoStack, buf);
printf("Undid: %s\n", buf); /* Undid: Typed: World */
pushSS(&redoStack, buf);
printf("--- Redo ---\n");
popSS(&redoStack, buf);
printf("Redid: %s\n", buf); /* Redid: Typed: World */
pushSS(&undoStack, buf);
return 0;
}
// Section 8
Errors You Will Hit
⚠ Stack Underflow — popping from an empty stack
Symptom: Program reads garbage value or crashes when trying to pop
Fix: Always call isEmpty() before pop() or peek(). Never assume the stack has elements.
⚠ Stack Overflow — pushing to a full array stack
Symptom: Values silently overwrite memory beyond the array boundary
Fix: Always call isFull() before push() in array-based stacks. Or use the linked list version which has no fixed limit.
⚠ Not resetting top after using the stack
Symptom: Old data appears when you reuse the stack for a new problem
Fix: Always call initStack() to set top = -1 before using a stack for a fresh problem.
// Section 9
Quick Reference — All Stack Operations
| Operation | Array Stack | Linked List Stack | Time |
|---|
| push(x) | data[++top] = x | insert new node at head | O(1) |
| pop() | return data[top--] | delete head, return its data | O(1) |
| peek() | return data[top] | return top->data | O(1) |
| isEmpty() | top == -1 | top == NULL | O(1) |
| isFull() | top == MAX-1 | not applicable (dynamic) | O(1) |
| Space used | Fixed MAX slots | Grows as needed | — |
// What's Next
You Are Ready for Unit 07
You now understand stacks completely — the LIFO rule, all four operations, both implementations, and three classic applications. You also understand the call stack that powers every program you have ever run.
In Unit 07 we cover Queues — the other side of the coin. Where stacks are LIFO, queues are FIFO: First In, First Out. Think of a ticket counter line — the person who arrives first gets served first. Queues power CPU scheduling, message delivery systems, and breadth-first graph traversal.
UP NEXT → UNIT 07
Queues — First In, First Out
Enqueue, dequeue, circular queue, priority queue — explained simply.
🎯 Key Takeaways
- ✓A stack is LIFO — Last In, First Out. Only the top element is accessible at any time
- ✓Four operations: push (add to top), pop (remove from top), peek (read top), isEmpty (check if empty) — all O(1)
- ✓Array stack: simple, fixed size. Track top index starting at -1. Linked list stack: dynamic, no size limit
- ✓Stack overflow = pushing to a full stack. Stack underflow = popping from an empty stack. Always check both
- ✓Balanced parentheses: push openers, pop and match on closers, valid if stack empty at end
- ✓The call stack is how your computer tracks function calls — each call pushes a frame, return pops it
- ✓Undo/redo in editors uses two stacks — undo stack for done actions, redo stack for undone actions
- ✓Reversing a string with a stack: push all characters, pop them back — LIFO gives you reverse for free