Unit 3: Stacks, Queues & Recursion

Python — Array-based Stack

Python
class ArrayStack:
    """Stack using a fixed-size array.
    Industry: Paytm's payment gateway uses a stack to undo
    transaction steps if OTP verification fails."""

    def __init__(self, capacity):
        self.stack = [None] * capacity
        self.top = -1          # -1 means empty
        self.capacity = capacity

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

    def is_full(self):
        return self.top == self.capacity - 1

    def push(self, value):
        """Add element to top. O(1)."""
        if self.is_full():
            print("Stack Overflow!")
            return
        self.top += 1
        self.stack[self.top] = value

    def pop(self):
        """Remove and return top element. O(1)."""
        if self.is_empty():
            print("Stack Underflow!")
            return None
        value = self.stack[self.top]
        self.top -= 1
        return value

    def peek(self):
        if self.is_empty(): return None
        return self.stack[self.top]

    def display(self):
        print("Stack (top→bottom):", self.stack[self.top::-1] if self.top >= 0 else "(empty)")


# === Driver ===
s = ArrayStack(5)
for val in [10, 20, 30]:
    s.push(val)
s.display()
print(f"Pop: {s.pop()}")
print(f"Peek: {s.peek()}")
s.display()

Python — Linked-List-based Stack

Python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedStack:
    """Stack using linked list — no size limit (dynamic)."""
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top   # New node points to old top
        self.top = new_node        # Update top
        self.size += 1

    def pop(self):
        if not self.top:
            print("Stack Underflow!"); return None
        data = self.top.data
        self.top = self.top.next   # Move top to next
        self.size -= 1
        return data

    def display(self):
        curr, parts = self.top, []
        while curr:
            parts.append(str(curr.data)); curr = curr.next
        print("Top → " + " → ".join(parts) + " → NULL")


ls = LinkedStack()
for v in [100, 200, 300]: ls.push(v)
ls.display()
print(f"Pop: {ls.pop()}")
ls.display()

C — Array-based Stack

C
#include <stdio.h>
#define MAX 100

int stack[MAX], top = -1;

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

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

int main() {
    push(10); push(20); push(30);
    printf("Pop: %d\n", pop());  // 30
    printf("Pop: %d\n", pop());  // 20
    return 0;
}

Python — Circular Array Queue

Python
class CircularQueue:
    """Queue using circular array — prevents the 'false full' problem.
    Industry: Swiggy's order pipeline uses this exact pattern."""

    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = -1
        self.rear = -1
        self.capacity = capacity
        self.size = 0

    def is_empty(self): return self.size == 0
    def is_full(self): return self.size == self.capacity

    def enqueue(self, value):
        """Add element at rear. O(1)."""
        if self.is_full():
            print("Queue is full!"); return
        if self.is_empty():
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity  # Circular wrap
        self.queue[self.rear] = value
        self.size += 1

    def dequeue(self):
        """Remove element from front. O(1)."""
        if self.is_empty():
            print("Queue is empty!"); return None
        value = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity  # Circular wrap
        self.size -= 1
        if self.is_empty():  # Reset if empty
            self.front = self.rear = -1
        return value

    def display(self):
        if self.is_empty(): print("Queue: (empty)"); return
        parts = []
        for i in range(self.size):
            idx = (self.front + i) % self.capacity
            parts.append(str(self.queue[idx]))
        print("Front ← " + " ← ".join(parts) + " ← Rear")


# === Driver: Swiggy order queue ===
orders = CircularQueue(5)
orders.enqueue("Order#101-Biryani")
orders.enqueue("Order#102-Pizza")
orders.enqueue("Order#103-Dosa")
orders.display()
print(f"Processing: {orders.dequeue()}")
orders.enqueue("Order#104-Momos")
orders.display()

C — Array Queue + Linked List Queue

C
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

/* Array-based circular queue */
int q[MAX], front = -1, rear = -1, qsize = 0;

void enqueue(int val) {
    if (qsize == MAX) { printf("Full!\n"); return; }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    q[rear] = val; qsize++;
}

int dequeue() {
    if (qsize == 0) { printf("Empty!\n"); return -1; }
    int val = q[front];
    front = (front + 1) % MAX;
    qsize--;
    return val;
}

/* Linked-list queue */
struct QNode { int data; struct QNode* next; };
struct QNode *qfront = NULL, *qrear = NULL;

void llEnqueue(int val) {
    struct QNode* n = (struct QNode*)malloc(sizeof(struct QNode));
    n->data = val; n->next = NULL;
    if(!qrear) { qfront = qrear = n; return; }
    qrear->next = n; qrear = n;
}

int llDequeue() {
    if(!qfront) { printf("Empty!\n"); return -1; }
    int val = qfront->data;
    struct QNode* t = qfront;
    qfront = qfront->next;
    if(!qfront) qrear = NULL;
    free(t);
    return val;
}

int main() {
    enqueue(10); enqueue(20); enqueue(30);
    printf("Dequeue: %d\n", dequeue());  // 10
    llEnqueue(100); llEnqueue(200);
    printf("LL Dequeue: %d\n", llDequeue());  // 100
    return 0;
}

Python Implementation

Python
def tower_of_hanoi(n, source, auxiliary, destination):
    """Move n disks from source to destination using auxiliary.
    
    The key insight:
    1. Move n-1 disks from source to auxiliary (recursive)
    2. Move the largest disk from source to destination (base move)
    3. Move n-1 disks from auxiliary to destination (recursive)
    
    Total moves = 2^n - 1. For n=64 (legend): 18 quintillion moves!
    """
    if n == 1:
        # Base case: only one disk — move it directly
        print(f"Move disk 1 from {source} to {destination}")
        return
    
    # Step 1: Move top n-1 disks out of the way
    tower_of_hanoi(n - 1, source, destination, auxiliary)
    
    # Step 2: Move the largest disk
    print(f"Move disk {n} from {source} to {destination}")
    
    # Step 3: Move the n-1 disks from auxiliary to destination
    tower_of_hanoi(n - 1, auxiliary, source, destination)


print("=== Tower of Hanoi (3 disks) ===")
tower_of_hanoi(3, "A", "B", "C")
print(f"\nTotal moves for 3 disks: {2**3 - 1} = 7")

C Implementation

C
#include <stdio.h>

void hanoi(int n, char src, char aux, char dst) {
    if (n == 1) {
        printf("Move disk 1: %c -> %c\n", src, dst);
        return;
    }
    hanoi(n-1, src, dst, aux);
    printf("Move disk %d: %c -> %c\n", n, src, dst);
    hanoi(n-1, aux, src, dst);
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

Merge Sort — Python

Python
def merge_sort(arr):
    """Divide array in half, sort each half, merge sorted halves.
    Time: O(n log n) always. Space: O(n). Stable.
    Used by: Python's Timsort, Java's Arrays.sort() for objects."""
    
    if len(arr) <= 1:    # Base case: single element is sorted
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # Sort left half
    right = merge_sort(arr[mid:])    # Sort right half
    
    return merge(left, right)


def merge(left, right):
    """Merge two sorted arrays into one sorted array. O(n)."""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:    # <= for stability
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    
    result.extend(left[i:])      # Append remaining
    result.extend(right[j:])
    return result


data = [38, 27, 43, 3, 9, 82, 10]
print("Merge Sort:", merge_sort(data))

Quick Sort — Python

Python
def quick_sort(arr, low, high):
    """In-place Quick Sort using Lomuto partition.
    Average: O(n log n). Worst: O(n²) on already-sorted input.
    Used by: C's qsort(), Go's sort, Rust's sort_unstable."""
    
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)   # Sort left
        quick_sort(arr, pivot_index + 1, high)  # Sort right


def partition(arr, low, high):
    """Lomuto partition: last element as pivot."""
    pivot = arr[high]          # Choose last element as pivot
    i = low - 1                # Boundary of "≤ pivot" section
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]   # Swap to left side
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Place pivot correctly
    return i + 1


data = [10, 80, 30, 90, 40, 50, 70]
quick_sort(data, 0, len(data) - 1)
print("Quick Sort:", data)

C — Merge Sort & Quick Sort

C
#include <stdio.h>

/* ─── Merge Sort ─── */
void merge(int a[], int l, int m, int r) {
    int n1=m-l+1, n2=r-m, L[n1], R[n2];
    for(int i=0;i<n1;i++) L[i]=a[l+i];
    for(int j=0;j<n2;j++) R[j]=a[m+1+j];
    int i=0,j=0,k=l;
    while(i<n1 && j<n2) a[k++]=(L[i]<=R[j])?L[i++]:R[j++];
    while(i<n1) a[k++]=L[i++];
    while(j<n2) a[k++]=R[j++];
}
void mergeSort(int a[], int l, int r) {
    if(l<r) { int m=l+(r-l)/2; mergeSort(a,l,m); mergeSort(a,m+1,r); merge(a,l,m,r); }
}

/* ─── Quick Sort ─── */
int partition(int a[], int lo, int hi) {
    int pivot=a[hi], i=lo-1;
    for(int j=lo;j<hi;j++)
        if(a[j]<=pivot){i++; int t=a[i];a[i]=a[j];a[j]=t;}
    int t=a[i+1]; a[i+1]=a[hi]; a[hi]=t;
    return i+1;
}
void quickSort(int a[], int lo, int hi) {
    if(lo<hi){int p=partition(a,lo,hi);quickSort(a,lo,p-1);quickSort(a,p+1,hi);}
}

int main() {
    int a[]={38,27,43,3,9}, b[]={10,80,30,90,40};
    mergeSort(a,0,4);
    quickSort(b,0,4);
    printf("Merge: "); for(int i=0;i<5;i++) printf("%d ",a[i]);
    printf("\nQuick: "); for(int i=0;i<5;i++) printf("%d ",b[i]);
    return 0;
}