Data Structures & Algorithms

Adding plates:      Removing plates:
    [3] ← Top         [3] ← Remove this first!
    [2]               [2]
    [1]               [1]
    ---               ---

class Stack:
    def __init__(self):
        self.items = []  # Using a list internally
    
    def push(self, item):
        """Add item to TOP - O(1)"""
        self.items.append(item)
    
    def pop(self):
        """Remove and return TOP item - O(1)"""
        if self.is_empty():
            return None
        return self.items.pop()
    
    def peek(self):
        """Look at TOP without removing - O(1)"""
        if self.is_empty():
            return None
        return self.items[-1]
    
    def is_empty(self):
        """Check if stack has no items"""
        return len(self.items) == 0
    
    def size(self):
        """How many items in stack"""
        return len(self.items)

# Let's use it!
stack = Stack()
stack.push(10)  # Stack: [10]
stack.push(20)  # Stack: [10, 20]
stack.push(30)  # Stack: [10, 20, 30]

print(stack.peek())  # 30 (just looking, not removing)
print(stack.pop())   # 30 (removed!)
print(stack.pop())   # 20
print(stack.peek())  # 10

def is_balanced(expression):
    """Check if parentheses are balanced"""
    stack = []
    
    for char in expression:
        if char == '(':
            stack.append(char)  # Push opening
        elif char == ')':
            if not stack:       # Nothing to match!
                return False
            stack.pop()         # Pop matching opening
    
    return len(stack) == 0      # Stack should be empty

# Examples
print(is_balanced("(())"))     # True
print(is_balanced("((())"))    # False - unmatched (
print(is_balanced("())"))      # False - unmatched )

Overflow  → Trying to PUSH when stack is FULL
Underflow → Trying to POP when stack is EMPTY

PUSH(stack, item):
  Step 1: if TOP == MAX_SIZE - 1
            Print "Stack Overflow"
            Return
  Step 2: TOP = TOP + 1
  Step 3: stack[TOP] = item

POP(stack):
  Step 1: if TOP == -1
            Print "Stack Underflow"
            Return
  Step 2: item = stack[TOP]
  Step 3: TOP = TOP - 1
  Step 4: Return item

  Array Implementation:

  Index:  [0] [1] [2] [3] [4]    MAX_SIZE = 5
  Values: [10][20][30][ ][ ]
                    ↑
                   TOP = 2

  Push 40:  [10][20][30][40][ ]   TOP = 3
  Pop:      [10][20][30][ ][ ]   TOP = 2, returns 40

#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;  // Empty stack

void push(int item) {
    if (top == MAX_SIZE - 1) {
        printf("Stack Overflow!\n");
        return;
    }
    stack[++top] = item;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return stack[top--];
}

int peek() {
    if (top == -1) return -1;
    return stack[top];
}

EVALUATE_POSTFIX(expression):
  Step 1: Scan expression LEFT to RIGHT
  Step 2: If OPERAND → Push to stack
  Step 3: If OPERATOR →
            Pop two operands (B = pop, A = pop)
            Compute result = A operator B
            Push result back to stack
  Step 4: Final value in stack = ANSWER

Step-by-step evaluation of: 1 2 + 3 4 2 / * -

Token  | Action              | Stack
-------|---------------------|----------
  1    | Push 1              | [1]
  2    | Push 2              | [1, 2]
  +    | Pop 2,1 → 1+2=3     | [3]
  3    | Push 3              | [3, 3]
  4    | Push 4              | [3, 3, 4]
  2    | Push 2              | [3, 3, 4, 2]
  /    | Pop 2,4 → 4/2=2     | [3, 3, 2]
  *    | Pop 2,3 → 3*2=6     | [3, 6]
  -    | Pop 6,3 → 3-6=-3    | [-3]

Result = -3  ✓

INFIX_TO_POSTFIX(expression):
  Create empty stack (for operators)
  Create empty output string

  Scan expression LEFT to RIGHT:
    If OPERAND → Add to output
    If '(' → Push to stack
    If ')' → Pop and add to output until '(' found
    If OPERATOR →
      While stack top has HIGHER or EQUAL precedence:
        Pop and add to output
      Push current operator to stack

  Pop remaining operators from stack → Add to output

Step-by-step conversion:

Token  | Action                          | Stack      | Output
-------|---------------------------------|------------|-------------------
  A    | Operand → output                |            | A
  +    | Push operator                   | [+]        | A
  (    | Push (                          | [+, (]     | A
  B    | Operand → output                | [+, (]     | A B
  -    | Push operator                   | [+, (, -]  | A B
  C    | Operand → output                | [+, (, -]  | A B C
  *    | * > - → Push                    | [+,(,-,*]  | A B C
  (    | Push (                          | [+,(,-,*,(]| A B C
  D    | Operand → output                | [+,(,-,*,(]| A B C D
  /    | Push operator                   | [+,(,-,*,(,/]| A B C D
  E    | Operand → output                | [+,(,-,*,(,/]| A B C D E
  ^    | ^ > / → Push                   | [+,(,-,*,(,/,^]| A B C D E
  F    | Operand → output                | [+,(,-,*,(,/,^]| A B C D E F
  )    | Pop until ( → ^, /              | [+,(,-,*]  | A B C D E F ^ /
  )    | Pop until ( → *, -              | [+]        | A B C D E F ^ / * -
  END  | Pop remaining → +               |            | A B C D E F ^ / * - +

Postfix: A B C D E F ^ / * - +  ✓

Infix (needs parentheses):    (A + B) * C   vs   A + (B * C)
Prefix (no parentheses):      * + A B C     vs   + A * B C
Postfix (no parentheses):     A B + C *     vs   A B C * +

Each expression is UNAMBIGUOUS without parentheses!

Adding to queue:        Removing from queue:
Front                   Front
  ↓                       ↓
[1] [2] [3] ← Back      [1] leaves first!

FRONT → points to first element
REAR  → points to last element

If FRONT = NULL (or -1), queue is EMPTY.

  Index:  [0] [1] [2] [3] [4]
  Values: [10][20][30][ ][ ]
           ↑         ↑
         FRONT     REAR

ENQUEUE(queue, item):
  Step 1: if REAR == MAX_SIZE - 1
            Print "Queue Overflow"
            Return
  Step 2: if FRONT == -1       // Queue was empty
            FRONT = 0
  Step 3: REAR = REAR + 1
  Step 4: queue[REAR] = item

DEQUEUE(queue):
  Step 1: if FRONT == -1
            Print "Queue Underflow"
            Return
  Step 2: item = queue[FRONT]
  Step 3: if FRONT == REAR     // Only one element was left
            FRONT = REAR = -1  // Queue becomes empty
          else
            FRONT = FRONT + 1
  Step 4: Return item

from collections import deque  # Double-ended queue

class Queue:
    def __init__(self):
        self.items = deque()  # More efficient than list
    
    def enqueue(self, item):
        """Add item to BACK - O(1)"""
        self.items.append(item)
    
    def dequeue(self):
        """Remove and return FRONT item - O(1)"""
        if self.is_empty():
            return None
        return self.items.popleft()  # Remove from left
    
    def front(self):
        """Look at FRONT without removing - O(1)"""
        if self.is_empty():
            return None
        return self.items[0]
    
    def is_empty(self):
        return len(self.items) == 0

# Let's use it!
queue = Queue()
queue.enqueue("Alice")   # Queue: [Alice]
queue.enqueue("Bob")     # Queue: [Alice, Bob]
queue.enqueue("Charlie") # Queue: [Alice, Bob, Charlie]

print(queue.front())    # Alice (first in line)
print(queue.dequeue())  # Alice (served first!)
print(queue.dequeue())  # Bob
print(queue.front())    # Charlie (now first)

Linear Queue Problem:
  [ ][ ][30][40][50]    FRONT=2, REAR=4
   ↑  ↑                 Wasted space!
  empty cells

Circular Queue Solution:
  QUEUE[1] comes after QUEUE[N]

         [1]
       /     \
    [5]       [2]
      |       |
    [4]       [3]
       \     /
         ---
  REAR wraps around to fill gaps!

Insertion:
  if REAR == N and there's space:
    Set REAR = 1 (instead of N + 1)    // Wrap around!
  Formula: REAR = (REAR + 1) % MAX_SIZE

Deletion:
  if FRONT == N:
    Set FRONT = 1 (instead of N + 1)   // Wrap around!
  Formula: FRONT = (FRONT + 1) % MAX_SIZE

All operations: O(1)

#define MAX 5
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int item) {
    if ((rear + 1) % MAX == front) {
        printf("Queue Overflow!\n");
        return;
    }
    if (front == -1) front = 0;  // First element
    rear = (rear + 1) % MAX;    // Wrap around
    queue[rear] = item;
}

int dequeue() {
    if (front == -1) {
        printf("Queue Underflow!\n");
        return -1;
    }
    int item = queue[front];
    if (front == rear)           // Last element
        front = rear = -1;
    else
        front = (front + 1) % MAX; // Wrap around
    return item;
}

General Deque:
  ← Insert/Delete    Insert/Delete →
       FRONT  [1] [2] [3]  REAR
  ← Insert/Delete    Insert/Delete →

Input Restricted:
  × No insert         Insert →
       FRONT  [1] [2] [3]  REAR
  ← Delete            Delete →

Output Restricted:
  ← Insert            Insert →
       FRONT  [1] [2] [3]  REAR
  ← Delete            × No delete

from collections import deque

dq = deque()

# Add from both ends
dq.append(3)       # Right: [3]
dq.appendleft(1)   # Left:  [1, 3]
dq.append(5)       # Right: [1, 3, 5]

# Remove from both ends
dq.pop()           # Remove 5 from right
dq.popleft()       # Remove 1 from left
# Result: [3]

import heapq

# Min heap - smallest value = highest priority
pq = []
heapq.heappush(pq, 30)  # Add 30
heapq.heappush(pq, 10)  # Add 10
heapq.heappush(pq, 20)  # Add 20

print(heapq.heappop(pq))  # 10 (smallest first!)
print(heapq.heappop(pq))  # 20
print(heapq.heappop(pq))  # 30

# Stack (using list)
stack = []
stack.append(1)  # Push (O(1))
stack.pop()      # Pop (O(1))

# Queue (using deque - NEVER use list for queues)
from collections import deque
q = deque()
q.append(1)    # Enqueue (O(1))
q.popleft()    # Dequeue (O(1))

# Priority Queue / Min-Heap
import heapq
pq = []
heapq.heappush(pq, 5) # O(log n)
lowest = heapq.heappop(pq) # O(log n)