Stack-Data Structure

By /

Stack — Data Structure

Definition and Real-World Analogy

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle, meaning the most recently added item is the first one to be removed. Conceptually, it is similar to a stack of plates in a cafeteria: plates are added only on the top, and when you take a plate, you also remove it from the top. In computer science, the “top” is the only place where both insertion (called push) and deletion (called pop) can occur, which makes stacks simple and fast for well-structured access patterns. Stacks are pervasive in systems work and application design. They are used by compilers and run-time systems to keep track of nested function calls and local variables, by parsers to evaluate arithmetic and logical expressions, and by algorithms to implement depth-first search, backtracking, and undo/redo features. Because all operations target a single end, stack operations are typically O(1), with clear invariants and predictable behavior. When implemented carefully, stacks also encourage memory locality and low overhead. You will commonly see stacks implemented using arrays (fixed capacity, with an index known as top) or using linked lists (dynamic capacity, with a pointer to the top node). While both models are correct, their trade-offs differ in space overhead, cache behavior, and ease of detecting overflow. Understanding these foundations helps you design safe APIs and choose the right implementation for your constraints.

Core Operations and Terminology

  • push(x): Insert element x on the top of the stack.
  • pop(): Remove and return the top element; underflow if the stack is empty.
  • peek()/top(): Return (without removing) the top element; underflow if empty.
  • isEmpty(): True if no elements are present.
  • isFull(): True if the stack has reached its capacity (primarily for array-based stacks).

A correct stack implementation is governed by a few simple invariants that keep code safe and predictable. The top points to the most recent element, and it is the only place where insertion and deletion occur. This single-end discipline ensures that push and pop run in constant time, independent of the number of items. Two important exceptional conditions must be handled explicitly: underflow and overflow. Underflow occurs when pop or peek is attempted on an empty stack; this should be detected and reported before any memory access, returning a status code or raising an error. Overflow applies to array-based stacks when an insertion is attempted into a fully occupied array; you should detect this before writing past array bounds. Linked-list stacks don’t overflow in the same sense, but they can fail to allocate memory for a new node, which must be checked. In production code, these checks are accompanied by clear return values, error messages, or assertions. Consistent handling of these conditions, maintaining a clear contract for each operation, keeps the stack modular and easy to test, and prevents hard-to-debug memory corruption bugs.

Implementations

Array-Based Stack

An array-based stack uses a contiguous block of memory for storage and an integer index named top to indicate the position of the latest element. Initially, top is set to −1 to denote an empty stack. On push, you first check for overflow (top == capacity − 1), then increment top and assign data[top] = value. On pop, you check for underflow (top == −1), then read data[top] and decrement top. This model offers excellent cache locality and zero per-element pointer overhead, which is valuable for performance-sensitive code that pushes and pops frequently. However, its capacity is fixed at creation time; exceeding it either causes an error (which you must handle) or requires a resizing strategy. If you adopt resizing, your stack becomes an amortized O(1) structure with occasional O(n) expansions, similar to a dynamic array. For embedded systems or constrained environments, fixed-capacity stacks are often preferable because they avoid dynamic allocation and deliver predictable behavior. In all cases, thorough boundary checks are non-negotiable: never allow writes when the stack is full or reads when it is empty. Clear documentation of capacity, error codes, and state transitions will make your array stack straightforward to integrate and test.

// Array-based stack in C
#include <stdio.h>
#include <stdbool.h>

#define MAX 100

typedef struct {
    int data[MAX];
    int top; // -1 means empty
} Stack;

void init(Stack *s) { s->top = -1; }
bool isEmpty(const Stack *s) { return s->top == -1; }
bool isFull(const Stack *s) { return s->top == MAX - 1; }

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

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

bool peek(const Stack *s, int *out) {
    if (isEmpty(s)) return false;
    *out = s->data[s->top];
    return true;
}

int main(void) {
    Stack s; init(&s);
    push(&s, 10); push(&s, 20); push(&s, 30);
    int v;
    if (peek(&s, &v)) printf("Top = %d\n", v);
    while (pop(&s, &v)) printf("Popped %d\n", v);
    if (!pop(&s, &v)) printf("Underflow correctly detected\n");
    return 0;
}

Linked-List-Based Stack

A linked-list-based stack stores each element in a node that contains the value and a pointer to the next node. The stack’s top is simply a pointer to the head of the singly linked list. Pushing a value allocates a new node, fills its data field, links it to the current top, and makes it the new top. Popping removes the top node, returns its data, and frees the node’s memory. This approach supports conceptually “unbounded” growth, limited only by available memory, and it avoids the fixed-capacity constraint of arrays. It also makes the cost of push/pop independent of the stack size, remaining O(1) without resizing events. The trade-offs include extra memory for pointers, more frequent allocations (which can be slower than array writes), and potentially less cache locality. As with any structure that uses dynamic memory, careful error handling and cleanup are crucial: check allocation results, prevent memory leaks by freeing nodes on pop and at program exit, and avoid use-after-free by clearing pointers when appropriate. If your application involves many small stacks created and destroyed frequently, consider using memory pools or arenas to reduce allocation overhead while preserving the clarity and safety of the linked approach.

// Linked-list-based stack in C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top; // NULL means empty
} Stack;

void init(Stack *s) { s->top = NULL; }
bool isEmpty(const Stack *s) { return s->top == NULL; }

bool push(Stack *s, int x) {
    Node *n = (Node*)malloc(sizeof(Node));
    if (!n) return false;                // allocation failure
    n->data = x;
    n->next = s->top;
    s->top = n;
    return true;
}

bool pop(Stack *s, int *out) {
    if (isEmpty(s)) return false;        // underflow
    Node *n = s->top;
    *out = n->data;
    s->top = n->next;
    free(n);
    return true;
}

bool peek(const Stack *s, int *out) {
    if (isEmpty(s)) return false;
    *out = s->top->data;
    return true;
}

void clear(Stack *s) {
    int tmp;
    while (pop(s, &tmp)) { /* free via pop */ }
}

int main(void) {
    Stack s; init(&s);
    push(&s, 5); push(&s, 15); push(&s, 25);
    int v;
    while (pop(&s, &v)) printf("Popped %d\n", v);
    if (!pop(&s, &v)) printf("Underflow correctly detected\n");
    clear(&s);
    return 0;
}

Typical Applications

  • Function call management and recursion (the run-time call stack).
  • Expression evaluation and syntax parsing (postfix/prefix/infix conversions).
  • Balanced parentheses/brackets validation in compilers and editors.
  • Undo/redo systems in text and graphics software.
  • Browser navigation (back/forward stacks).
  • Depth-first search and backtracking in graphs and puzzles.
  • State restoration and transactional checkpoints.

Stacks shine wherever a problem unfolds and then must be resolved in the reverse order of occurrence. A classic example is the program call stack: when a function A calls B which calls C, local states are pushed in nested order, and returns unwind in the opposite order, ensuring each function finds its own environment intact. In compilers and calculators, stacks support evaluation of arithmetic expressions without requiring complex recursive descent for every subexpression; postfix evaluation, in particular, becomes a straightforward push-pop sequence over operands and operators. In user interfaces, stacks enable intuitive undo/redo: each action is pushed so that the last change can be reverted immediately, while a separate stack can track redo operations until a new action truncates that path. In algorithms, depth-first search leverages an explicit or implicit stack to explore branches to completion before backtracking, which is both memory-efficient and natural for problems like maze solving or generating permutations. Across these scenarios, the LIFO discipline enforces a clear computational order that reduces bookkeeping and helps prove correctness.

Common Pitfalls and Testing

Despite their simplicity, stacks can fail in subtle ways if invariants are not preserved. Off-by-one mistakes with the top index in array stacks can lead to silent memory corruption; a reliable pattern is to initialize top to −1, pre-increment on push, and post-decrement on pop, combined with clear boundary checks. Forgetting to check underflow on pop and peek is another frequent error—add early guards that return status codes, assert, or raise exceptions. With linked stacks, memory management errors dominate: always free nodes on pop, nullify top on clear, and handle allocation failures gracefully to avoid crashes. Test suites should include boundary tests (empty stack operations), capacity edge cases (pushing exactly to the array limit), randomized sequences of operations to simulate real workloads, and negative tests that intentionally provoke underflow and overflow conditions. Validate that the sequence of pushed items is reversed by pops, and that peek never changes state. For multi-threaded contexts, stacks require synchronization; race conditions around top can corrupt structure with catastrophic results. Prefer single-threaded ownership or protect operations with locks or lock-free algorithms designed specifically for concurrent stacks. Finally, expose a small, consistent API, document error behavior, and avoid leaking implementation details so you can swap array and linked variants without affecting callers.

Worked Example: Evaluating a Postfix Expression

Postfix (Reverse Polish) notation places operators after operands, eliminating the need for parentheses and simplifying evaluation with a stack. To evaluate, scan tokens from left to right. When you see a number, push it. When you see an operator, pop the right-hand operand, then the left-hand operand, apply the operator, and push the result. At the end, exactly one value should remain—the result. For example, the infix expression (3 + 4) × 5 becomes postfix 3 4 + 5 ×. Processing proceeds as follows: push 3, push 4, see + then pop 4 and 3, compute 7, push 7, push 5, see × then pop 5 and 7, compute 35, push 35; the final answer is 35. This strategy scales to multiple operators and respects precedence implicitly by the ordering of tokens in the postfix stream. In C, you can implement this with the array-based stack above. Be careful with division and subtraction, preserving operand order (right first, then left) when popping. Adding robust error checks for malformed input (too few operands, extra operands, or invalid tokens) is essential. This example illustrates how a disciplined LIFO structure turns grammar evaluation into a predictable sequence of constant-time operations, providing both efficiency and conceptual clarity.

// Simple postfix evaluator using the array-based stack
#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>

#define MAX 100
typedef struct { int data[MAX]; int top; } Stack;
void init(Stack *s){ s->top = -1; }
bool isEmpty(const Stack *s){ return s->top == -1; }
bool push(Stack *s,int x){ if(s->top==MAX-1) return false; s->data[++s->top]=x; return true; }
bool pop(Stack *s,int *out){ if(isEmpty(s)) return false; *out=s->data[s->top--]; return true; }

int apply(char op, int a, int b) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return b ? a / b : 0; // naive: no div-by-zero handling
    }
    return 0;
}

int evalPostfix(const char *expr, bool *ok) {
    Stack s; init(&s); *ok = true;
    for (const char *p = expr; *p; ++p) {
        if (*p == ' ') continue;
        if (isdigit((unsigned char)*p)) {
            push(&s, *p - '0');
        } else if (*p=='+'||*p=='-'||*p=='*'||*p=='/') {
            int rhs, lhs;
            if (!pop(&s, &rhs) || !pop(&s, &lhs)) { *ok = false; return 0; }
            push(&s, apply(*p, lhs, rhs));
        } else {
            *ok = false; return 0;
        }
    }
    int res;
    if (!pop(&s, &res) || !isEmpty(&s)) { *ok = false; return 0; }
    return res;
}

int main(void){
    bool ok; int v = evalPostfix("3 4 + 5 *", &ok);
    if (ok) printf("Result = %d\n", v);
    else printf("Malformed expression\n");
    return 0;
}

Complexity, Space, and Design Trade-offs

Both array-based and linked-list-based stacks provide O(1) time for push, pop, and peek under normal circumstances. The key differences lie in space overhead and constant factors. Array stacks use a contiguous block of memory and a single integer index, yielding excellent cache locality and minimal per-element overhead; however, they require a fixed capacity or a resizing strategy that occasionally incurs O(n) time to grow. Linked stacks have per-node pointer overhead and rely on dynamic allocation, which can cost more per operation and reduce locality, but they avoid pre-sizing and are bounded only by available memory. Error models differ as well: array stacks report overflow at capacity, while linked stacks primarily fail on allocation. In systems programming, fixed-capacity stacks are common for predictability, while in general-purpose applications linked stacks offer flexibility. If you anticipate rapid, large growth, you might favor dynamic arrays that double capacity to keep amortized push O(1), benefiting from contiguous storage and avoiding per-node pointers. If you need frequent interleaving of stacks and dynamic lifetimes, linked stacks with pooled allocation can minimize fragmentation. Ultimately, choose the implementation that fits your constraints: data volume, memory limits, error handling requirements, and performance profile. Regardless of choice, keep APIs consistent so the underlying representation can be swapped without impacting callers.

Crust Summary

  • A stack is a LIFO structure where both insertion and deletion occur at the top.
  • Core operations: push, pop, peek, isEmpty, and (for arrays) isFull; handle underflow/overflow explicitly.
  • Array stacks: fixed capacity, great locality, minimal overhead; consider resizing for flexibility.
  • Linked stacks: dynamic size, O(1) operations, higher per-element overhead; manage memory carefully.
  • Applications include call stacks, expression evaluation, parsing, DFS, backtracking, and undo/redo.
  • Test boundaries rigorously and preserve invariants to avoid corruption and leaks.
  • Both designs deliver O(1) operations; select based on capacity needs, memory constraints, and performance goals.

Related Posts

Scroll to Top