Unit III — Stacks & Queues

Syllabus Coverage: Stack and Queue as ADT. Operations on stack and queue. Implementations using arrays and dynamic memory allocation. Application of stack for expression conversion and expression evaluation, Recursion and stacks, Linear queue vs. Circular queue. (08 Hours)

Table of Contents

Glossary — Key Terms

1 — Stack

1.1 Stack as an ADT

Real-Life Analogies:

• Stack of plates in a cafeteria
• Pile of books on a desk
• Browser back button (most recent page first)
• Undo operation in text editors

ADT Stack:
    Data:
        An ordered collection of elements with LIFO access
        A variable 'top' pointing to the topmost element
    
    Operations:
        push(element)   → Insert element at top              — O(1)
        pop()           → Remove and return top element       — O(1)
        peek() / top()  → Return top element (no removal)    — O(1)
        isEmpty()       → Return true if stack is empty       — O(1)
        isFull()        → Return true if stack is full        — O(1)
        size()          → Return number of elements           — O(1)
    
    Error Conditions:
        pop() or peek() on empty stack → "Stack Underflow"
        push() on full stack (array)   → "Stack Overflow"

Visual:

        ┌─────┐
  top → │  30 │  ← last pushed, first popped
        ├─────┤
        │  20 │
        ├─────┤
        │  10 │  ← first pushed, last popped
        └─────┘

1.2 Stack Operations

Operation    Stack (bottom→top)    top    Return
─────────    ─────────────────     ───    ──────
push(10)     [10]                   0       —
push(20)     [10, 20]               1       —
push(30)     [10, 20, 30]           2       —
pop()        [10, 20]               1       30
peek()       [10, 20]               1       20
pop()        [10]                   0       20

1.3 Stack Implementation Using Array

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int top;
} Stack;

// Initialize stack
void init(Stack *s) {
    s->top = -1;
}

// Check if stack is empty
int isEmpty(Stack *s) {
    return s->top == -1;
}

// Check if stack is full
int isFull(Stack *s) {
    return s->top == MAX - 1;
}

// Push operation
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow!\n");
        return;
    }
    s->data[++(s->top)] = value;
}

// Pop operation
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow!\n");
        return -1;  // Error value
    }
    return s->data[(s->top)--];
}

// Peek operation
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[s->top];
}

🔍 Line-by-Line Logic — Array-Based Stack:

• s->top = -1 — Why -1? Because valid array indices start at 0. Using -1 as the initial top means “no elements exist.” When we push the first element, top becomes 0 — exactly the first valid index.
• isEmpty: top == -1 — Directly follows from our convention. No elements = top is at -1.
• isFull: top == MAX - 1 — If top has reached the last valid index, the array is full.
• push: s->data[++(s->top)] = value — The ++ is pre-increment: first increment top, then store at the new position. This ensures we write to the next empty slot, not overwrite the current top.
• pop: return s->data[(s->top)--] — The -- is post-decrement: first read the value at top, then decrement. This returns the current top element and logically removes it (the data stays in memory but top moves down, so it’s treated as empty).
• Overflow/Underflow checks — Every push/pop first checks for overflow/underflow. Forgetting these checks leads to array out-of-bounds bugs (writing past the array) or reading garbage values.

Pros: Simple, fast ($O(1)$ all operations), cache-friendly
Cons: Fixed size, can overflow

1.4 Stack Implementation Using Linked List

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

void init(Stack *s) {
    s->top = NULL;
}

int isEmpty(Stack *s) {
    return s->top == NULL;
}

void push(Stack *s, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;   // New node points to old top
    s->top = newNode;          // Top now points to new node
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    Node *temp = s->top;
    int value = temp->data;
    s->top = temp->next;
    free(temp);
    return value;
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->top->data;
}

🔍 Line-by-Line Logic — Linked List Stack:

• s->top = NULL — Empty stack = null pointer. No sentinel node needed.
• push: newNode->next = s->top; s->top = newNode; — Why insert at the head? Because the head of the linked list is the top of the stack. Inserting at the head is $O(1)$ — no traversal needed. The new node points to the old top, then becomes the new top. Think of it as stacking a new plate on top.
• pop: temp = s->top; s->top = temp->next; free(temp); — Save the top node, move top to the next node, then free the old top. We must save the pointer in temp first because after s->top = temp->next, we’d lose access to the old node and couldn’t free it — causing a memory leak.
• No isFull needed — The linked list grows dynamically. The only “full” condition is when malloc fails (system out of memory), which is extremely rare.
• Every node costs extra memory — Each node stores a next pointer (typically 4-8 bytes) in addition to the data. For small data types like int, this almost doubles the memory usage compared to arrays.

Pros: Dynamic size, no overflow (until memory exhausted)
Cons: Extra memory for pointers, slightly slower due to dynamic allocation

Array vs Linked List Stack

Practice Questions — Stack Basics

1.5 Two Stacks in One Array

Array:  [S1→  ...  free space  ...  ←S2]
         0   top1           top2   n-1

Overflow occurs only when the two tops meet: top1 + 1 == top2.

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int top1;  // Top of stack 1 (grows left → right)
    int top2;  // Top of stack 2 (grows right → left)
} TwoStacks;

void init(TwoStacks *ts) {
    ts->top1 = -1;
    ts->top2 = MAX;
}

int isFull(TwoStacks *ts) {
    return ts->top1 + 1 == ts->top2;
}

void push1(TwoStacks *ts, int value) {
    if (isFull(ts)) { printf("Stack Overflow!\n"); return; }
    ts->data[++(ts->top1)] = value;
}

void push2(TwoStacks *ts, int value) {
    if (isFull(ts)) { printf("Stack Overflow!\n"); return; }
    ts->data[--(ts->top2)] = value;
}

int pop1(TwoStacks *ts) {
    if (ts->top1 == -1) { printf("Stack 1 Underflow!\n"); return -1; }
    return ts->data[(ts->top1)--];
}

int pop2(TwoStacks *ts) {
    if (ts->top2 == MAX) { printf("Stack 2 Underflow!\n"); return -1; }
    return ts->data[(ts->top2)++];
}

🔍 Line-by-Line Logic:

• top1 = -1, top2 = MAX — Stack 1 is empty when top1 is before the array start. Stack 2 is empty when top2 is past the array end. They start at opposite extremes.
• isFull: top1 + 1 == top2 — The stacks share the array. Overflow happens only when they collide — no space between them. This is more memory-efficient than splitting the array in half (which wastes space if one stack is much fuller than the other).
• push1: ++(ts->top1) — Stack 1 grows right (increasing index). Pre-increment top1, then store value.
• push2: --(ts->top2) — Stack 2 grows left (decreasing index). Pre-decrement top2, then store value.
• pop1: (ts->top1)-- — Return value at top1, then decrement (shrink right → left).
• pop2: (ts->top2)++ — Return value at top2, then increment (shrink left → right).
• Why this approach? — Both stacks share the entire array’s free space. If stack 1 needs 90% of the space and stack 2 needs only 10%, that works fine. A naïve split (first half for S1, second half for S2) would waste space.

1.6 Stack Permutations & Catalan Number

Example ($n = 3$, input: 1, 2, 3):

Catalan Number — Counting Valid Stack Permutations:

The number of valid stack permutations of $n$ elements is the $n$-th Catalan number:

2 — Applications of Stack

2.1 Expression Types — Infix, Prefix, Postfix

Why Convert to Prefix/Postfix?

• Infix is natural for humans but ambiguous without parentheses and precedence rules
• Postfix/Prefix are unambiguous — no need for parentheses, no precedence rules
• Computers can evaluate postfix/prefix expressions very efficiently using a stack

Operator Precedence (highest to lowest)

Conversion Examples

2.2 Infix to Postfix Conversion

Algorithm (Shunting-Yard Algorithm)

INPUT: Infix expression (string)
OUTPUT: Postfix expression (string)

1. Create an empty stack (for operators) and an empty output string
2. Scan the infix expression left to right:
   a. If OPERAND (letter/number): Add directly to output
   b. If '(': Push onto stack
   c. If ')': Pop and add to output until '(' is found. Discard '('.
   d. If OPERATOR:
      - While stack is not empty AND top of stack is not '(' AND
        (precedence of top ≥ precedence of current operator):
          Pop from stack and add to output
      - Push current operator onto stack
3. After scanning, pop all remaining operators from stack to output

Detailed Worked Example

2.3 Infix to Prefix Conversion

Algorithm

1. Reverse the infix expression (and swap '(' ↔ ')')
2. Apply infix-to-postfix algorithm on the reversed expression
3. Reverse the result → this is the prefix expression

2.4 Postfix Expression Evaluation

Algorithm

1. Scan postfix expression left to right
2. If OPERAND: Push onto stack
3. If OPERATOR: 
   - Pop two operands (second popped is LEFT operand)
   - Apply operator: result = left_operand OPERATOR right_operand
   - Push result back onto stack
4. After scanning, the stack contains one element — the final result

C Implementation

int evaluatePostfix(char* exp) {
    Stack s;
    init(&s);
    
    for (int i = 0; exp[i] != '\0'; i++) {
        if (exp[i] >= '0' && exp[i] <= '9') {
            push(&s, exp[i] - '0');  // Convert char to int
        } else if (exp[i] != ' ') {
            int right = pop(&s);
            int left = pop(&s);
            switch (exp[i]) {
                case '+': push(&s, left + right); break;
                case '-': push(&s, left - right); break;
                case '*': push(&s, left * right); break;
                case '/': push(&s, left / right); break;
            }
        }
    }
    return pop(&s);  // Final result
}

🔍 Line-by-Line Logic:

• exp[i] - '0' — Converts ASCII character to integer. In ASCII, '0'=48, '1'=49, ..., '9'=57. So '5' - '0' = 53 - 48 = 5. This only works for single-digit numbers.
• exp[i] != ' ' — Skip spaces (used as delimiters between tokens).
• right = pop(&s) then left = pop(&s) — Order matters! The first pop gives the RIGHT operand (it was pushed last). The second pop gives the LEFT operand. For + and * this doesn’t matter (commutative), but for - and / the order is critical: left - right, not right - left.
• Why a stack? — In postfix notation, when we encounter an operator, its operands are always the two most recently seen values. The stack naturally gives us “most recent first” (LIFO), making it a perfect match.
• return pop(&s) — After processing the entire expression, exactly one value remains on the stack — the final result. If there’s more than one value left, the expression was malformed.

2.5 Prefix Expression Evaluation

Algorithm

1. Scan prefix expression from RIGHT to LEFT
2. If OPERAND: Push onto stack
3. If OPERATOR:
   - Pop two operands (first popped is LEFT operand — opposite of postfix!)
   - Apply operator: result = left_operand OPERATOR right_operand
   - Push result
4. Stack contains final result

2.6 Parenthesis Matching

A classic stack application — check if parentheses in an expression are balanced.

int isBalanced(char* exp) {
    Stack s;
    init(&s);
    
    for (int i = 0; exp[i] != '\0'; i++) {
        char ch = exp[i];
        
        if (ch == '(' || ch == '[' || ch == '{') {
            push(&s, ch);
        }
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(&s)) return 0;  // No matching open bracket
            
            char top = pop(&s);
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{'))
                return 0;  // Mismatched
        }
    }
    return isEmpty(&s);  // Stack should be empty if balanced
}

🔍 Line-by-Line Logic:

• Opening brackets → push — Every opening bracket is a “promise” that a matching closing bracket will come later. We store it on the stack.
• Closing bracket → pop and match — When we see a closing bracket, the most recent unmatched opening bracket (stack top) MUST be its matching type. If } appears but stack top is (, there’s a mismatch.
• isEmpty(&s) check before pop — If we see a closing bracket but the stack is empty, there’s no opening bracket to match it — immediately unbalanced.
• return isEmpty(&s) — After processing all characters, the stack must be empty. If there are leftover opening brackets on the stack, they were never closed — unbalanced. This catch handles cases like "(()".
• Why a stack? — Brackets must be matched in nested order: the most recently opened bracket must be closed first (LIFO). This exactly mirrors the stack’s behavior.

Practice Questions — Expression Conversion & Evaluation

3 — Recursion and Stacks

3.1 What is Recursion?

// Template for recursive functions:
returnType function(parameters) {
    if (base_condition)    // Base case
        return base_value;
    else                   // Recursive case
        return function(smaller_parameters);
}

// Direct Recursion — function A calls A
void directRecursion(int n) {
    if (n <= 0) return;
    printf("%d ", n);
    directRecursion(n - 1);   // A calls A
}

// Indirect Recursion — A calls B, B calls A
void funcB(int n);   // Forward declaration

void funcA(int n) {
    if (n <= 0) return;
    printf("%d ", n);
    funcB(n - 1);     // A calls B
}

void funcB(int n) {
    if (n <= 0) return;
    printf("%d ", n);
    funcA(n / 2);     // B calls A
}

🔍 Why This Matters:

• Direct recursion is the common case — factorial(n) calls factorial(n-1). The function name appears in its own body.
• Indirect recursion creates a cycle: A → B → A → B → … Each function in the chain must have a base case, otherwise the cycle never terminates.
• Forward declaration needed — In C, funcA calls funcB which isn’t defined yet. We need void funcB(int n); as a prototype before funcA’s definition.
• Both types use the call stack the same way — each call creates an activation record regardless of whether it’s direct or indirect.

3.2 How Recursion Uses the Stack

Every time a function is called, the system creates an activation record (also called a stack frame) on the call stack containing:

• Return address
• Local variables
• Parameters
• Saved registers

int factorial(int n) {
    if (n <= 1) return 1;       // Base case
    return n * factorial(n - 1); // Recursive case
}

Call: factorial(4)
  Call: factorial(3)
    Call: factorial(2)
      Call: factorial(1)
        Returns: 1                    ← base case hit
      Returns: 2 * 1 = 2             ← unwinds
    Returns: 3 * 2 = 6
  Returns: 4 * 6 = 24

Final Answer: 24

┌──────────────────┐
│ factorial(1)     │ ← top (current)
│ n=1, returns 1   │
├──────────────────┤
│ factorial(2)     │
│ n=2              │
├──────────────────┤
│ factorial(3)     │
│ n=3              │
├──────────────────┤
│ factorial(4)     │
│ n=4              │
├──────────────────┤
│ main()           │ ← bottom
└──────────────────┘

// BAD — no base case!
int bad(int n) {
    return n * bad(n);  // Infinite recursion → Stack Overflow
}

3.3 Classic Recursive Problems

Factorial

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
// Time: O(n)    Space: O(n) — recursion depth

🔍 Why This Logic: n! = n × (n-1)! is the mathematical definition itself. The base case n ≤ 1 returns 1 because 0! = 1! = 1. Each call reduces n by 1, so after exactly n calls we hit the base case. The space is $O(n)$ because n stack frames exist simultaneously at the deepest point.

Fibonacci

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// Time: O(2ⁿ) — exponential!    Space: O(n)

🔍 Why This Logic:

• if (n <= 1) return n — Base cases: fib(0) = 0 and fib(1) = 1. Returning n itself handles both.
• fibonacci(n-1) + fibonacci(n-2) — Directly mirrors the mathematical recurrence $F(n) = F(n-1) + F(n-2)$.
• Why is it $O(2^n)$? — Each call makes TWO recursive calls, creating a binary tree of calls. fib(5) calls fib(4) and fib(3), which each call two more, etc. Many sub-problems are computed repeatedly (e.g., fib(3) is computed multiple times). This is grossly inefficient — memoization or iteration reduces it to $O(n)$.
• Space is $O(n)$, not $O(2^n)$ — Because at any time, only one branch of the recursion tree is on the stack (depth = $n$). The tree is wide but the stack only tracks the current path.

Tower of Hanoi

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);   // Move n-1 disks to auxiliary
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);   // Move n-1 disks to target
}
// Number of moves: 2ⁿ - 1
// Time: O(2ⁿ)    Space: O(n)

🔍 Line-by-Line Logic:

• The key insight: To move n disks from A to C, you need to: (1) move n-1 disks from A to B (using C as auxiliary), (2) move the largest disk from A to C, (3) move n-1 disks from B to C (using A as auxiliary).
• if (n == 1) — Base case: a single disk can be moved directly. No recursion needed.
• hanoi(n-1, from, aux, to) — Move the top n-1 disks out of the way to the auxiliary peg. Notice how the roles of pegs change: aux becomes the destination, to becomes the auxiliary.
• printf("Move disk %d...") — Now the bottom disk (largest) is exposed and can be moved directly to the target.
• hanoi(n-1, aux, to, from) — Move the n-1 disks from auxiliary to target, completing the puzzle.
• Why $2^n - 1$ moves? — The recurrence is $T(n) = 2T(n-1) + 1$, which solves to $T(n) = 2^n - 1$. For 3 disks: 7 moves. For 64 disks: $1.8 \times 10^{19}$ moves (the legend says the world ends when this is done!).

Sum of Array

int sumArray(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumArray(arr, n - 1);
}
// Time: O(n)    Space: O(n)

🔍 Why This Logic: The sum of n elements = last element + sum of first n-1 elements. Base case: sum of 0 elements is 0. We use arr[n-1] (not arr[n]) because the last element of an n-element array is at index n-1. Each call reduces the problem size by 1.

Binary Search (Recursive)

int binarySearch(int arr[], int low, int high, int key) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == key) return mid;
    if (arr[mid] < key)
        return binarySearch(arr, mid + 1, high, key);
    else
        return binarySearch(arr, low, mid - 1, key);
}
// Time: O(log n)    Space: O(log n)

🔍 Line-by-Line Logic:

• if (low > high) return -1 — Base case: if search range is empty, the key doesn’t exist. This happens when we’ve narrowed the window to nothing.
• low + (high - low) / 2 — Computes midpoint without integer overflow. The naïve (low + high) / 2 can overflow if both are large. This is a classic defensive coding trick.
• arr[mid] == key — Found it! Return the index.
• arr[mid] < key → search right half — If the middle element is too small, the key (if it exists) must be in the right half [mid+1, high].
• else → search left half — Middle is too large, so search [low, mid-1].
• Space is $O(\log n)$ — Each recursive call adds a stack frame, and we halve the problem each time, so maximum recursion depth is $\log_2 n$. The iterative version in Unit 2 uses $O(1)$ space.

3.4 Nested Recursion & Tail Recursion

// Nested Recursion Example
int nested(int n) {
    if (n > 100)
        return n - 10;
    else
        return nested(nested(n + 11));  // Argument is a recursive call!
}

🔍 Line-by-Line Logic:

• This is the famous McCarthy 91 function. For any $n \leq 100$, it always returns 91.
• Why it’s tricky: To evaluate nested(95), we first need nested(106) = 96, then nested(96), which again needs nested(107) = 97, then nested(97), and so on — eventually reaching nested(101) = 91. So nested(95) = 91.
• Key difference from direct/indirect: In direct recursion, the argument is a simple expression like n-1. In nested recursion, the argument is another recursive call, making the evaluation order non-obvious.

nested(97)
  = nested(nested(108))       // 108 > 100, so nested(108) = 98
  = nested(98)
  = nested(nested(109))       // nested(109) = 99
  = nested(99)
  = nested(nested(110))       // nested(110) = 100
  = nested(100)
  = nested(nested(111))       // nested(111) = 101
  = nested(101)
  = 91                        // 101 > 100, return 101 - 10 = 91

// Tail Recursive — recursive call is the LAST thing
int factorialTail(int n, int acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);  // Nothing to do after this returns
}
// Usage: factorialTail(5, 1)

// Non-Tail Recursive — multiplication happens AFTER the recursive call
int factorialNonTail(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Must multiply n after call returns
}

🔍 Why Tail Recursion Matters:

• Compiler optimization (TCO — Tail Call Optimization): A tail-recursive function can be automatically converted to a loop by the compiler, using $O(1)$ stack space instead of $O(n)$.
• Non-tail: n * factorial(n-1) — the function must remember n on the stack because it needs to multiply after the recursive call returns. Each call adds a stack frame → $O(n)$ space.
• Tail: factorialTail(n-1, n*acc) — the result is fully computed in the argument. The current frame can be reused for the next call since nothing is needed later.
• Rule of thumb: If you can convert a recursive function to use an accumulator parameter, it’s tail-recursive.

3.5 Recursion vs Iteration

Practice Questions — Recursion

4 — Queue

4.1 Queue as an ADT

Real-Life Analogies:

• Queue at a ticket counter
• Print jobs waiting for a printer
• CPU task scheduling
• Customers at a bank

ADT Queue:
    Data:
        An ordered collection of elements with FIFO access
        Two pointers: 'front' and 'rear'
    
    Operations:
        enqueue(element)  → Add element at rear              — O(1)
        dequeue()         → Remove and return front element   — O(1)
        front() / peek()  → Return front element (no removal) — O(1)
        isEmpty()         → Return true if queue is empty     — O(1)
        isFull()          → Return true if queue is full      — O(1)
        size()            → Return number of elements         — O(1)
    
    Error Conditions:
        dequeue() on empty queue → "Queue Underflow"
        enqueue() on full queue  → "Queue Overflow"

Visual:

  dequeue ← [10 | 20 | 30 | 40 | 50] ← enqueue
             ↑                     ↑
           front                  rear

4.2 Queue Operations

4.3 Linear Queue Implementation Using Array

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int front, rear;
} Queue;

void init(Queue *q) {
    q->front = 0;
    q->rear = -1;
}

int isEmpty(Queue *q) {
    return q->front > q->rear;
}

int isFull(Queue *q) {
    return q->rear == MAX - 1;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow!\n");
        return;
    }
    q->data[++(q->rear)] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue Underflow!\n");
        return -1;
    }
    return q->data[(q->front)++];
}

int peek(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->data[q->front];
}

🔍 Line-by-Line Logic:

• front = 0, rear = -1 — front points to the first element, rear to the last. Starting rear at -1 means the queue is empty (since front > rear).
• isEmpty: front > rear — When front overtakes rear, all elements have been dequeued.
• isFull: rear == MAX - 1 — The rear has reached the last index. Note: this is the source of the false overflow problem — space before front is wasted even though it’s technically free.
• ++(q->rear) — Pre-increment rear first, then place the value. Since rear starts at -1, the first enqueue puts the value at index 0.
• (q->front)++ — Return the front element first (post-increment), then advance front. This means the dequeued slot is abandoned forever.
• Why this design fails in practice — After many enqueue/dequeue cycles, front moves forward, leaving wasted slots behind. Even if only 1 element is in the queue, isFull() may return true. This is why circular queues exist.

4.4 Problem with Linear Queue — Need for Circular Queue

After several enqueue/dequeue operations:
[ _ | _ | _ | 40 | 50 ]       front=3, rear=4
  ↑   ↑   ↑
  wasted space!

isFull() returns TRUE (rear == MAX-1) even though 3 slots are empty!

4.5 Circular Queue Implementation

Visual:

        ┌───┬───┬───┬───┬───┐
        │ 40│ 50│   │ 10│ 20│      Circular view:
        └───┴───┴───┴───┴───┘
          0   1   2   3   4          rear=1, front=3
              ↑       ↑
            rear    front

#include <stdio.h>
#define MAX 5

typedef struct {
    int data[MAX];
    int front, rear;
    int count;    // Track number of elements
} CircularQueue;

void init(CircularQueue *q) {
    q->front = 0;
    q->rear = -1;
    q->count = 0;
}

int isEmpty(CircularQueue *q) {
    return q->count == 0;
}

int isFull(CircularQueue *q) {
    return q->count == MAX;
}

void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow!\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX;   // Wrap around!
    q->data[q->rear] = value;
    q->count++;
}

int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue Underflow!\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX;  // Wrap around!
    q->count--;
    return value;
}

int peek(CircularQueue *q) {
    if (isEmpty(q)) return -1;
    return q->data[q->front];
}

🔍 Line-by-Line Logic:

• count field — Instead of computing fullness from front/rear (which is error-prone in circular queues), we track the count explicitly. isEmpty = count == 0, isFull = count == MAX. Clean and unambiguous.
• rear = (rear + 1) % MAX — The heart of the circular queue. When rear is at index MAX-1 (the last slot), (MAX-1 + 1) % MAX = 0 — it wraps back to the beginning! This reuses slots that were freed by dequeue.
• front = (front + 1) % MAX — Same wrap-around logic for the front pointer. After dequeuing from the last index, front wraps to 0.
• Why modulo %? — It creates a logical circle from a linear array. Index sequence: 0, 1, 2, ..., MAX-1, 0, 1, 2, ... endlessly. This is the same trick used in hash tables and ring buffers.
• No wasted space — Unlike the linear queue, every slot can be reused. The queue is truly full only when count == MAX.
• Why rear starts at -1? — So that the first (rear + 1) % MAX gives 0, placing the first element at index 0. Alternative designs start rear at 0 and use rear as the next insertion point.

Dry Run

4.6 Queue Implementation Using Linked List

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
} Queue;

void init(Queue *q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue *q) {
    return q->front == NULL;
}

void enqueue(Queue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue Underflow!\n");
        return -1;
    }
    Node *temp = q->front;
    int value = temp->data;
    q->front = q->front->next;
    
    if (q->front == NULL)   // Queue became empty
        q->rear = NULL;
    
    free(temp);
    return value;
}

🔍 Line-by-Line Logic:

• Two pointers: front and rear — Unlike a stack (which only needs one end), a queue operates on BOTH ends. front for dequeue, rear for enqueue. Both start as NULL (empty queue).
• isEmpty: front == NULL — If there’s no front node, the queue is empty. No isFull() needed — linked list grows dynamically until memory runs out.
• Enqueue — special case isEmpty — For the very first element, both front and rear must point to it. After that, new nodes are always appended after rear.
• q->rear->next = newNode; q->rear = newNode — Two-step append: (1) link the current last node to the new node, (2) update rear to the new node. Order matters — if you update rear first, you lose the link to the old last node.
• if (q->front == NULL) q->rear = NULL — Critical edge case in dequeue! If we just removed the last element, front becomes NULL. But rear still points to the freed node (dangling pointer). We must reset rear to NULL too, otherwise the next enqueue would try to access freed memory.
• free(temp) — Prevents memory leak. We saved the front node in temp before advancing front, so we can safely free it.
• Advantages over array queue — No fixed size, no false overflow, no wasted space. Trade-off: extra memory per node for the next pointer.

4.7 Linear Queue vs Circular Queue

Practice Questions — Queue

4.8 Deque (Double-Ended Queue)

  insertFront / deleteFront ←→ [10 | 20 | 30 | 40 | 50] ←→ insertRear / deleteRear
                                  ↑                   ↑
                                front               rear

Two Restricted Variants:

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int front, rear, count;
} Deque;

void init(Deque *dq) {
    dq->front = 0;
    dq->rear = -1;
    dq->count = 0;
}

int isEmpty(Deque *dq) { return dq->count == 0; }
int isFull(Deque *dq) { return dq->count == MAX; }

void insertRear(Deque *dq, int value) {
    if (isFull(dq)) { printf("Deque Overflow!\n"); return; }
    dq->rear = (dq->rear + 1) % MAX;
    dq->data[dq->rear] = value;
    dq->count++;
}

void insertFront(Deque *dq, int value) {
    if (isFull(dq)) { printf("Deque Overflow!\n"); return; }
    dq->front = (dq->front - 1 + MAX) % MAX;
    dq->data[dq->front] = value;
    dq->count++;
}

int deleteFront(Deque *dq) {
    if (isEmpty(dq)) { printf("Deque Underflow!\n"); return -1; }
    int value = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAX;
    dq->count--;
    return value;
}

int deleteRear(Deque *dq) {
    if (isEmpty(dq)) { printf("Deque Underflow!\n"); return -1; }
    int value = dq->data[dq->rear];
    dq->rear = (dq->rear - 1 + MAX) % MAX;
    dq->count--;
    return value;
}

🔍 Line-by-Line Logic:

• (front - 1 + MAX) % MAX — Moving front backward (inserting at front). Adding MAX before % prevents negative indices. E.g., if front = 0: $(0 - 1 + 100) \% 100 = 99$ — wraps to the end.
• (rear - 1 + MAX) % MAX — Same wrap-around logic for deleting from rear.
• Deque is a superset — It can act as a Stack (insert and delete from one end only) OR a Queue (insert at one end, delete from the other). This makes it the most versatile linear data structure.
• Input-restricted deque = essentially a queue that allows deletion from both ends.
• Output-restricted deque = essentially a queue that allows insertion at both ends.

4.9 Priority Queue — Overview

4.10 Implementing Stack Using Two Queues

Approach — Make push costly:

1. Push(x): Enqueue x to empty queue q2. Then transfer all elements from q1 to q2 one by one. Swap q1 and q2.
2. Pop(): Simply dequeue from q1.

Push(1):  q1: [1]       q2: []
Push(2):  Enqueue 2 to q2: [2], transfer q1→q2: [2, 1], swap → q1: [2, 1]  q2: []
Push(3):  Enqueue 3 to q2: [3], transfer q1→q2: [3, 2, 1], swap → q1: [3, 2, 1]  q2: []
Pop():    Dequeue from q1 → 3 ✔ (LIFO!)

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int front, rear, count;
} Queue;

void initQ(Queue *q) { q->front = 0; q->rear = -1; q->count = 0; }
int isEmptyQ(Queue *q) { return q->count == 0; }

void enqueue(Queue *q, int val) {
    q->rear = (q->rear + 1) % MAX;
    q->data[q->rear] = val;
    q->count++;
}

int dequeue(Queue *q) {
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    q->count--;
    return val;
}

// Stack using two queues
typedef struct {
    Queue q1, q2;
} StackUsing2Q;

void initStack(StackUsing2Q *s) {
    initQ(&s->q1);
    initQ(&s->q2);
}

void push(StackUsing2Q *s, int value) {
    // Step 1: Enqueue to q2
    enqueue(&s->q2, value);
    
    // Step 2: Transfer all from q1 to q2
    while (!isEmptyQ(&s->q1)) {
        enqueue(&s->q2, dequeue(&s->q1));
    }
    
    // Step 3: Swap q1 and q2
    Queue temp = s->q1;
    s->q1 = s->q2;
    s->q2 = temp;
}

int pop(StackUsing2Q *s) {
    if (isEmptyQ(&s->q1)) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return dequeue(&s->q1);
}

🔍 Line-by-Line Logic:

• Key idea: After each push, q1 always has elements in LIFO (stack) order, with the most recently pushed element at the front of the queue.
• Push is $O(n)$ — We transfer all existing elements to maintain the order. Every push moves $n$ elements.
• Pop is $O(1)$ — The front of q1 is always the “top” of the stack. Just dequeue.
• Swap trick — Instead of copying queues, we swap the struct values. After the swap, q1 has the correct stack order and q2 is empty (ready for the next push).
• Alternative approach — Make pop costly instead: push always enqueues to q1 in $O(1)$, but pop transfers $n-1$ elements to q2, dequeues the last one, then swaps. This gives $O(1)$ push and $O(n)$ pop.

4.11 Implementing Queue Using Two Stacks

Approach — Dequeue-Costly (Lazy Transfer):

• Enqueue: Always push onto s1 → $O(1)$
• Dequeue: If s2 is empty, pop all elements from s1 and push onto s2 (reverses order). Then pop from s2.

typedef struct {
    Stack s1;  // Input stack (enqueue goes here)
    Stack s2;  // Output stack (dequeue comes from here)
} QueueUsing2S;

void initQueue(QueueUsing2S *q) {
    initStack(&q->s1);
    initStack(&q->s2);
}

void enqueue(QueueUsing2S *q, int value) {
    push(&q->s1, value);  // Always push to s1
}

int dequeue(QueueUsing2S *q) {
    if (isEmpty(&q->s2)) {
        // Transfer all from s1 to s2 (reverses order → FIFO)
        while (!isEmpty(&q->s1)) {
            push(&q->s2, pop(&q->s1));
        }
    }
    if (isEmpty(&q->s2)) {
        printf("Queue Underflow!\n");
        return -1;
    }
    return pop(&q->s2);
}

🔍 Line-by-Line Logic:

• s1 is the inbox, s2 is the outbox. Elements enter through s1 (newest on top), and leave through s2 (oldest on top).
• Why transfer reverses order: If s1 has [3, 2, 1] (3 on top, 1 at bottom), popping all and pushing to s2 gives s2 = [1, 2, 3] (1 on top). Now pop(s2) gives 1 — the first element enqueued (FIFO!).
• Lazy transfer: We only move elements to s2 when s2 is empty. If s2 still has elements, those are in the correct FIFO order already — just pop from s2.
• Amortized $O(1)$: Each element is pushed and popped from s1 exactly once, and pushed and popped from s2 exactly once. Total: 4 operations per element across its lifetime → amortized $O(1)$ per enqueue/dequeue.

Comprehensive Unit III Practice Set

📝 View Complete Solutions for Unit III →

← Back to DSA Index