Stacks

Stack

A stack, also called a pushdown stack, is an operation-restricted linear data structure. Insertion and deletion can take place only at the end of the structure.

Elements in a stack follow first in, last out (FILO). The position occupied by the earliest element is called the bottom, and the position occupied by the latest element is called the top.

A stack can be implemented with either an array or a linked list.

Sequential Stack

A stack implemented with an array is called a static stack. An array index can represent the location of the top; for an empty stack, top is -1.

During a push, the top pointer increases by 1. During a pop, it decreases by 1.

Pushing onto a full stack or popping from an empty stack crosses the array boundary and can crash the program. These conditions are called overflow and underflow. A sequential stack therefore requires an array size in advance. Too little space can cause overflow, while too much wastes space.

An array-backed stack is generally more efficient than a linked implementation. Push and pop do not move many elements; they move only the top pointer.

Linked Stack

A stack implemented with a linked list is called a dynamic stack. Inserting at the head performs a push, and deleting at the head performs a pop.

A dynamic stack inherits some linked-list properties: its elements need not be contiguous in physical storage. Its operations are restricted, however, to insertion and deletion at the top rather than at the tail or in the middle.

Dynamic-stack nodes are allocated as needed, avoiding unused fixed capacity, but allocating and releasing memory carries additional overhead.

Push

Push places a new element into the stack, only from the top side. The new element becomes the new top. Initially the stack is empty and top is -1. Each added element increases top by 1.

Push affects only the last element and does not move the entire collection, so it takes $O(1)$ for a fixed-capacity array stack or linked stack.

The dynamic-array examples below have amortized $O(1)$ push; a push that resizes the array takes $O(n)$.

stack_t *stack_push(stack_t *stack, T elem) {
    if (stack == NULL) {
        return NULL;
    }
    array_add(stack->data, elem);
    return stack;
}

Pop

Pop removes an element from the stack. Only the top element may leave, and its predecessor becomes the new top. Removing an element decreases top by 1. In an array, the value need not be physically erased; a later push overwrites it.

Pop affects only the last element and does not move the entire collection, so its time complexity is $O(1)$ for either implementation.

T stack_pop(stack_t *stack) {
    if (stack == NULL) {
        exit(1);
    }
    return array_remove(stack->data, stack_size(stack) - 1);
}