Stacks and Queues

The Stack

A stack enforces LIFO — Last In, First Out. The two fundamental operations are:

• push(x) — add x to the top
• pop() — remove and return the top element

Stacks appear in function call management (every call frame is pushed; every return pops), expression evaluation, undo systems, and depth-first search.

Array-backed Stack

Using a dynamic array, push appends to the end and pop removes from the end — both O(1):

typedef struct {
    int *data;
    int size;
    int capacity;
} Stack;

void stack_init(Stack *s, int capacity) {
    s->data = malloc(capacity * sizeof(int));
    s->size = 0;
    s->capacity = capacity;
}

void stack_push(Stack *s, int x) {
    if (s->size == s->capacity) {
        s->capacity *= 2;
        s->data = realloc(s->data, s->capacity * sizeof(int));
    }
    s->data[s->size++] = x;    /* O(1) amortised */
}

int stack_pop(Stack *s) {
    return s->data[--s->size]; /* O(1) */
}

int stack_peek(const Stack *s) {
    return s->data[s->size - 1];
}

int stack_is_empty(const Stack *s) {
    return s->size == 0;
}

Linked-list-backed Stack

Maintain a pointer to the head. Push prepends a new node; pop removes the head. Both are strict O(1) with no amortised cost:

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

typedef struct {
    StackNode *head;
} LinkedStack;

void linked_stack_push(LinkedStack *s, int x) {
    StackNode *node = malloc(sizeof(StackNode));
    node->val = x;
    node->next = s->head;
    s->head = node;
}

int linked_stack_pop(LinkedStack *s) {
    StackNode *top = s->head;
    int val = top->val;
    s->head = top->next;
    free(top);
    return val;
}

The Queue

A queue enforces FIFO — First In, First Out:

• enqueue(x) — add x to the back
• dequeue() — remove and return the front element

Queues appear in breadth-first search, task scheduling, buffered I/O, and any system where order of arrival must be preserved.

Circular Buffer

A naive array queue shifts elements on every dequeue: O(n). A circular buffer fixes this with two indices — head and tail — that wrap around modulo the capacity. Both enqueue and dequeue become O(1):

typedef struct {
    int *buf;
    int head, tail, size, capacity;
} CircularQueue;

void cq_init(CircularQueue *q, int capacity) {
    q->buf = malloc(capacity * sizeof(int));
    q->head = q->tail = q->size = 0;
    q->capacity = capacity;
}

void cq_enqueue(CircularQueue *q, int x) {
    q->buf[q->tail] = x;
    q->tail = (q->tail + 1) % q->capacity;
    q->size++;
}

int cq_dequeue(CircularQueue *q) {
    int val = q->buf[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->size--;
    return val;
}

Linked-list Queue

Maintain both a head and a tail pointer. Enqueue appends to the tail; dequeue removes from the head. Both are O(1):

typedef struct QNode {
    int val;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *head;
    QNode *tail;
} LinkedQueue;

void lq_enqueue(LinkedQueue *q, int x) {
    QNode *node = malloc(sizeof(QNode));
    node->val = x;
    node->next = NULL;
    if (q->tail) q->tail->next = node;
    q->tail = node;
    if (!q->head) q->head = node;
}

int lq_dequeue(LinkedQueue *q) {
    QNode *front = q->head;
    int val = front->val;
    q->head = front->next;
    if (!q->head) q->tail = NULL;
    free(front);
    return val;
}

Deque

A deque (double-ended queue) supports O(1) push and pop at both ends. It is useful when you need stack and queue behaviour simultaneously — for example, in sliding window algorithms or implementing a history with a max size.

A common implementation uses a doubly-linked list of fixed-size blocks, giving O(1) at both ends with reasonable cache behaviour — the same approach taken by C++‘s std::deque.

Priority Queue

A priority queue extends the queue concept: each element carries a priority, and dequeue always removes the element with the highest priority (here: smallest numeric value). The canonical efficient implementation is a min-heap — a complete binary tree stored in an array where every parent is ≤ its children, so the minimum always sits at index 0.

typedef struct {
    int *data;
    int  size;
    int  capacity;
} PriorityQueue;

void pq_init(PriorityQueue *pq, int capacity) {
    pq->data = malloc(capacity * sizeof(int));
    pq->size = 0;
    pq->capacity = capacity;
}

/* push: append then bubble up until heap property is restored */
void pq_push(PriorityQueue *pq, int val) {
    pq->data[pq->size++] = val;
    int i = pq->size - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (pq->data[i] < pq->data[parent]) {
            int tmp = pq->data[i]; pq->data[i] = pq->data[parent]; pq->data[parent] = tmp;
            i = parent;
        } else break;
    }
}

/* pop: remove root, move last element to root, sift down */
int pq_pop(PriorityQueue *pq) {
    int min_val = pq->data[0];
    pq->data[0] = pq->data[--pq->size];
    int i = 0;
    while (1) {
        int l = 2*i+1, r = 2*i+2, smallest = i;
        if (l < pq->size && pq->data[l] < pq->data[smallest]) smallest = l;
        if (r < pq->size && pq->data[r] < pq->data[smallest]) smallest = r;
        if (smallest == i) break;
        int tmp = pq->data[i]; pq->data[i] = pq->data[smallest]; pq->data[smallest] = tmp;
        i = smallest;
    }
    return min_val;
}

int pq_peek(const PriorityQueue *pq) { return pq->data[0]; }
int pq_is_empty(const PriorityQueue *pq) { return pq->size == 0; }

Both pq_push and pq_pop are O(log n) — the heap height is ⌊log₂ n⌋. Priority queues are the backbone of Dijkstra’s algorithm (always process the nearest vertex), Huffman coding (always merge the two lightest trees), and any event-driven simulation (always fire the nearest-in-time event).

Stack Application: Expression Evaluation

One of the most elegant stack applications is converting and evaluating arithmetic expressions. Humans write 3 + 4 * 2 in infix notation (operator between operands). Compilers and calculators internally use postfix (operator after operands: 3 4 2 * +) because postfix evaluates left-to-right with a single stack and needs no parentheses or precedence rules.

Evaluating a Postfix Expression

Scan left-to-right: if the token is a number, push it; if it’s an operator, pop two operands, apply the operator, and push the result.

int evaluate_postfix(const char *expr) {
    Stack s;
    stack_init(&s, 64);

    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == ' ') continue;
        if (c >= '0' && c <= '9') {
            stack_push(&s, c - '0');           /* single-digit operand */
        } else {
            int b = stack_pop(&s);
            int a = stack_pop(&s);             /* a op b, not b op a */
            if      (c == '+') stack_push(&s, a + b);
            else if (c == '-') stack_push(&s, a - b);
            else if (c == '*') stack_push(&s, a * b);
            else if (c == '/') stack_push(&s, a / b);
        }
    }
    return stack_pop(&s);
}

evaluate_postfix("3 4 2 * +") correctly returns 11 (4 * 2 = 8, then 3 + 8 = 11), respecting multiplication’s higher precedence — embedded in the order the operators appear in the postfix string rather than in any explicit rule.

Converting Infix to Postfix: The Shunting-Yard Algorithm

Dijkstra’s shunting-yard algorithm converts infix to postfix using a stack to hold operators that are waiting to be emitted, enforcing precedence as it goes:

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void infix_to_postfix(const char *infix, char *out) {
    Stack ops;
    stack_init(&ops, 64);
    int k = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];
        if (c == ' ') continue;

        if (c >= '0' && c <= '9') {
            out[k++] = c; out[k++] = ' ';
        } else if (c == '(') {
            stack_push(&ops, c);
        } else if (c == ')') {
            while (!stack_is_empty(&ops) && (char)stack_peek(&ops) != '(') {
                out[k++] = (char)stack_pop(&ops); out[k++] = ' ';
            }
            stack_pop(&ops);                   /* discard the matching '(' */
        } else {                               /* +  -  *  / */
            while (!stack_is_empty(&ops) &&
                   precedence((char)stack_peek(&ops)) >= precedence(c)) {
                out[k++] = (char)stack_pop(&ops); out[k++] = ' ';
            }
            stack_push(&ops, c);
        }
    }
    while (!stack_is_empty(&ops)) { out[k++] = (char)stack_pop(&ops); out[k++] = ' '; }
    out[k] = '\0';
}

Both functions run in O(n) — each token is pushed and popped at most once. The two together form a classic compiler front-end: convert the expression once to postfix, then evaluate it efficiently any number of times, with no parenthesis parsing needed at evaluation time.

Complexity Summary

*Amortised for dynamic array backing.

Choosing Between Implementations

The array-backed versions have better cache locality and lower overhead per element. The linked-list versions never need resizing and have strict (non-amortised) O(1) operations. In practice, the array-backed versions are faster for most workloads.