Lesson 10 · 10 of 20

A stack and a queue · C

Use a stack in C to check whether the brackets in an expression are balanced, and a circular queue for a printer's jobs.

C · A stack and a queue in DMarlon Studio: the example's code and its output in the terminal

A stack (LIFO, last in, first out) only lets you add and remove at the top, like a pile of plates. Here it is an array stack with an index top: push is stack[top++] = c and pop is stack[--top].

balanced checks the brackets in an expression. Every opener ((, [ or {) is pushed. Every closer must match the last opener left on the stack: "([{"[closer - ")]}"] gives the opener for the closer just found, because both strings list them in the same order. If the stack is empty or they do not match, it is unbalanced; and if something is still open at the end, as in ((total), it is too.

A queue (FIFO, first in, first out) serves in order of arrival, like a printer's. Queue is a ring buffer: head is the first one waiting and count how many there are. enqueue writes at position (head + count) % CAP and dequeue reads at head and moves it forward.

% CAP wraps the indexes back to 0 at the end of the array, so the slot freed by each printed job is reused and elements never have to move.

Both structures have a fixed capacity here, CAP, and balanced returns 0 if the stack would overflow. With what you saw in the realloc lesson you can turn them into structures that grow.

Code · main.c

#include <stdio.h>#include <string.h>#define CAP 16  // room in the stack and in the queueint balanced(const char *text) {    char stack[CAP]; int top = 0;  // a stack (LIFO): last in, first out    for (; *text; text++) {        const char *closer = strchr(")]}", *text);        if (strchr("([{", *text)) {            if (top == CAP) return 0;  // too deep for our stack            stack[top++] = *text;      // push        } else if (closer && (top == 0 || stack[--top] != "([{"[closer - ")]}"]))            return 0;                  // pop: it must be the matching opener    }    return top == 0;  // nothing left open}typedef struct { const char *items[CAP]; int head, count; } Queue;  // FIFO ring buffervoid enqueue(Queue *q, const char *job) { q->items[(q->head + q->count++) % CAP] = job; }const char *dequeue(Queue *q) {  // head moves forward and wraps around    const char *job = q->items[q->head];    q->head = (q->head + 1) % CAP; q->count--;    return job;}int main(void) {    const char *exprs[] = {"(a[i] + b) * {c}", "f(x[0)]", "((total)"};    for (int i = 0; i < 3; i++)        printf("%-18s %s\n", exprs[i], balanced(exprs[i]) ? "balanced" : "NOT balanced");    Queue printer = {.head = 0, .count = 0};    enqueue(&printer, "invoice.pdf"); enqueue(&printer, "photo.png");    printf("Printing %s\n", dequeue(&printer)); enqueue(&printer, "report.docx");    while (printer.count > 0) printf("Printing %s\n", dequeue(&printer));    return 0;}

Output · cc main.c -o main && ./main

(a[i] + b) * {c}   balanced
f(x[0)]            NOT balanced
((total)           NOT balanced
Printing invoice.pdf
Printing photo.png
Printing report.docx

Key points

Stack: last in, first out.
Queue: first in, first out.
top++ pushes and --top pops.
A ring buffer moves on with % CAP and never shifts data.

Exercise

Add an int is_full(const Queue *q) function to the queue, make enqueue return 0 when it is full and test it with CAP set to 3.