Stacks and Queues

You’ve learned linked lists. Now let’s build two data structures that are used everywhere in computing.

These aren’t just academic exercises. Your computer uses stacks to call functions. Your web browser uses stacks for the back button. Theme parks use queues for ride lines.

Stacks: Last In, First Out

A stack is like a stack of plates at a buffet. You add plates to the top. You take plates from the top. The last plate you put on is the first one you take off.

This is called LIFO - Last In, First Out. A stack with three items looks like a vertical column: 1 at the bottom (added first), 2 in the middle, and 3 at the top (added last and will be removed first).

A vertical stack of three boxes. At the top is value 3 labeled as 'top - last added, first removed'. In the middle is value 2. At the bottom is value 1 labeled as 'bottom - first added, last removed'. Items are only added to or removed from the top.

Stack Operations

A stack has two main operations:

  • Push: Add something to the top
  • Pop: Remove and return the top item

That’s it. You can’t add to the middle. You can’t remove from the bottom. Only the top.

It’s like stacking comic books. You can put a new one on top. You can take the top one off. But if you want the one at the bottom, you have to remove all the ones above it first.

Stack Implementation

We can build a stack using a linked list where we only add and remove from the head:

#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode {
    int value;
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *top;
    int size;
} Stack;

void stack_init(Stack *s) {
    s->top = NULL;
    s->size = 0;
}

int stack_is_empty(Stack *s) {
    return s->top == NULL;
}

void stack_push(Stack *s, int value) {
    StackNode *node = malloc(sizeof(StackNode));
    if (node == NULL) {
        printf("Out of memory!\n");
        return;
    }
    node->value = value;
    node->next = s->top;  // New node points to old top
    s->top = node;        // New node becomes top
    s->size++;
}

int stack_pop(Stack *s) {
    if (stack_is_empty(s)) {
        printf("Stack is empty! Can't pop.\n");
        return -1;  // Error value
    }
    StackNode *temp = s->top;
    int value = temp->value;
    s->top = temp->next;  // Second node becomes top
    free(temp);
    s->size--;
    return value;
}

int stack_peek(Stack *s) {
    if (stack_is_empty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->top->value;  // Look but don't remove
}

void stack_free(Stack *s) {
    while (!stack_is_empty(s)) {
        stack_pop(s);
    }
}

Using the Stack

int main(void) {
    Stack s;
    stack_init(&s);

    stack_push(&s, 10);
    stack_push(&s, 20);
    stack_push(&s, 30);

    printf("Top: %d\n", stack_peek(&s));  // 30

    printf("Pop: %d\n", stack_pop(&s));   // 30
    printf("Pop: %d\n", stack_pop(&s));   // 20
    printf("Pop: %d\n", stack_pop(&s));   // 10

    stack_free(&s);
    return 0;
}

Real Uses of Stacks

Undo/Redo: Every action goes on a stack. Ctrl+Z pops the last action and undoes it.

Browser back button: Each page you visit is pushed onto a stack. Click back, and it pops the current page to show the previous one.

Function calls: When your program calls a function, it pushes information onto “the call stack.” When the function returns, it pops. This is why you get a “stack overflow” error if a function calls itself forever - you run out of stack space!

Syntax checking: Compilers use stacks to match parentheses. Push on (, pop on ). If the stack isn’t empty at the end, you have mismatched parentheses.

Example: Matching Parentheses

int check_parentheses(const char *str) {
    Stack s;
    stack_init(&s);

    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(') {
            stack_push(&s, '(');
        } else if (str[i] == ')') {
            if (stack_is_empty(&s)) {
                return 0;  // Too many closing parens
            }
            stack_pop(&s);
        }
    }

    int balanced = stack_is_empty(&s);
    stack_free(&s);
    return balanced;
}

int main(void) {
    printf("((a+b)*c): %s\n",
           check_parentheses("((a+b)*c)") ? "Balanced" : "Not balanced");
    printf("((a+b): %s\n",
           check_parentheses("((a+b)") ? "Balanced" : "Not balanced");
    return 0;
}

Queues: First In, First Out

A queue is like a line at a coffee shop. The first person in line gets served first. New people join at the back. It’s fair.

This is called FIFO - First In, First Out. A queue with four items shows 1 at the front (where items are removed) and 4 at the back (where new items are added). Items 2 and 3 are in the middle waiting their turn.

A horizontal queue of four connected boxes. At the left (front) is value 1 with a label 'Remove here' showing where items are dequeued. Moving right are values 2, 3, and 4. Value 4 at the right (back) has a label 'Add here' showing where new items are enqueued. Items flow from right to left - added at back, removed from front.

Queues are perfectly fair - first come, first served.

Queue Operations

A queue has two main operations:

  • Enqueue: Add to the back of the line
  • Dequeue: Remove from the front of the line

Queue Implementation

For a queue, we need to track both ends:

#include <stdio.h>
#include <stdlib.h>

typedef struct QueueNode {
    int value;
    struct QueueNode *next;
} QueueNode;

typedef struct {
    QueueNode *front;
    QueueNode *back;
    int size;
} Queue;

void queue_init(Queue *q) {
    q->front = NULL;
    q->back = NULL;
    q->size = 0;
}

int queue_is_empty(Queue *q) {
    return q->front == NULL;
}

void queue_enqueue(Queue *q, int value) {
    QueueNode *node = malloc(sizeof(QueueNode));
    if (node == NULL) {
        printf("Out of memory!\n");
        return;
    }
    node->value = value;
    node->next = NULL;

    if (queue_is_empty(q)) {
        // First node - it's both front and back
        q->front = node;
        q->back = node;
    } else {
        // Add to back
        q->back->next = node;
        q->back = node;
    }
    q->size++;
}

int queue_dequeue(Queue *q) {
    if (queue_is_empty(q)) {
        printf("Queue is empty! Can't dequeue.\n");
        return -1;
    }

    QueueNode *temp = q->front;
    int value = temp->value;
    q->front = temp->next;

    // Was that the last node?
    if (q->front == NULL) {
        q->back = NULL;
    }

    free(temp);
    q->size--;
    return value;
}

int queue_peek(Queue *q) {
    if (queue_is_empty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->front->value;
}

void queue_free(Queue *q) {
    while (!queue_is_empty(q)) {
        queue_dequeue(q);
    }
}

Using the Queue

int main(void) {
    Queue q;
    queue_init(&q);

    queue_enqueue(&q, 10);
    queue_enqueue(&q, 20);
    queue_enqueue(&q, 30);

    printf("Front: %d\n", queue_peek(&q));  // 10

    printf("Dequeue: %d\n", queue_dequeue(&q));  // 10
    printf("Dequeue: %d\n", queue_dequeue(&q));  // 20
    printf("Dequeue: %d\n", queue_dequeue(&q));  // 30

    queue_free(&q);
    return 0;
}

Real Uses of Queues

Print jobs: Documents wait in a queue. First document sent, first document printed.

Network packets: Data packets wait in queues at routers. First packet in, first packet out.

Task scheduling: Your operating system puts tasks in queues. The CPU works through them in order (well, mostly - priority queues can get complicated).

Game events: Player actions go into a queue. The game processes them in order so everything stays synchronized.

Example: Print Queue Simulator

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char document[50];
    int pages;
} PrintJob;

typedef struct JobNode {
    PrintJob job;
    struct JobNode *next;
} JobNode;

typedef struct {
    JobNode *front;
    JobNode *back;
} PrintQueue;

void pq_init(PrintQueue *q) {
    q->front = NULL;
    q->back = NULL;
}

void pq_add_job(PrintQueue *q, const char *doc, int pages) {
    JobNode *node = malloc(sizeof(JobNode));
    if (node == NULL) return;

    strncpy(node->job.document, doc, 49);
    node->job.document[49] = '\0';
    node->job.pages = pages;
    node->next = NULL;

    if (q->front == NULL) {
        q->front = node;
        q->back = node;
    } else {
        q->back->next = node;
        q->back = node;
    }
    printf("Added to queue: %s (%d pages)\n", doc, pages);
}

void pq_process(PrintQueue *q) {
    if (q->front == NULL) {
        printf("No jobs in queue.\n");
        return;
    }

    JobNode *temp = q->front;
    printf("Printing: %s (%d pages)... Done!\n",
           temp->job.document, temp->job.pages);

    q->front = temp->next;
    if (q->front == NULL) {
        q->back = NULL;
    }
    free(temp);
}

void pq_free(PrintQueue *q) {
    while (q->front != NULL) {
        JobNode *temp = q->front;
        q->front = temp->next;
        free(temp);
    }
    q->back = NULL;
}

int main(void) {
    PrintQueue printer;
    pq_init(&printer);

    pq_add_job(&printer, "TPS Report", 3);
    pq_add_job(&printer, "Comic Script", 12);
    pq_add_job(&printer, "Resume", 1);

    printf("\nProcessing print queue:\n");
    pq_process(&printer);
    pq_process(&printer);
    pq_process(&printer);
    pq_process(&printer);  // Empty queue

    pq_free(&printer);
    return 0;
}

Stack vs Queue: When to Use Which?

Use a stack when:

  • You need “undo” functionality
  • Processing things in reverse order
  • Matching brackets/parentheses
  • Tracking where you’ve been (like in a maze)

Use a queue when:

  • First come, first served is fair
  • Processing things in the order they arrived
  • Buffering data between fast and slow processes
  • Breadth-first search (we’ll learn this with trees)

Array-Based Versions

You can also implement stacks and queues with arrays instead of linked lists:

Array Stack

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top;
} ArrayStack;

void astack_init(ArrayStack *s) {
    s->top = -1;  // Empty stack
}

int astack_is_full(ArrayStack *s) {
    return s->top >= MAX_SIZE - 1;
}

int astack_is_empty(ArrayStack *s) {
    return s->top < 0;
}

void astack_push(ArrayStack *s, int value) {
    if (astack_is_full(s)) {
        printf("Stack overflow!\n");
        return;
    }
    s->top++;
    s->items[s->top] = value;
}

int astack_pop(ArrayStack *s) {
    if (astack_is_empty(s)) {
        printf("Stack underflow!\n");
        return -1;
    }
    return s->items[s->top--];
}

Array versions are faster (no malloc/free) but have a fixed maximum size.

Try It Yourself

  1. Implement a function that reverses a string using a stack
  2. Build a queue that stores strings instead of integers
  3. Implement a “circular queue” using an array (the back wraps around to the front)
  4. Use two stacks to implement a queue (hint: one for enqueue, one for dequeue)

Common Mistakes

  • Popping from an empty stack (underflow)
  • Pushing to a full array stack (overflow)
  • Forgetting to update the back pointer when dequeuing the last element
  • Memory leaks from not freeing all nodes

Next Up

In Part 18, we’ll learn about trees - hierarchical data structures that let you organize data like a family tree or file system.

Enjoyed This?

If this helped something click, subscribe to my YouTube channel. More content like this, same approach - making things stick without insulting your intelligence. It’s free, it helps more people find this stuff, and it tells me what’s worth making more of.