Stacks: short notes (Data Structures)

Revision mode

Introduction

A stack is a collection in which insertions and deletions happen at one end only, called the top. The element removed is always the one inserted most recently: last in, first out (LIFO). A stack of plates is the usual picture.

Stacks appear wherever work must be undone or resumed in reverse order: the call stack of a running program, undo histories, matching brackets, evaluating expressions, depth-first search and parsing. This note defines the stack, gives array and linked implementations with their costs, and treats the counting and validity questions about push and pop sequences. Expression conversion and evaluation are in Stack Applications.

Conventions: C11; arrays are 0-based; top is the index of the top element and is $-1$ for an empty array stack.

Prerequisites

Arrays and Their Relation to Pointers: array indexing.
Structures, Unions and Enumerations: self-referential structures for linked nodes.

Core concepts

The stack abstract data type

Operation	Effect	Error case
`push(S, x)`	put `x` on top	overflow if a fixed-capacity stack is full
`pop(S)`	remove and return the top element	underflow if `S` is empty
`top(S)` (or `peek`)	return the top element without removing it	underflow if empty
`isEmpty(S)`	true if no elements	none
`isFull(S)`	true if at capacity (array version)	none

All of these take $O(1)$ time in both standard implementations. Searching for an arbitrary element is not a stack operation; doing it needs $O(n)$ pops.

Array implementation

#define CAP 100
typedef struct { int a[CAP]; int top; } AStack;     /* top == -1 means empty */

void init(AStack *s) { s->top = -1; }
int push(AStack *s, int x) {
    if (s->top == CAP - 1) return 0;               /* overflow */
    s->a[++s->top] = x;                            /* increment, then store */
    return 1;
}
int pop(AStack *s, int *x) {
    if (s->top == -1) return 0;                    /* underflow */
    *x = s->a[s->top--];                           /* read, then decrement */
    return 1;
}

Empty: top == -1. Full: top == CAP - 1. Number of elements: top + 1.
A common alternative keeps top as the index of the next free slot (starting at 0); then push is a[top++] = x and pop is x = a[--top]. Both conventions are in use, so read the given code carefully.
Fixed capacity; growing needs reallocation (amortised $O(1)$ with doubling, see Dynamic Memory Allocation).

Linked implementation

The top is the head of a singly linked list; push inserts at the head and pop deletes the head, both $O(1)$ .

struct node { int val; struct node *next; };

int push(struct node **top, int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) return 0;                       /* only "overflow": no memory */
    n->val = x; n->next = *top; *top = n;
    return 1;
}
int pop(struct node **top, int *x) {
    struct node *n = *top;
    if (n == NULL) return 0;                       /* underflow */
    *x = n->val; *top = n->next; free(n);
    return 1;
}

Pushing at the tail of a singly linked list instead would make pop $O(n)$ , because finding the new tail needs a traversal.

Push and pop on an array stack and a linked stack — Figure 1. The same operations, push 10, push 20, push 30, pop, on an array stack (top index moving 0, 1, 2, 1) and on a linked stack (new nodes inserted at the head; pop removes the head node).

Aspect	Array stack	Linked stack
push, pop, top	$O(1)$	$O(1)$
Capacity	fixed (or amortised growth)	limited only by memory
Extra space	unused slots	one pointer per element
Locality	contiguous, cache-friendly	scattered nodes

Two stacks in one array

Two stacks can share one array of size $N$ without wasting space: stack 1 starts at index 0 and grows upward, stack 2 starts at index $N-1$ and grows downward.

int A[N], t1 = -1, t2 = N;                         /* both empty */
int push1(int x) { if (t1 + 1 == t2) return 0; A[++t1] = x; return 1; }
int push2(int x) { if (t1 + 1 == t2) return 0; A[--t2] = x; return 1; }

Overflow occurs only when the array is completely full: t1 + 1 == t2, which is the same as t1 == t2 - 1.

Stack versus recursion and the call stack

Stack versus queue. A stack is LIFO; a queue is FIFO. The same linear structure with opposite ends for insertion and deletion is a queue, not a stack. Which structure a code fragment implements can be decided by looking only at where inserts and deletes happen.

Underflow and overflow are not the same. Overflow is a capacity failure of a fixed array (or of malloc for a linked stack). Underflow is using pop or top on an empty stack. A correct implementation must test both; a missing underflow test is undefined behaviour in C when top is then used as an index.

The call stack is a stack. Each function call pushes a frame; each return pops one. C does not guarantee tail-call elimination, so assume each call pushes a frame unless told otherwise. An infinite recursion therefore overflows the call stack, which is a form of stack overflow distinct from overflowing an explicit array stack in the program.

How it works: valid pop sequences

Suppose $1, 2, \ldots, n$ are pushed in this order, and pops may be interleaved with the pushes at any moment. Which output (pop) orders are possible?

Simulation test. For each required output value $v$ : while the top is not $v$ , push the next input; if all inputs are pushed and the top is still not $v$ , the sequence is impossible; otherwise pop $v$ . For a length- $n$ permutation, this uses $\Theta(n)$ time and $O(n)$ auxiliary space with unit-cost stack operations.

Pattern test. An output permutation $p$ is achievable exactly when there are no positions $i < j < k$ with $p_j < p_k < p_i$ (no "3-1-2" pattern). Intuition: once a large value $p_i$ is output, every smaller value not yet output sits on the stack in increasing order from bottom to top, so those smaller values must come out in decreasing order.

Counting. The number of achievable output sequences is the Catalan number

C_n = \frac{1}{n+1}\binom{2n}{n}, \qquad C_3 = 5,\; C_4 = 14,\; C_5 = 42 .

Each achievable sequence corresponds to a sequence of $n$ pushes and $n$ pops in which no prefix has more pops than pushes, and such balanced sequences are counted by $C_n$ . The same numbers count binary tree shapes (Trees and Binary Trees).

Worked examples

C outputs below are for C11 with gcc on x86-64 Linux (LP64).

Example 1 (array stack overflow). With CAP 4, pushing 10, 20, 30, 40, 50: the fifth push fails, and top is 3. Two pops then return 40 and 30.

Example 2 (linked stack). push 1, push 2, push 3, pop, push 4, then pop until empty: the outputs are 3, then 4 2 1.

Example 3 (valid sequences, input 1 2 3 4).

3 2 1 4: push 1, 2, 3; pop 3, 2, 1; push 4; pop 4. Valid.
2 4 3 1: push 1, 2; pop 2; push 3, 4; pop 4, 3, 1. Valid.
4 2 3 1: after popping 4 the stack holds 1 2 3 (3 on top), so 2 cannot come next. Invalid (pattern 4, 2, 3).
1 4 2 3: invalid (pattern 4, 2, 3).

For input 1 2 3, the only impossible order among the 6 permutations is 3 1 2, leaving $C_3 = 5$ .

Example 4 (two stacks, $N = 5$ ). Alternating push1 and push2 of six values: the first five succeed and the sixth push (to stack 2) fails because t1 + 1 == t2 with t1 = 2, t2 = 3.

Important properties and observations

LIFO: the pop order is the reverse of the push order for elements still on the stack.
All stack operations are $O(1)$ ; a stack does not support efficient search or access by position.
Recursion uses the run-time call stack; any recursive algorithm can be converted to an iterative one with an explicit stack (Recursion).
A queue can be simulated with two stacks: push onto an in-stack; to dequeue, if the out-stack is empty move all elements from the in-stack to it, then pop it. Each element is moved at most once, giving amortised $O(1)$ per operation (Queues).
Depth-first search is the stack-based counterpart of breadth-first search (Depth-First Search).

GATE examination perspective

Trace a sequence of push and pop operations and report the final stack or the popped values.
Which output sequence is impossible? Use the simulation or the 3-1-2 pattern test.
Count achievable sequences: Catalan number.
Conditions in code: empty and full tests depend on whether top starts at $-1$ or 0.
Two stacks in one array: overflow when top1 == top2 - 1.
Queue from two stacks and its amortised cost.

Summary

Sources

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009: Section 10.1 (stacks and queues; Exercise 10.1-6 is the queue from two stacks), Chapter 17 (amortised analysis; Section 17.1 analyses a stack with a MULTIPOP operation).
D. E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., Addison-Wesley, 1997: Section 2.2.1 (stacks, queues and deques; permutations obtainable with a stack).