Stack

Description

In computer science, a stack is an abstract data type (ADT) that serves as a collection of elements with two principal operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the element from the top of the stack.

The stack operates on a Last-In, First-Out (LIFO) principle, meaning that the most recently added item is the first one to be removed. This simple yet powerful concept has widespread applications in computer architecture, algorithm design, memory management, language parsing, and recursion.

Stacks can be implemented using arrays or linked lists, and they form the foundation for several system-level processes and algorithms.

Real-World Analogy

Imagine a stack of books on a desk:

• You can only remove the top book (pop).
• If you want to add a new book, you place it on top (push).
• You cannot access books in the middle directly—you must pop until you reach the desired level.

This strict discipline enables precise and predictable control, which makes stacks invaluable in programming.

Key Operations

Stack Implementation in Code

Using Python (List-Based)

stack = []

# Push
stack.append(10)
stack.append(20)

# Peek
print(stack[-1])  # 20

# Pop
print(stack.pop())  # 20

# Check if empty
print(len(stack) == 0)

Using Java

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.peek()); // 20
System.out.println(stack.pop());  // 20

Using C++

#include <stack>
std::stack<int> s;
s.push(10);
s.push(20);
int top = s.top(); // 20
s.pop();           // remove 20

Applications of Stack

1. Function Call Management

• Stacks are used in call stacks to store function calls and local variables.
• When a function is invoked, its context is pushed onto the stack.
• When it returns, the context is popped.

2. Undo/Redo Functionality

• Applications like word processors or drawing apps use stacks to record actions.
• An “undo” pops the last action; a “redo” pushes it back.

3. Expression Evaluation

• Used to convert infix to postfix/prefix notations.
• Evaluate expressions such as 3 + (4 * 5) by processing operators and operands via stack.

4. Syntax Parsing

• Compilers and interpreters use stacks to parse brackets, parentheses, and nested structures.
• Detect balanced parentheses: ((())) → valid, (() → invalid.

5. Depth-First Search (DFS)

• DFS traversal in graphs or trees is implemented using a stack (explicit or via recursion).

6. Backtracking

• Algorithms like Sudoku solver, N-Queens, and maze exploration use stacks to backtrack to previous states.

7. Web Browser History

• Stores visited URLs.
• Hitting “Back” pops the last visited page.

Stack Memory in Programming

Most programming languages use a region of memory called the stack to store:

• Function call frames
• Local variables
• Return addresses

This is distinct from the heap, which stores dynamically allocated memory.

Stack vs Heap:

Stack Overflow

Occurs when the stack grows beyond its allocated memory space, often due to:

• Infinite recursion
• Deep call nesting

Example:

def recurse():
    recurse()  # No base case

recurse()  # Causes stack overflow

In C/C++, this can crash the program or lead to undefined behavior.

Advanced Stack Techniques

Multi-Stack in a Single Array

• Used in constrained memory environments.
• Divide array into fixed-size parts or dynamically manage pointers.

Two Stacks in One Array

• Stack A grows from left to right.
• Stack B grows from right to left.
• Prevents memory waste.

Stack with Min/Max

• Augmented stacks that allow O(1) retrieval of min/max.
• Maintain auxiliary stack to track minimums.

Postfix Evaluation

expr = "3 4 + 2 *"
stack = []
for token in expr.split():
    if token.isdigit():
        stack.append(int(token))
    else:
        b, a = stack.pop(), stack.pop()
        result = eval(f"{a}{token}{b}")
        stack.append(result)
print(stack[0])  # 14

Visual Representation

Imagine the following sequence:

Stack: []
Push 10 → [10]
Push 20 → [10, 20]
Peek → 20
Pop → [10]

A stack visually grows vertically, and only the top element is accessible.

When Not to Use a Stack

• If you need random access to elements (use array or list).
• If operations happen from both ends (use deque or queue).
• If elements need sorting or prioritization (use priority queue or heap).

Related Terms

• Queue: FIFO data structure
• Deque: Double-ended queue
• Call Stack
• Recursion
• Backtracking
• Memory Allocation
• Dynamic Programming (memoization)
• Prefix/Infix/Postfix notation
• Abstract Data Type (ADT)
• LIFO
• Stack Overflow
• Heap Memory
• Syntax Tree