Stacks

Definition

A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. The last element inserted is the first one to be removed. Imagine a pile of books: you can add or remove only from the top.

Basic Operations

• push(x) — insert x on top.
• pop() — remove and return the top element.
• peek() / top() — return the top without removing it.
• isEmpty() — returns true if the stack has no elements.
• isFull() — for array-based stacks, true if capacity is reached.

All standard stack operations run in O(1) time.

Array Implementation

#define MAX 100
int stack[MAX];
int top = -1;
void push(int x) { if (top == MAX - 1) return; stack[++top] = x; }
int pop() { if (top == -1) return -1; return stack[top--]; }
int peek() { return (top == -1) ? -1 : stack[top]; }
int isEmpty() { return top == -1; }

Linked List Implementation

A linked list stack stores the top node in head. Push creates a new node and points it at the old head. Pop advances head to head->next and frees the old head. Both are O(1).

struct Node { int data; struct Node* next; };
struct Node* top = NULL;
void push(int x) {
    struct Node* n = malloc(sizeof(struct Node));
    n->data = x; n->next = top; top = n;
}
int pop() {
    if (!top) return -1;
    int x = top->data; struct Node* t = top; top = top->next; free(t); return x;
}

Applications

1. Function call stack — used by every language to manage local variables and return addresses.
2. Expression evaluation — converting infix to postfix and evaluating postfix expressions.
3. Parenthesis matching — verifying balanced brackets in source code.
4. Undo mechanism — text editors, graphic software push each action onto a stack.
5. Backtracking — maze solving, N-queens, DFS.
6. Browser history — back button pops the previous URL.

Infix to Postfix Conversion

Postfix notation (a b +) does not require parentheses and is easier for a computer to evaluate. The algorithm uses an operator stack: scan the infix expression left to right, output operands, push operators while respecting precedence, and pop for closing parentheses.

Evaluating a Postfix Expression

// For each token:
// if operand: push
// if operator: pop two, compute, push result
// Final stack top = answer.

Stack Overflow and Underflow

Overflow occurs when you try to push onto a full (fixed-size) stack. Underflow occurs when you pop from an empty stack. A robust implementation must guard against both.

Summary

Stacks are one of the simplest and most widely-used data structures. They manage function calls, parse expressions, and support undo and backtracking, all with O(1) per operation.

Important Questions

1. Define stack and explain LIFO with an example.
2. List stack operations and their time complexities.
3. Implement a stack using an array.
4. Implement a stack using a linked list.
5. Convert A + B * C to postfix using stack.
6. Evaluate the postfix expression 2 3 + 4 * step by step.
7. How does a stack support recursion?
8. List five real-world applications of stacks.