Linked stacks and queues

Learning outcomes

Use linked-list operations to implement stack and queue ADTs, and preserve endpoint invariants through empty transitions.

9.1 Linked stack

Let top point to the first node. Push is insertion at the head; pop is deletion at the head. Both perform a constant number of pointer updates. A push also requires allocation, which can fail. “No fixed capacity” is not the same as unlimited memory.

PUSH(x):
    allocate new node; if allocation fails, report failure
    new.value = x
    new.next = top
    top = new

POP():
    if top is NULL: report underflow
    old = top
    result = old.value
    top = old.next
    free old
    return result

After pushing 10, 20 and 30, top points to 30 → 20 → 10 → NULL. Popping returns 30 and leaves 20 → 10 → NULL. The operation must save the returned value before freeing its node.

The pointer-update cost is Θ(1); the cost of the system allocator is normally abstracted away in this introductory analysis. Displaying all elements is Θ(n), and total node storage is Θ(n). If constant-time size is required, maintain a count rather than traversing for every size query.

9.2 Linked queue

A queue retains two endpoints: front points to the next item to remove, and rear points to the last node. Enqueue at rear and dequeue at front.

Invariant: an empty queue has both front and rear null. A nonempty queue has a reachable rear node whose next link is null.

ENQUEUE(x):
    allocate new node; if allocation fails, report failure
    new.value = x; new.next = NULL
    if rear is NULL: front = new
    else: rear.next = new
    rear = new

DEQUEUE():
    if front is NULL: report underflow
    old = front; result = old.value
    front = old.next
    if front is NULL: rear = NULL
    free old
    return result

The reset of rear is essential. Without it, removing the final node leaves a dangling rear pointer, and a later enqueue may write through freed storage.

9.3 Worked boundary trace

Each enqueue or dequeue performs Θ(1) link work. No shifting or modular arithmetic is needed, but node links and allocations add overhead. For a bounded buffer with predictable memory use, a circular array may be the better choice.

9.4 Design the API around failure

Returning a special integer such as −1 is ambiguous if −1 is valid data. A boolean success result plus an output pointer separates status from value. The output remains unchanged on failure. Document pointer validity as a precondition and define who owns each allocated node.

Test an empty pop, a full lifecycle from empty to populated and back, repeated reuse after emptying, and cleanup with remaining elements. Allocation-failure testing requires a controllable allocator or fault-injection wrapper; ordinary successful runs do not prove that path was executed.

Practice

1. Show the linked stack after pushing 7, pushing 9, popping, and pushing 4.
2. Explain why a linked queue with only a front pointer cannot generally enqueue in Θ(1) time.
3. Identify the unsafe statement if code frees old before evaluating old->next.
4. Write a queue cleanup algorithm and state its final endpoint invariant.

/* C11. Linked stack and queue with explicit allocation and ownership. */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *next; } Node;
typedef struct { Node *top; } Stack;
typedef struct { Node *front, *rear; } Queue;
static Node *make_node(int value)
{
    Node *p = malloc(sizeof *p);
    if (p != NULL) *p = (Node){value, NULL};
    return p;
}
static bool push(Stack *s, int value)
{
    Node *p = make_node(value);
    if (p == NULL) return false;
    p->next = s->top; s->top = p; return true;
}
static bool pop(Stack *s, int *out)
{
    if (s->top == NULL) return false;
    Node *p = s->top; *out = p->value; s->top = p->next; free(p); return true;
}
static bool enqueue(Queue *q, int value)
{
    Node *p = make_node(value);
    if (p == NULL) return false;
    if (q->rear == NULL) q->front = p;
    else q->rear->next = p;
    q->rear = p; return true;
}
static bool dequeue(Queue *q, int *out)
{
    if (q->front == NULL) return false;
    Node *p = q->front; *out = p->value; q->front = p->next;
    if (q->front == NULL) q->rear = NULL; /* Never leave a dangling tail. */
    free(p); return true;
}
static void clear_stack(Stack *s) { int ignored; while (pop(s, &ignored)) {} }
static void clear_queue(Queue *q) { int ignored; while (dequeue(q, &ignored)) {} }
int main(void)
{
    Stack s = {NULL}; Queue q = {NULL, NULL}; int value = -1;
    assert(!pop(&s, &value) && !dequeue(&q, &value) && value == -1);
    for (int i = 1; i <= 3; ++i) {
        if (!push(&s, i) || !enqueue(&q, i)) {
            clear_stack(&s); clear_queue(&q); return EXIT_FAILURE;
        }
    }
    printf("Linked stack:");
    for (int i = 3; i >= 1; --i) {
        assert(pop(&s, &value) && value == i); printf(" %d", value);
    }
    putchar('\n');
    printf("Linked queue:");
    for (int i = 1; i <= 3; ++i) {
        assert(dequeue(&q, &value) && value == i); printf(" %d", value);
    }
    putchar('\n'); assert(q.front == NULL && q.rear == NULL && s.top == NULL);
    for (int i = 0; i < 100; ++i) {
        assert(enqueue(&q, i)); assert(dequeue(&q, &value) && value == i);
        assert(q.front == NULL && q.rear == NULL);
    }
    assert(push(&s, 9) && enqueue(&q, 9));
    clear_stack(&s); clear_queue(&q); clear_stack(&s); clear_queue(&q);
    assert(s.top == NULL && q.front == NULL && q.rear == NULL);
    puts("linked stack/queue tests passed");
    return EXIT_SUCCESS;
}