Stack: Operations, Applications & Real-World Use

TAKEAWAYS:

• A stack follows Last-In-First-Out (LIFO)—the last element added is the first removed, like a stack of plates.
• Core operations are push (add), pop (remove), peek (view top), and isEmpty (check if empty).
• Stacks are implemented using arrays (fixed size) or linked lists (dynamic size), each with trade-offs.
• Applications include function call stacks (recursion), expression evaluation, undo/redo operations, and backtracking algorithms.
• Time complexity: O(1) for push/pop/peek (amortized for dynamic arrays), O(n) for resizing (rare).
• Overflow/underflow errors occur when pushing to a full stack or popping from an empty stack.

1. Definition and Characteristics

A stack is a linear data structure that stores elements in a Last-In-First-Out (LIFO) order. Think of a stack of plates:

• You can only add or remove plates from the top.
• The last plate placed is the first one taken.

Key Properties:

• Abstract Data Type (ADT): Defined by operations, not implementation.
• Dynamic size: Grows/shrinks as elements are added/removed.
• No random access: Only the top element is accessible directly.

2. Stack Operations

The stack supports four primary operations:

Visual: Stack Operations

flowchart TD
    A["Stack (Empty)"] -->|"push(5)"| B["Stack\n[5]"]
    B -->|"push(3)"| C["Stack\n[5, 3]"]
    C -->|"peek()"| D["Returns 3"]
    C -->|"pop()"| E["Stack\n[5]"]
    E -->|"pop()"| F["Stack (Empty)"]

Trace of push(5), push(3), peek(), pop(), pop():

3. Implementations

Stacks can be implemented using:

1. Arrays (static size)
2. Linked Lists (dynamic size)

Comparison Table

*Amortized O(1) due to occasional resizing (doubling the array size).

Visual: Array vs. Linked List Stack

graph LR
    subgraph Array Stack
        A["stack[0]"] --> B["stack[1]"] --> C["stack[2]"]
        D["top = 2"] --> C
    end
    subgraph Linked List Stack
        E["Node(5)"] --> F["Node(3)"] --> G["Node(1)"]
        H["top → G"] --> G
    end

4. Applications in Real World

Stacks are ubiquitous in computing and everyday systems. Here’s how they power apps and services in Nepal and globally:

Example 1: Function Call Stack (Recursion)

• Where? Every programming language (C, Java, Python) uses a stack to manage function calls.
• How? When a function is called, its return address and local variables are pushed onto the stack. When it returns, these are popped.
• Nepali Example: In a bank loan calculator app, recursive functions might compute compound interest:

  def calculate_interest(principal, rate, years):
      if years == 0:
          return principal
      return calculate_interest(principal * (1 + rate), rate, years - 1)
  

  Trace for calculate_interest(1000, 0.05, 2):

  Call Stack (Top to Bottom)	Action
  calculate_interest(1000, 0.05, 2)	Pushes (1000, 0.05, 2)
  calculate_interest(1050, 0.05, 1)	Pushes (1050, 0.05, 1)
  calculate_interest(1102.5, 0.05, 0)	Base case: returns 1102.5
  Pops and returns 1102.5	Unwinds stack

Example 2: Undo/Redo in Text Editors (e.g., Microsoft Word, Google Docs)

• Where? Every text editor or IDE (VS Code, Sublime Text).
• How? Each edit (typing, deleting) is pushed onto a stack. Pressing Ctrl+Z pops the last action.
• Nepali Example: In eSewa’s online form, if you accidentally fill wrong details, the undo button uses a stack to revert changes.

Example 3: Expression Evaluation (Postfix/Infix Notation)

• Where? Calculators (e.g., scientific calculators), compilers.
• How? Stacks evaluate expressions like 3 + 5 * 2 by following operator precedence.
• Nepali Example: Khalti’s transaction history might use stacks to parse and validate payment expressions (e.g., amount = 500 + tax(10%)).

Example 4: Backtracking Algorithms (e.g., Maze Solving)

• Where? Pathfinding (e.g., GPS navigation), game AI.
• How? Algorithms like Depth-First Search (DFS) use a stack to explore paths.
• Nepali Example: Pathao’s ride-matching system might use a stack to explore possible driver routes before selecting the fastest.

Example 5: Browser History (Back/Forward Buttons)

• Where? Web browsers (Chrome, Firefox), mobile apps (Facebook, Instagram).
• How? Two stacks manage back and forward navigation.
• Nepali Example: In Daraz’s product page, clicking "Back" uses a stack to return to previous pages.

5. Worked Example: Balanced Parentheses Checker

Problem: Given a string like "({[]})", determine if parentheses/brackets are balanced using a stack.

Algorithm Steps:

1. Initialize an empty stack.
2. For each character in the string:
   • If it’s an opening bracket (, {, [, push it onto the stack.
   • If it’s a closing bracket ), }, ], pop from the stack and check if it matches the top.
3. If the stack is empty at the end, the string is balanced.

Mermaid Flowchart:

flowchart TD
    A["Start"] --> B["Initialize empty stack"]
    B --> C["For each char in string:"]
    C --> D["If char is '(', '{', '[':"]
    D --> E["Push onto stack"]
    E --> F["Else if char is ')', '}', ']':"]
    F --> G["Pop from stack"]
    G --> H["If stack empty or top mismatch:"]
    H --> I["Return False"]
    I --> J["End"]
    H --> K["Continue"]
    K --> C
    C --> L["If stack empty:"]
    L --> M["Return True"]
    M --> J

Code Implementation (Python):

def is_balanced(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping.values():  # Opening bracket
            stack.append(char)
        elif char in mapping:        # Closing bracket
            if not stack or stack.pop() != mapping[char]:
                return False
    return not stack  # True if stack empty

Trace for "({[]})":

Trace for "({[}])" (unbalanced):

6. Advantages and Disadvantages

7. Common Pitfalls and Errors

1. Stack Overflow:

   • Occurs when pushing to a full stack (e.g., infinite recursion without a base case).
   • Fix: Use dynamic resizing (linked list) or check stack size before pushing.

2. Stack Underflow:

   • Occurs when popping from an empty stack.
   • Fix: Always check isEmpty() before popping.

3. Incorrect Matching (e.g., in parentheses):

   • Example: "([)]" is unbalanced because ] does not match (.
   • Fix: Ensure the stack’s top element matches the closing bracket.

4. Memory Leaks (Linked List Implementation):

   • Forgetting to free memory when popping nodes.
   • Fix: Always update pointers correctly.

8. Exam Tip

How This Unit is Examined:

• Theory (20-30%):

  • Define stack, LIFO, and operations (push, pop, peek, isEmpty).
  • Compare array vs. linked list implementations (time/space complexity).
  • Explain applications (e.g., recursion, undo mechanisms).

• Practical (70-80%):

  • Trace operations: Given a sequence of push/pop, draw the stack state after each step.
  • Code implementation: Write a stack using arrays or linked lists (often in C or Python).
  • Algorithm application: Solve problems like:
    • Balanced parentheses.
    • Infix to postfix conversion.
    • Tower of Hanoi (uses recursion + stack).
  • Debugging: Identify errors in given stack code (e.g., incorrect top pointer updates).

Common Exam Questions:

1. "Implement a stack using a linked list in C. Show how push(5), push(3), pop() affects the stack."
2. "Explain how a stack is used in evaluating the postfix expression 3 4 2 * 1 5 - / +."
3. "What happens if you pop() from an empty stack? How would you handle this in code?"
4. "Compare the time complexity of push and pop in array vs. linked list implementations."

Pro Tip:

• Draw the stack visually in exams—even if not asked, it clarifies your understanding.
• Memorize the trace table format for operations (like the one above for push/pop).
• Practice recursion problems (they rely heavily on the call stack).

Final Note: Stacks are foundational to algorithms and system design. Mastering them will help you tackle graphs (DFS), expression parsing, and system-level programming in later units. Practice tracing operations and implementing them in code!