SyntaxPilot
Courses/C Programming/Lesson 23

C Programming · Lesson 23 of 30 · 13 min

Stacks and queues

queued

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).
  • push copies the text into history[top], then top++.
  • pop does the reverse: top-- first, then copy history[top] back.
  • main pushes before every change and pops for every undo.

What top means

index:   [0]     [1]         [2]
         "Hi"    "Hi there"  (free)        top = 2
  • top is how many items are on the stack, and also the index where the next push goes.
  • Push in one line: items[top++] = x; (store at top, then move top up).
  • Pop in one line: x = items[--top]; (move top down first, then read).
  • Both are instant: nobody else moves, only top changes. 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:

  1. An opener (, [, {: push it.
  2. A closer ), ], }: pop, and the popped opener must match it. It must close the newest opener still waiting: LIFO.
  3. 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.
  • %-18s prints 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;. With MAX 5: (4 + 1) % 5 = 0, back to the start.
  • Keep a count of the people waiting. Full means count == MAX, empty means count == 0. (Without a count, front == rear would 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 both head and tail.
  • Dequeue of the last node: head becomes NULL, so tail must become NULL too. Otherwise tail still 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

  1. Make the mini project's undo put the cancelled passenger back at the front of the line (a deque operation).
  2. Write a stack on a linked list (no size limit): push, and a pop that reports underflow.
  3. Reverse a string with a stack.
  4. 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 tail pointer?
  • 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; and items[--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 front and rear only move forward. A circular queue wraps them with % MAX and keeps a count.
  • A linked list queue has no size limit. With only head, every enqueue walks the list (Time Limit Exceeded for 300,000); with a tail pointer, enqueue and dequeue are both O(1). Reset tail to NULL when 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.