Stack (computing)

A stack is a LIFO (last-in, first-out) data structure: you can only access the most recently added item. The two core operations are push (add an item to the top) and pop (remove the top item). A common third is peek (read the top without removing it).

The metaphor is a stack of plates: you put a plate on top, you take a plate from the top, you can’t reach into the middle without disturbing everything above.

Two perspectives

The stack appears in two related but distinct contexts in this vault:

Stack as data structure (this section + abstract data type): a generic LIFO container used in algorithms, language runtimes, and applications.
Processor stack (computer architecture): a specific in-memory region the CPU uses for subroutine return addresses, saved registers, and local variables. See the bottom section.

The data-structure stack is general; the processor stack is one application.

Operations

The standard interface:

push(item) — put an item on top.
pop() — remove and return the top item.
peek() (or top()) — return the top item without removing it.
isEmpty() — check if the stack is empty.

Optional: size(), clear().

Implementation requirements:

A top variable (index or pointer) marking the topmost element.
A special value (or counter at $- 1$ ) indicating the stack is empty.
Error handling for popping an empty stack and pushing onto a full one.

Use cases

LIFO order is exactly what you want when:

Reversing things. Push characters of a word, pop to print in reverse.
Backtracking. Web browsers’ “back” button — push each visited URL, pop to go back.
Undo functionality. Each action pushes the inverse onto an undo stack.
Expression evaluation. Postfix (RPN) calculators use stacks to hold operands.
Matching brackets. Push every opening bracket; on every closer, pop and check it matches.
Recursion implementation. The processor’s call stack holds the chain of in-progress function calls.

Implementation 1: array-based

Use a fixed-size array plus a top index pointing to the topmost element. top = -1 means empty.

typedef struct {
    int top;
    int data[100];
} ArrayStk;
 
int push(ArrayStk *stk, int n) {
    if (stk->top == 99) return 0;       // full
    stk->data[++stk->top] = n;
    return 1;
}
 
int pop(ArrayStk *stk, int *value) {
    if (stk->top == -1) return 0;       // empty
    *value = stk->data[stk->top--];
    return 1;
}

++stk->top (pre-increment) advances top first, then stores. stk->data[stk->top--] (post-decrement) reads first, then decrements.

Worked example with size 4:

Pushing 4, 7, 13, 8 fills the array; popping returns them in reverse order: 8, 13, 7, 4.

Pros: O(1) push/pop, contiguous memory (cache-friendly), no per-element allocation overhead.

Cons: fixed capacity. Push on a full stack fails.

Implementation 2: linked-list-based

Each node holds the value and a pointer to the node below. The stack’s “head” pointer is the top.

typedef struct _stk_node {
    struct _stk_node *next;   // pointer to node below
    int               nodval;
} StkNode;
 
void push(StkNode **stkHead, int n) {
    StkNode *p = malloc(sizeof *p);
    p->nodval = n;
    p->next   = *stkHead;     // chain to old top
    *stkHead  = p;            // new node becomes top
}
 
int pop(StkNode **stkHead, int *out) {
    if (*stkHead == NULL) return 0;
    StkNode *p = *stkHead;
    *out = p->nodval;
    *stkHead = p->next;       // drop top
    free(p);
    return 1;
}

Pushing prepends a node; popping detaches the head. Both O(1).

Pros: no fixed capacity — grows as long as memory allows.

Cons: per-node malloc overhead, scattered memory (cache-unfriendly), each node uses an extra pointer’s worth of memory.

Which to use

Array-based wins for fixed, predictable workloads where the maximum size is known. Linked-list-based wins when the stack might grow arbitrarily large or when you don’t want a hard size limit. In practice, modern stacks are often built on dynamic arrays (Dynamic array) — array-style indexing with the linked list’s unbounded growth, at the cost of occasional reallocation.

Modifying the top element

A useful function tos (top-of-stack) returns a pointer to the top element so it can be modified in place:

int tos(ArrayStk *stk, int **ptop) {
    if (stk->top == -1) return 0;
    *ptop = &stk->data[stk->top];
    return 1;
}

Then you can do *ptr_top = *ptr_top + 50; to add 50 to the top of the stack without popping and re-pushing.

Processor stack (computer architecture)

Beyond being a generic data structure, the processor stack is a specific region of memory the CPU uses during program execution. It serves three purposes:

Subroutine return addresses. When a function is called, the return address is pushed; ret pops and jumps. Allows nested function calls to nest arbitrarily deep.
Saved registers. A function pushes registers it needs to preserve, restores them before returning. See Subroutine linkage.
Local variables. Variables declared inside a function live in the function’s Stack frame until the function returns.

The CPU has a dedicated register called the stack pointer (SP, r27/sp in Nios II) that always points at the top of the stack. In most architectures, the stack grows downward in memory — pushing decrements SP first, then writes; popping reads, then increments SP.

Stack manipulation in Nios II:

# Push r5
subi sp, sp, 4
stw  r5, 0(sp)

# Pop r5
ldw  r5, 0(sp)
addi sp, sp, 4

Two instructions per push or pop — there’s no dedicated push/pop instruction in this RISC ISA. The operations are exactly the same as the linked-list stack pattern, just with hardware-managed pointers.

Importantly, popping doesn’t erase the popped value — only the stack pointer moves. The data sits in memory above SP. Treating that memory as “still mine” is dangerous: an interrupt arriving between pop and any later read can push its own frame onto the stack, overwriting your popped data with the ISR’s saved context. Multithreaded preemption can do the same. So never read or write memory above SP — once you’ve popped, the bytes are formally garbage even though they happen to still be in DRAM.

For the related concepts of frame layout, calling conventions, and nested calls: Stack frame, Subroutine linkage, Subroutine nesting.

Stack overflow

The stack has a finite size (typically 1–8 MB per thread in modern OSes). If too many nested calls or too-large frames push SP past the allocated region, you get a stack overflow — the stack writes into other memory or triggers a fault. Deep recursion is the classic trigger; this is why iterative algorithms are sometimes preferred over recursive ones for very deep recursion patterns.

For the alternative O(1)-but-FIFO ordering, see Queue.

Idriss Rami — Notes

Explorer