Stacks: LIFO, Operations, Applications & Expression Handling

TAKEAWAYS:

• A stack is a LIFO (Last-In-First-Out) structure where the last inserted element is the first to be removed, implemented via arrays or linked lists.
• Core operations (push, pop, peek, isEmpty) run in O(1) time, making stacks efficient for temporary storage and undo mechanisms.
• Infix-to-postfix conversion and postfix evaluation use stacks to handle operator precedence and parentheses without recursion.
• Stacks enable recursion via the call stack, where each function call is a stack frame storing local variables and return addresses.
• Applications include browser history, syntax checking (e.g., parentheses in code), and memory allocation (e.g., function calls in compilers).
• Disadvantages include fixed capacity (with array-based stacks) and no random access, limiting use cases compared to queues or linked lists.

1. Definition and Characteristics of a Stack

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element added to the stack is the first one to be removed. This structure is analogous to a stack of plates: you can only add or remove the topmost plate.

Key Characteristics:

• LIFO Principle: The most recently inserted item is the first to be deleted.
• Single Access Point: All operations (insertion/deletion) occur at the top of the stack.
• Dynamic Size: Can grow or shrink as elements are added or removed (unless implemented with a fixed-size array).
• No Random Access: Elements cannot be accessed directly; only the top element is accessible.

Real-World Analogy: Undo/Redo in Text Editors

When you press Ctrl+Z in Microsoft Word or Google Docs, the editor uses a stack to keep track of your actions. The most recent action (e.g., deleting text) is the first to be undone, demonstrating the LIFO principle.

2. Stack Operations

Stacks support four primary operations:

Visualization of Stack Operations

Let’s simulate a stack with the following operations: push(10), push(20), push(30), pop(), peek().

graph TD
  A["Stack after push(10)"] -->|"push(20)"| B["Stack after push(20)"]
  B -->|"push(30)"| C["Stack after push(30)"]
  C -->|"pop()"| D["Stack after pop() with 30 removed"]
  D -->|"peek()"| E["Stack after peek() (top: 20)"]

State After Each Operation:

1. After push(10):

   Top
   [10]
   

2. After push(20):

   Top
   [20]
   [10]
   

3. After push(30):

   Top
   [30]
   [20]
   [10]
   

4. After pop():

   Top
   [20]
   [10]
   

   (Returns 30)
5. After peek():

   Top
   [20]
   [10]
   

   (Returns 20 without removal)

3. Implementation of Stacks

Stacks can be implemented using:

1. Arrays: Fixed size, but simple to implement.
2. Linked Lists: Dynamic size, no fixed capacity.

Array-Based Implementation (Pseudocode)

class Stack:
    def __init__(self, capacity):
        self.stack = [None] * capacity
        self.top = -1

```figure
{"type":"array","values":[null,10,20,30,null],"highlight":[1,2,3],"pointers":{"top":3,"capacity":4},"caption":"Array-based stack with top pointer and capacity"}

def push(self, x):
    if self.top == len(self.stack) - 1:
        print("Stack Overflow")
    else:
        self.top += 1
        self.stack[self.top] = x

def pop(self):
    if self.isEmpty():
        print("Stack Underflow")
    else:
        x = self.stack[self.top]
        self.top -= 1
        return x

def peek(self):
    if self.isEmpty():
        print("Stack is empty")
    else:
        return self.stack[self.top]

def isEmpty(self):
    return self.top == -1

#### **Linked List-Based Implementation (Pseudocode)**
```python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

```figure
{"type":"linked-list","values":[30,20,10],"highlight":[0],"caption":"Linked list stack with top node highlighted"}

class Stack: def init(self): self.top = None

def push(self, x):
    new_node = Node(x)
    new_node.next = self.top
    self.top = new_node

def pop(self):
    if self.isEmpty():
        print("Stack Underflow")
    else:
        x = self.top.data
        self.top = self.top.next
        return x

def peek(self):
    if self.isEmpty():
        print("Stack is empty")
    else:
        return self.top.data

def isEmpty(self):
    return self.top is None

---
### **4. Applications of Stacks**
Stacks are widely used in various real-world scenarios:

```figure
{"type":"stack","values":["fib(3)","fib(2)","fib(1)","fib(0)"],"caption":"Call stack for `fib(3)` showing recursive function calls (top: most recent call)"}

a) Expression Evaluation (Infix to Postfix)

Stacks are crucial for converting and evaluating arithmetic expressions. For example:

• Infix: (A + B) * C - D
• Postfix: AB+C*D-

Algorithm for Infix to Postfix Conversion:

1. Initialize an empty stack and an empty output queue.
2. Traverse the infix expression from left to right.
3. If the token is an operand, add it to the output.
4. If the token is an operator:
   • While the stack is not empty and the top of the stack has higher or equal precedence, pop the operator to the output.
   • Push the current operator onto the stack.
5. After traversing, pop all remaining operators from the stack to the output.

Example: Convert (A + B) * C - D to Postfix

Infix: ( A + B ) * C - D
Steps:
1. Push '(' to stack.
2. 'A' → Output: A
3. '+' → Stack: [+]
4. 'B' → Output: A B
5. ')' → Pop until '(' is encountered: Output: A B +, Stack: []
6. '*' → Stack: [*]
7. 'C' → Output: A B + C
8. '-' → Stack: [-]
9. 'D' → Output: A B + C D
Final Postfix: AB+C*D-

b) Recursion and Call Stack

When a function calls another function, the call stack keeps track of the function calls. Each function call is a stack frame containing:

• Return address
• Local variables
• Arguments

Example: Fibonacci Function Call Stack

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

For fib(3), the call stack looks like this:

Stack Frame 1: fib(3) → calls fib(2) and fib(1)
Stack Frame 2: fib(2) → calls fib(1) and fib(0)
Stack Frame 3: fib(1) → returns 1
Stack Frame 4: fib(0) → returns 0
Stack Frame 2: fib(2) → returns 1 + 0 = 1
Stack Frame 1: fib(3) → returns 1 + 1 = 2

c) Backtracking Algorithms

Stacks are used in algorithms like maze solving or N-Queens problem to explore paths and backtrack when a dead end is reached.

Example: Maze Solving with Stack

Start: (0,0)
Path: (0,0) → (0,1) → (1,1) → (1,0) → (2,0)
If (2,0) leads to a dead end, backtrack to (1,0) and explore other paths.

d) Browser History

When you visit websites, the browser uses a stack to keep track of your history. Pressing Back removes the current page (LIFO) and loads the previous one.

e) Syntax Checking

Stacks are used to check for balanced parentheses, brackets, and braces in code. For example:

• Input: { [ ( ) ] }
• Stack operations:
  1. Push {, [, (
  2. Pop ), [, { → Balanced.

5. Comparison with Other Data Structures

6. Time and Space Complexity

In the real world

1. eSewa/Khalti Payment Stacks

   • When you initiate a payment, the app uses a stack to manage transaction steps (e.g., entering amount → selecting payment method → confirming). If you press "back," the stack pops the last step, reverting to the previous screen.

2. Daraz Order Processing

   • Daraz uses stacks to handle order queues for fulfillment. New orders are pushed onto the stack, and the most recent order (top of the stack) is processed first for same-day delivery, demonstrating LIFO for priority handling.

3. Pathao Driver Route Planning

   • Pathao’s algorithm for optimizing driver routes uses a stack to backtrack and find the shortest path when a route is blocked. For example, if a street is congested, the app pops the current route and pushes a new alternative path onto the stack.

4. NEPSE Stock Market Trades

   • When traders place buy/sell orders, the exchange uses a stack to manage limit orders. The most recent order (top of the stack) is processed first, ensuring fairness in execution.

Worked Example: Evaluate Postfix Expression

Postfix Expression: 3 4 2 * + Steps:

1. Push 3 → Stack: [3]
2. Push 4 → Stack: [3, 4]
3. Push 2 → Stack: [3, 4, 2]
4. * encountered → Pop 2 and 4, compute 4 * 2 = 8 → Push 8 → Stack: [3, 8]
5. + encountered → Pop 8 and 3, compute 3 + 8 = 11 → Push 11 → Stack: [11]
6. Final result: 11

Code Implementation:

def evaluate_postfix(expression):
    stack = []
    tokens = expression.split()
    for token in tokens:
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)
    return stack.pop()

# Example
print(evaluate_postfix("3 4 2 * +"))  # Output: 11

Exam Tip

1. Master Stack Operations:

   • Always show the state of the stack after each operation in your answers. Examiners expect visual traces for push, pop, and peek.
   • Example: For (A + B) * C - D → Postfix, label each step clearly (e.g., "Push 'A' → Stack: [A]").

2. Algorithm Steps:

   • For infix-to-postfix conversion, list the precedence rules (e.g., * and / have higher precedence than + and -) and show how the stack handles operators.
   • Example:

     Precedence: * / > + -
     Step 1: Push '(' → Stack: [(]
     Step 2: 'A' → Output: A
     Step 3: '+' → Stack: [+, (]
     

3. Real-World Tie-Ins:

   • Link stack concepts to recursion (call stack), browser history, or undo mechanisms in apps like Microsoft Word. Use examples like:

     "When you press Ctrl+Z in Word, the editor uses a stack to undo the last action (e.g., deleting text). The most recent deletion is the first to be undone, demonstrating LIFO."

4. Avoid Common Mistakes:

   • Fixed-size arrays: If the stack is implemented with an array, mention how push fails if the stack is full (overflow).
   • Postfix evaluation: Ensure you pop two operands before applying an operator (e.g., for 3 4 +, pop 4 and 3, then compute 3 + 4).

5. Time Complexity:

   • Always state that all stack operations are O(1) unless using a linked list with a tail pointer (still O(1) for push/pop at head).

6. Diagrams:

   • Draw the stack before and after each operation. For example:

     Before push(5): []
     After push(5): [5]
     

   • Use mermaid diagrams for algorithm flows (e.g., infix-to-postfix conversion). Example:

Final Note: Stacks are a fundamental building block in computer science. Focus on visualizing operations and applying them to real-world scenarios like expression evaluation or recursion. Practice tracing stack states for infix/postfix conversions—this is a high-weightage topic in exams!