These are the notes for C episode 23. Last episode you built a linked list. Here you use arrays and linked lists to build two of the most used data structures in programming: the stack (the undo button) and the queue (the ticket counter). Each one is invented as the fix for a program that gives the wrong answer or runs too slowly. Every example was compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13, the same command as the SyntaxPilot compiler) and run as shown. The online compiler stops a program after 8 seconds and reports Time Limit Exceeded.
The problem: undo, twice
Real-life example: Ctrl+Z. You type Hi, then Hi there, then Hi there!. Undo once: Hi there. Undo again: you expect plain Hi, an older version. So the editor must remember every old version and hand them back newest first.
The obvious attempt keeps one saved copy, last. Before every change, copy the text into last; to undo, copy last back:
#include <stdio.h>
#include <string.h>
int main() {
char text[50] = "Hi";
char last[50];
strcpy(last, text); strcpy(text, "Hi there");
strcpy(last, text); strcpy(text, "Hi there!");
printf("Now: %s\n", text);
strcpy(text, last); printf("Undo 1: %s\n", text);
strcpy(text, last); printf("Undo 2: %s\n", text);
return 0;
}
Now: Hi there!
Undo 1: Hi there
Undo 2: Hi there
Undo 2 is wrong. It should be Hi.
Why: one variable remembers one thing. Saving Hi there overwrote Hi, so the older version is gone for good. We need a pile of saved copies.
The idea: a stack of plates
| Wedding buffet plates | Stack in C |
|---|---|
| A pile of plates, one on top of another | a stack: an array plus a counter top |
| A washed plate goes on top | push: add an item at the top |
| A guest takes the top plate, never one from the middle | pop: remove the item at the top |
| The last plate put on is the first one taken | LIFO: Last In, First Out |
A stack is a collection where items are added and removed at the same end, the top. Undo is LIFO: the newest version comes back first.
A stack of saved texts: the undo button fixed
#include <stdio.h>
#include <string.h>
char history[100][50];
int top = 0;
void push(char *text) {
strcpy(history[top], text);
top++;
}
void pop(char *text) {
top--;
strcpy(text, history[top]);
}
int main() {
char text[50] = "Hi";
push(text); strcpy(text, "Hi there");
push(text); strcpy(text, "Hi there!");
printf("Now: %s\n", text);
pop(text); printf("Undo 1: %s\n", text);
pop(text); printf("Undo 2: %s\n", text);
return 0;
}
Now: Hi there!
Undo 1: Hi there
Undo 2: Hi
char history[100][50]is room for 100 texts of up to 49 characters (a 2D array of chars, one row per text).pushcopies the text intohistory[top], thentop++.popdoes the reverse:top--first, then copyhistory[top]back.mainpushes before every change and pops for every undo.
What top means
index: [0] [1] [2]
"Hi" "Hi there" (free) top = 2
topis how many items are on the stack, and also the index where the next push goes.- Push in one line:
items[top++] = x;(store attop, then movetopup). - Pop in one line:
x = items[--top];(movetopdown first, then read). - Both are instant: nobody else moves, only
topchanges. In Big-O notation this is O(1), constant time.
The difference between top++ and ++top matters here. items[top--] in a pop reads one place above the top item (a free slot) and gives the wrong value with no error at all.
Overflow and underflow
A stack in an array has a fixed number of places, so it needs two checks:
- Stack overflow: pushing onto a full stack.
- Stack underflow: popping from an empty stack.
#include <stdio.h>
#define MAX 3
int items[MAX];
int top = 0;
void push(int x) {
if (top == MAX) {
printf("Stack overflow! %d not added\n", x);
return;
}
items[top++] = x;
}
int pop() {
if (top == 0) {
printf("Stack underflow! ");
return -1;
}
return items[--top];
}
int main() {
push(10); push(20); push(30); push(40);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
return 0;
}
Stack overflow! 40 not added
30
20
10
Stack underflow! -1
The fourth push is refused, the pops come out 30, 20, 10 (last in, first out), and the fourth pop reports underflow and returns -1 as a "nothing here" value.
Without the checks, the fourth push would write items[3], past the end of a 3-element array, into memory that belongs to something else. C gives no error message for this: the program just silently corrupts another variable or crashes later. (In episode 26 you'll meet AddressSanitizer, which catches it.) The name stack overflow is also what you see when a recursive function calls itself too many times, because function calls live on a stack too (episode 27).
Where stacks hide: checking brackets
Real-life example: your compiler. In { x[i] = (y+1); } every opening bracket needs its own closing bracket, and they are nested. The rule:
- An opener
(,[,{: push it. - A closer
),],}: pop, and the popped opener must match it. It must close the newest opener still waiting: LIFO. - At the end the stack must be empty: leftover openers were never closed.
#include <stdio.h>
char st[100];
int top = 0;
int matches(char open, char close) {
return (open == '(' && close == ')') ||
(open == '[' && close == ']') ||
(open == '{' && close == '}');
}
int balanced(char *s) {
top = 0;
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{')
st[top++] = c;
else if (c == ')' || c == ']' || c == '}') {
if (top == 0 || !matches(st[--top], c))
return 0;
}
}
return top == 0;
}
int main() {
char *tests[] = {"(a+b)*[c-d]", "{x[i] = (y+1);}",
"(a+b]", "((a+b)"};
for (int i = 0; i < 4; i++)
printf("%-18s %s\n", tests[i],
balanced(tests[i]) ? "balanced" : "NOT balanced");
return 0;
}
(a+b)*[c-d] balanced
{x[i] = (y+1);} balanced
(a+b] NOT balanced
((a+b) NOT balanced
(a+b]: the]pops(, which doesn't match.((a+b): one(is left on the stack at the end.%-18sprints a string left-aligned in 18 columns, so the results line up.
This is also why a missing } makes the compiler complain far below where you forgot it: it only notices when the brackets run out.
The problem: the ticket counter
Real-life example: the railway ticket counter. Passengers 101, 102 and 103 join the line in that order. The rule is first come, first served. Let's reuse the stack:
#include <stdio.h>
int items[10];
int top = 0;
void push(int x) { items[top++] = x; }
int pop() { return items[--top]; }
int main() {
push(1); push(2); push(3); // tokens in arrival order
printf("Serving: %d\n", pop());
printf("Serving: %d\n", pop());
printf("Serving: %d\n", pop());
return 0;
}
Serving: 3
Serving: 2
Serving: 1
The person who came last is served first. Fine for plates, terrible for people.
Why: a stack has one open end; items come in and go out of the same end. A line needs two ends: join at the back, leave from the front.
The idea: a queue
| Ticket counter line | Queue in C |
|---|---|
| People standing one behind another in arrival order | a queue |
| A new person joins at the back | enqueue: add at the rear |
| The person at the window gets a ticket and leaves | dequeue: remove from the front |
| First in line is first served | FIFO: First In, First Out |
A stack is LIFO, a queue is FIFO: that one letter is the whole difference.
A queue with an array, and why it says "full" when it's empty
Two indexes: front (where people leave) and rear (where people join).
#include <stdio.h>
#define MAX 5
int items[MAX];
int front = 0, rear = 0;
void enqueue(int x) {
if (rear == MAX) {
printf("Queue full! %d turned away\n", x);
return;
}
items[rear++] = x;
}
int dequeue() {
return items[front++];
}
int main() {
for (int t = 1; t <= 5; t++) enqueue(t);
for (int i = 0; i < 5; i++) printf("Serving %d\n", dequeue());
printf("People waiting: %d\n", rear - front);
enqueue(6);
return 0;
}
Serving 1
Serving 2
Serving 3
Serving 4
Serving 5
People waiting: 0
Queue full! 6 turned away
Nobody is waiting, yet passenger 6 is turned away.
Why: front and rear only ever move forward. After 5 joins, rear is 5 (the end of the array), so the queue looks full, while every place behind front is empty and wasted.
index: [0] [1] [2] [3] [4]
- - - - - front = 5, rear = 5: "full" but empty
(Moving everyone forward one place on every dequeue would fix it, but that is the slow "everyone moves one chair" problem from episode 22.)
The circular queue
Real-life example: the round tray at a sweet shop. After the last slot comes slot 0 again. Bend the array into a circle:
- Move an index forward with the remainder operator
%(episode 3):rear = (rear + 1) % MAX;. WithMAX5:(4 + 1) % 5 = 0, back to the start. - Keep a count of the people waiting. Full means
count == MAX, empty meanscount == 0. (Without a count,front == rearwould mean both "empty" and "full".)
#include <stdio.h>
#define MAX 5
int items[MAX];
int front = 0, rear = 0, count = 0;
void enqueue(int x) {
if (count == MAX) {
printf("Queue full! %d turned away\n", x);
return;
}
items[rear] = x;
rear = (rear + 1) % MAX;
count++;
}
int dequeue() {
int x = items[front];
front = (front + 1) % MAX;
count--;
return x;
}
int main() {
for (int t = 1; t <= 5; t++) enqueue(t);
for (int i = 0; i < 5; i++) printf("Serving %d\n", dequeue());
enqueue(6); enqueue(7);
printf("Serving %d\n", dequeue());
printf("rear is back at index %d\n", rear);
return 0;
}
Serving 1
Serving 2
Serving 3
Serving 4
Serving 5
Serving 6
rear is back at index 2
Passengers 6 and 7 were accepted, and rear wrapped around to index 2, reusing the places that 1 and 2 left behind.
| Step | front | rear | count | Array |
|---|---|---|---|---|
| 5 joins | 0 | 0 (wrapped) | 5 | 1 2 3 4 5 |
| 5 served | 0 (wrapped) | 0 | 0 | empty |
| 6 and 7 join | 0 | 2 | 2 | 6 7 - - - |
| 1 served | 1 | 2 | 1 | - 7 - - - |
A queue with no size limit: the linked list
The circular queue still has only MAX places. Real-life example: Tatkal booking at 10 a.m.: 300,000 requests at once. In episode 22 we built a structure with no fixed size, the linked list. A list queue: the head node is the front (dequeue removes the first node) and enqueue is add_back.
The obvious attempt: add_back from episode 22
#include <stdio.h>
#include <stdlib.h>
struct node {
int token;
struct node *next;
};
struct node *add_back(struct node *head, int token) {
struct node *n = malloc(sizeof(struct node));
n->token = token;
n->next = NULL;
if (head == NULL)
return n;
struct node *p = head;
while (p->next != NULL)
p = p->next;
p->next = n;
return head;
}
int main() {
struct node *head = NULL;
for (int t = 1; t <= 300000; t++)
head = add_back(head, t);
printf("Front: %d\n", head->token);
return 0;
}
In the online compiler: Time Limit Exceeded (stopped after 8 seconds; on a fast machine it still runs for more than 20 seconds).
Why: every enqueue walks the whole line from the front to find the last node. The 10,000th booking walks past about 10,000 nodes; adding up all 300,000 bookings gives about 300,000² / 2 ≈ 45 billion steps. Each enqueue is O(n), all of them O(n²).
The fix: keep a tail pointer
Keep head for the front and tail for the last node. Enqueue links the new node after tail and moves tail: no walking at all.
#include <stdio.h>
#include <stdlib.h>
struct node {
int token;
struct node *next;
};
struct node *head = NULL, *tail = NULL;
void enqueue(int token) {
struct node *n = malloc(sizeof(struct node));
n->token = token;
n->next = NULL;
if (tail == NULL)
head = tail = n;
else {
tail->next = n;
tail = n;
}
}
int dequeue() {
struct node *first = head;
int t = first->token;
head = head->next;
if (head == NULL)
tail = NULL;
free(first);
return t;
}
int main() {
for (int t = 1; t <= 300000; t++)
enqueue(t);
printf("Front: %d\n", head->token);
printf("Back: %d\n", tail->token);
printf("Serving %d\n", dequeue());
printf("Next: %d\n", head->token);
return 0;
}
Front: 1
Back: 300000
Serving 1
Next: 2
Done in about 0.01 seconds. Two special cases:
- Empty queue (
tail == NULL): the new node is bothheadandtail. - Dequeue of the last node:
headbecomesNULL, sotailmust becomeNULLtoo. Otherwisetailstill points at the freed node, and the next enqueue writes into freed memory (use after free).
(For a real program, dequeue should also check head == NULL before reading head->token, exactly like call_next in episode 22.)
Stack or queue?
| Stack | Queue | |
|---|---|---|
| Open ends | one (the top) | two (front and rear) |
| Add | push at the top |
enqueue at the rear |
| Remove | pop from the top |
dequeue from the front |
| Order | LIFO: newest leaves first | FIFO: oldest leaves first |
| Array version | items[top++], items[--top] |
circular: % MAX and a count |
| List version | add/remove at the head | head + tail pointers |
| Every operation | O(1) | O(1) |
| Used for | undo, browser back button, bracket checking, function calls (the call stack gdb's bt shows) |
ticket counters, printer jobs, messages in order, tasks waiting for the CPU |
Mini project: a ticket counter with undo
Both structures together: q is a circular queue of waiting passengers, served is a stack of issued tickets so the clerk can undo the last one.
#include <stdio.h>
#define MAX 5
int q[MAX], front = 0, rear = 0, count = 0; // the queue
int served[MAX], top = 0; // the undo stack
void join(int t) {
if (count == MAX) { printf("Full: %d waits\n", t); return; }
q[rear] = t; rear = (rear + 1) % MAX; count++;
}
void serve() {
if (count == 0) { printf("Nobody waiting\n"); return; }
int t = q[front]; front = (front + 1) % MAX; count--;
served[top++] = t;
printf("Ticket issued to %d\n", t);
}
void undo() {
if (top == 0) { printf("Nothing to undo\n"); return; }
printf("Ticket of %d cancelled\n", served[--top]);
}
int main() {
join(101); join(102); join(103);
serve(); serve();
undo();
serve(); serve();
printf("Waiting: %d\n", count);
return 0;
}
Ticket issued to 101
Ticket issued to 102
Ticket of 102 cancelled
Ticket issued to 103
Nobody waiting
Waiting: 0
Tickets go to 101 and 102 in arrival order (FIFO). Undo cancels the newest ticket, 102 (LIFO). Then 103 is served, and the line is empty.
Homework from the video: make undo put the passenger back at the front of the line. That needs a queue you can add to at the front as well, called a deque (double-ended queue). Solution below.
Common mistakes (and the real messages)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
push with no full check |
No error: another variable silently changes, or a crash later | top went past MAX, writing outside the array |
if (top == MAX) ... before storing |
pop on an empty stack |
Garbage value or a crash | items[-1] isn't yours |
if (top == 0) ... first |
return items[top--]; in pop |
No error: the wrong item | Reads the free slot above the top | return items[--top]; |
items[++top] = x; in push |
No error: items[0] is never used, the last push overflows |
Moves top before storing |
items[top++] = x; |
| Using a stack for a waiting line | Serving: 3, Serving: 2, Serving: 1 |
LIFO serves the newest first | Use a queue (FIFO) |
rear++ with no wrap |
Queue full! 6 turned away with nobody waiting |
front and rear never come back |
rear = (rear + 1) % MAX; and a count |
front == rear as the only test |
Can't tell full from empty | Both look the same in a circle | Keep a count (or leave one slot empty) |
add_back that walks the list for every enqueue |
Time Limit Exceeded with 300,000 items |
O(n) per enqueue | Keep a tail pointer |
Not resetting tail after the last dequeue |
Crash or corrupted list on the next enqueue | tail points at freed memory |
if (head == NULL) tail = NULL; |
printf("%d %d", pop(), pop()); |
4 2 on one compiler, 2 4 on another |
The order of evaluating arguments isn't fixed in C | Pop into variables first |
Practice
- Make the mini project's
undoput the cancelled passenger back at the front of the line (a deque operation). - Write a stack on a linked list (no size limit):
push, and apopthat reports underflow. - Reverse a string with a stack.
- Add a redo button to the undo program. Hint: redo is a second stack, and a new edit clears it.
Solutions
1. Undo puts the passenger back at the front (a circular queue that can also add at the front):
#include <stdio.h>
#define MAX 5
int q[MAX], front = 0, rear = 0, count = 0;
int served[MAX], top = 0;
void join(int t) {
if (count == MAX) { printf("Full: %d waits\n", t); return; }
q[rear] = t; rear = (rear + 1) % MAX; count++;
}
void join_front(int t) { // the deque part: add at the FRONT
if (count == MAX) { printf("Full: %d waits\n", t); return; }
front = (front - 1 + MAX) % MAX; // step front back one place, wrapping
q[front] = t; count++;
}
void serve() {
if (count == 0) { printf("Nobody waiting\n"); return; }
int t = q[front]; front = (front + 1) % MAX; count--;
served[top++] = t;
printf("Ticket issued to %d\n", t);
}
void undo() {
if (top == 0) { printf("Nothing to undo\n"); return; }
int t = served[--top];
printf("Ticket of %d cancelled, back to the front\n", t);
join_front(t);
}
int main() {
join(101); join(102); join(103);
serve(); serve();
undo();
serve(); serve();
printf("Waiting: %d\n", count);
return 0;
}
Ticket issued to 101
Ticket issued to 102
Ticket of 102 cancelled, back to the front
Ticket issued to 102
Ticket issued to 103
Waiting: 0
front = (front - 1 + MAX) % MAX steps front back one place; the + MAX keeps the value from going negative, because in C -1 % 5 is -1, not 4.
2. A stack on a linked list. The top of the stack is the head of the list, so push and pop are both O(1):
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
struct node *top = NULL; // the top of the stack is the head of the list
void push(int x) {
struct node *n = malloc(sizeof(struct node));
n->value = x;
n->next = top; // add at the front: O(1)
top = n;
}
int pop(int *out) {
if (top == NULL)
return 0; // underflow
struct node *first = top;
*out = first->value;
top = first->next;
free(first);
return 1;
}
int main() {
for (int i = 1; i <= 4; i++)
push(i * 10);
int x;
while (pop(&x))
printf("%d ", x);
printf("\n");
if (!pop(&x))
printf("Stack underflow\n");
return 0;
}
40 30 20 10
Stack underflow
3. Reverse a string with a stack. Push every letter, then pop them back: the newest comes out first.
#include <stdio.h>
#include <string.h>
int main() {
char word[] = "SyntaxPilot";
char st[100];
int top = 0;
for (int i = 0; word[i] != '\0'; i++)
st[top++] = word[i]; // push every letter
for (int i = 0; top > 0; i++)
word[i] = st[--top]; // pop them back: newest first
printf("%s\n", word);
return 0;
}
toliPxatnyS
4. Undo and redo with two stacks:
#include <stdio.h>
#include <string.h>
char undo_st[100][50], redo_st[100][50];
int utop = 0, rtop = 0;
void edit(char *text, const char *new_text) {
strcpy(undo_st[utop++], text);
strcpy(text, new_text);
rtop = 0; // a new edit clears the redo stack
}
void undo(char *text) {
if (utop == 0) { printf("Nothing to undo\n"); return; }
strcpy(redo_st[rtop++], text);
strcpy(text, undo_st[--utop]);
}
void redo(char *text) {
if (rtop == 0) { printf("Nothing to redo\n"); return; }
strcpy(undo_st[utop++], text);
strcpy(text, redo_st[--rtop]);
}
int main() {
char text[50] = "Hi";
edit(text, "Hi there");
edit(text, "Hi there!");
undo(text); printf("Undo: %s\n", text);
undo(text); printf("Undo: %s\n", text);
redo(text); printf("Redo: %s\n", text);
redo(text); printf("Redo: %s\n", text);
redo(text);
return 0;
}
Undo: Hi there
Undo: Hi
Redo: Hi there
Redo: Hi there!
Nothing to redo
Undo moves the current text onto the redo stack; redo moves it back onto the undo stack; a brand-new edit empties the redo stack (that's what real editors do).
All four were also run with -fsanitize=address,undefined with no reports.
Quick quiz
push(1); push(2); push(3);
pop();
push(4);
int a = pop();
int b = pop();
printf("%d %d", a, b);
- A.
4 3 - B.
4 2 - C.
3 2 - D.
1 2
Answer
B: 4 2. The first pop removes 3, leaving 1 2. push(4) gives 1 2 4. Then the pops return 4 and 2. (If you answered 4 3: 3 was already gone.) Popping into variables first matters: in printf("%d %d", pop(), pop()); C doesn't fix which argument is evaluated first.
Interview questions
- What is a stack? What is a queue? Explain LIFO and FIFO with a real example of each.
- Implement a stack with an array. How do you detect overflow and underflow?
- Why does a simple array queue run out of space, and how does a circular queue fix it?
- In a circular queue, how do you tell "full" from "empty"? (A
count, or keep one slot always empty: full when(rear + 1) % MAX == front.) - Implement a queue with a linked list so that both enqueue and dequeue are O(1). Why do you need a
tailpointer? - Check whether a string of brackets is balanced. What is the time and space complexity? (O(n) time, O(n) extra space.)
- How does an editor implement undo and redo?
- What is a deque? What is a priority queue? (A deque adds and removes at both ends; a priority queue always removes the most important item, like the emergency patient.)
- Implement a queue using two stacks. (Push into stack A; to dequeue, if B is empty pop everything from A into B, then pop B. Each item moves at most twice: O(1) on average.)
- What is the call stack, and what is a stack overflow error in recursion?
Glossary
| Term | Meaning | Example |
|---|---|---|
| Data structure | A way of organising data in memory so certain operations are fast | array, linked list, stack, queue |
| Stack | A collection where items are added and removed at the same end, the top | the undo history |
| Top | The end of a stack where items go in and come out; in an array stack, the count of items and the next free index | int top = 0; |
| Push | Add an item at the top of a stack | items[top++] = x; |
| Pop | Remove and return the item at the top of a stack | x = items[--top]; |
| LIFO | Last In, First Out: the newest item leaves first | a pile of plates |
| Stack overflow | Pushing onto a full stack (also: running out of call-stack space in deep recursion) | the 4th push into 3 places |
| Stack underflow | Popping from an empty stack | the 4th pop of 3 items |
| Queue | A collection where items join at one end (rear) and leave from the other (front) | the ticket counter line |
| Front | The end of a queue items leave from | front index, or head of a list |
| Rear | The end of a queue items join at | rear index, or tail of a list |
| Enqueue | Add an item at the rear of a queue | enqueue(6); |
| Dequeue | Remove and return the item at the front of a queue | dequeue() |
| FIFO | First In, First Out: the oldest item leaves first | first come, first served |
| Circular queue | An array queue whose indexes wrap from the last place back to 0 | rear = (rear + 1) % MAX; |
% (remainder) |
The remainder after division; used to wrap an index around | (4 + 1) % 5 is 0 |
| Tail pointer | A pointer to the last node of a list, so adding at the end needs no walking | tail->next = n; tail = n; |
| Deque | Double-ended queue: add and remove at both ends | putting a passenger back at the front |
| Balanced brackets | Every opener has a matching closer, properly nested | {x[i] = (y+1);} |
| O(1), constant time | The work doesn't grow with the number of items | push, pop, enqueue, dequeue |
| O(n) | The work grows in step with the number of items | walking a list to its end |
| Call stack | The stack where C keeps each function call's local variables; the newest call is on top | gdb's bt (episode 21) |
| Time Limit Exceeded | The online compiler stopped a program that ran longer than 8 seconds | 300,000 enqueues with walking add_back |
| Use after free | Using memory after it was freed | tail left pointing at a freed node |
Summary
- One saved copy can only undo once. A stack keeps every version: push at the top, pop from the top, LIFO. In an array:
items[top++] = x;anditems[--top]. - Always check overflow (
top == MAX) before a push and underflow (top == 0) before a pop: C won't warn you. - A stack checks brackets: push openers, every closer must match the newest opener, and the stack must end empty.
- A stack serves a line backwards. A queue is FIFO: enqueue at the rear, dequeue from the front.
- A simple array queue says "full" while it's empty because
frontandrearonly move forward. A circular queue wraps them with% MAXand keeps acount. - A linked list queue has no size limit. With only
head, every enqueue walks the list (Time Limit Exceeded for 300,000); with atailpointer, enqueue and dequeue are both O(1). ResettailtoNULLwhen the queue becomes empty.
Next episode: Trees: when every node gets two pointers, and searching a million items takes about 20 steps instead of a million.