Stacks

Introduction

A stack is a pile: you add to the top and take from the top, so the last item in is the first out (LIFO). Its operations:

Stacks are everywhere: the undo button, the browser's back button, and the call stack that the visualizer shows for every C program.

A stack is one of the smallest useful structures, and one of the most common. Whenever the most recent thing has to be dealt with first, whether an undo, a function call or an open bracket, a stack is the natural fit.

How it works

Using a stack: reversing

#include <stdio.h>

int main(void) {
    char word[] = "stack";
    char st[10];
    int top = -1;
    for (int i = 0; word[i] != '\0'; i++) st[++top] = word[i];
    while (top >= 0) putchar(st[top--]);
    putchar('\n');
    return 0;
}

Push every letter, then pop them all: they come out in reverse order. This small idea is behind many algorithms: undoing steps, checking brackets, and depth-first search.

A stack can also be built on a linked list, pushing and popping at the head, so it never gets full. You built that one in the C practice problem A stack as a linked list.

Syntax

typedef struct {
    int items[CAPACITY];
    int top;              // index of the top item; -1 when empty
} Stack;

bool push(Stack *s, int x);
bool pop(Stack *s, int *out);

Example

#include <stdio.h>
#include <stdbool.h>
#define CAPACITY 4

typedef struct {
    int items[CAPACITY];
    int top;   // index of the top item; -1 when empty
} Stack;

bool push(Stack *s, int x) {
    if (s->top == CAPACITY - 1) return false;   // overflow
    s->top++;
    s->items[s->top] = x;
    return true;
}

bool pop(Stack *s, int *out) {
    if (s->top == -1) return false;   // underflow
    *out = s->items[s->top];
    s->top--;
    return true;
}

int main(void) {
    Stack s;
    s.top = -1;
    for (int x = 10; x <= 50; x += 10)
        if (!push(&s, x)) printf("overflow: %d did not fit\n", x);
    int v;
    while (pop(&s, &v)) printf("popped %d\n", v);
    return 0;
}

The struct holds the array and top, the index of the top item. An empty stack has top == -1.

• push refuses when the array is full: that is overflow.
• pop refuses when the stack is empty: that is underflow. It returns the item through a pointer, *out, so that its return value can say whether it worked.

The functions take Stack *s, a pointer, so they change the caller's stack and not a copy. Notice the cells of items above top: they hold old values (or ?), but they are not part of the stack.

Line by line

1. Stack holds the array and top, and s.top = -1 in main makes it empty.
2. push refuses when top is at the last cell. Otherwise it moves top up and stores the value there.
3. pop refuses when top is -1. Otherwise it copies the top item through *out and moves top down.
4. The for loop tries to push five values, but the capacity is 4, so the push of 50 fails and prints a message.
5. The while loop pops until pop returns false, so the values come out newest first.

Expected result

overflow: 50 did not fit
popped 40
popped 30
popped 20
popped 10

In the real world

Every running program has a call stack: each function call pushes a frame holding its local variables, and each return pops one. Text editors keep undo stacks, and browsers keep a stack of the pages behind the Back button.

Common mistakes

• top starting at 0 instead of -1, so the first item goes into items[1].
• Popping without checking for an empty stack.
• Passing the struct by value: push(s, x) changes a copy, and the caller's stack stays empty.

Best practices

• Have pop report failure instead of returning a made-up value.
• Keep all changes to top inside push and pop.
• Decide what your program should do on overflow, then test it.

Summary

A stack adds and removes at one end, so the newest item leaves first. On an array, top is the index of the newest item, and both push and pop are O(1) as long as they check for full and empty.

Mark lesson complete