Unit III — Complete Solutions to All Practice Questions

Practice Questions — Stack Basics (Q1–Q5)
Practice Questions — Expression Conversion & Evaluation (Q1–Q5)
Practice Questions — Recursion (Q1–Q8)
Practice Questions — Queue (Q1–Q8)
Comprehensive Unit III Practice Set (Q1–Q16)

Practice Questions — Stack Basics

Q1. Define Stack as an ADT. List all operations with time complexities.

ADT Stack:
    Data:
        An ordered collection of elements following LIFO (Last In, First Out)
        A pointer 'top' indicating the topmost element

    Operations:
        create()       → Initialize an empty stack                — O(1)
        push(element)  → Add element on top of the stack          — O(1)
        pop()          → Remove and return the top element        — O(1)
        peek() / top() → Return the top element without removal   — O(1)
        isEmpty()      → Return true if stack has no elements     — O(1)
        isFull()       → Return true if stack is at capacity      — O(1)
        size()         → Return the number of elements            — O(1)

    Error Conditions:
        pop() on empty stack     → "Stack Underflow"
        push() on full stack     → "Stack Overflow"
        peek() on empty stack    → "Stack is Empty"

    Axioms:
        1. isEmpty(create()) = true
        2. pop(push(S, x)) = x
        3. LIFO: The last element pushed is the first popped

All operations are $O(1)$ because they only modify/access the top pointer.

Q2. Implement a Stack using an array in C.

#include <stdio.h>
#define MAX 100

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

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

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

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

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

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

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

void display(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is Empty!\n");
        return;
    }
    printf("Stack (top → bottom): ");
    for (int i = s->top; i >= 0; i--)
        printf("%d ", s->data[i]);
    printf("\n");
}

Q3. Implement a Stack using a linked list. What advantage does it have over array implementation?

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

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

typedef struct {
    Node* top;
    int size;
} Stack;

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

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

void push(Stack *s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    s->size++;
}

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);
    s->size--;
    return value;
}

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

Advantages over array implementation:

Feature	Array Stack	Linked List Stack
Size	Fixed (must declare MAX)	Dynamic (grows as needed)
Overflow	Can overflow if full	No overflow (limited only by memory)
Memory	May waste memory (unused slots)	Uses exactly as much as needed
Implementation	Simpler	Slightly more complex
Cache	Better cache locality	Worse (scattered memory)

Q4. Trace the operations on an initially empty stack.

Operations: push(5), push(3), pop(), push(7), push(2), pop(), peek()

Operation	Stack (top → bottom)	Return Value
`push(5)`	[5]	—
`push(3)`	[3, 5]	—
`pop()`	[5]	3
`push(7)`	[7, 5]	—
`push(2)`	[2, 7, 5]	—
`pop()`	[7, 5]	2
`peek()`	[7, 5]	7 (not removed)

Final stack: [7, 5] with top = 7.

Q5. What is Stack Overflow and Stack Underflow? When does each occur?

Stack Overflow: Occurs when trying to push() an element onto a full stack.

In array implementation: when top == MAX - 1
In linked list: when malloc() fails (system out of memory)
In recursion: when call stack depth exceeds system limit (infinite/deep recursion)

Stack Underflow: Occurs when trying to pop() or peek() from an empty stack.

When top == -1 (array) or top == NULL (linked list)
Indicates a logical error — trying to remove data that doesn’t exist

Condition	When	Cause
Overflow	push() on full stack	Too many elements / infinite recursion
Underflow	pop()/peek() on empty stack	More pops than pushes / logic error

Practice Questions — Expression Conversion & Evaluation

Q1. Convert the following infix expressions to postfix and prefix.

(a) A + B * C - D / E

Precedence: *, / before +, -

Postfix: A B C * + D E / -

Tracing (postfix conversion using stack):

Token	Stack	Output
A		A
+	+	A
B	+	A B
*	+ *	A B
C	+ *	A B C
-	-	A B C * + (pop *, pop +)
D	-	A B C * + D
/	- /	A B C * + D
E	- /	A B C * + D E
end		A B C * + D E / -

Postfix: A B C * + D E / -

Prefix: - + A * B C / D E

(b) (A + B) * (C - D) / E

Postfix: A B + C D - * E /

Prefix: / * + A B - C D E

(c) A * (B + C * D) + E

Inner: C * D first, then B + C*D, then A * (...), then ... + E

Postfix: A B C D * + * E +

Prefix: + * A + B * C D E

(d) ((A + B) - C * (D / E)) + F

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

Prefix: + - + A B * C / D E F

Q2. Evaluate the following postfix expressions.

(a) 5 3 + 8 2 - *

Token	Stack	Action
5	[5]	push
3	[5, 3]	push
+	[8]	pop 3,5 → 5+3=8
8	[8, 8]	push
2	[8, 8, 2]	push
-	[8, 6]	pop 2,8 → 8-2=6
*	[48]	pop 6,8 → 8*6=48

Result: 48

(b) 2 3 1 * + 9 -

Token	Stack	Action
2	[2]	push
3	[2, 3]	push
1	[2, 3, 1]	push
*	[2, 3]	pop 1,3 → 3*1=3
+	[5]	pop 3,2 → 2+3=5
9	[5, 9]	push
-	[-4]	pop 9,5 → 5-9=-4

Result: -4

(c) 4 5 + 7 2 - *

Token	Stack	Action
4	[4]	push
5	[4, 5]	push
+	[9]	pop 5,4 → 4+5=9
7	[9, 7]	push
2	[9, 7, 2]	push
-	[9, 5]	pop 2,7 → 7-2=5
*	[45]	pop 5,9 → 9*5=45

Result: 45

Q3. Evaluate the following prefix expressions.

(a) + * 2 3 4 (scan right to left, or use recursion)

Recursive evaluation:

+ needs two operands
- First: * 2 3 = 6
- Second: 4
+ 6 4 = 10

Result: 10

(b) - + 7 * 4 5 + 2 0

- needs two operands
- First: + 7 * 4 5 = + 7 20 = 27
- Second: + 2 0 = 2
- 27 2 = 25

Result: 25

Q4. Write C code to convert infix to postfix using a stack.

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop() { return stack[top--]; }
char peek() { return stack[top]; }
int isEmpty() { return top == -1; }

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
    return 0;
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

void infixToPostfix(char* infix, char* postfix) {
    int j = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];

        if (isalnum(c)) {
            postfix[j++] = c;
        } else if (c == '(') {
            push(c);
        } else if (c == ')') {
            while (!isEmpty() && peek() != '(')
                postfix[j++] = pop();
            pop(); // Remove '('
        } else if (isOperator(c)) {
            while (!isEmpty() && precedence(peek()) >= precedence(c))
                postfix[j++] = pop();
            push(c);
        }
    }

    while (!isEmpty())
        postfix[j++] = pop();

    postfix[j] = '\0';
}

int main() {
    char infix[] = "A+B*C-D/E";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("Postfix: %s\n", postfix);  // Output: ABC*+DE/-
    return 0;
}

Q5. Write a C function to check if parentheses in an expression are balanced.

#include <stdio.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop() { return stack[top--]; }
int isEmpty() { return top == -1; }

int isBalanced(char* expr) {
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];

        if (c == '(' || c == '{' || c == '[') {
            push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (isEmpty()) return 0;  // No matching open bracket

            char open = pop();
            if ((c == ')' && open != '(') ||
                (c == '}' && open != '{') ||
                (c == ']' && open != '['))
                return 0;  // Mismatched pair
        }
    }
    return isEmpty();  // Stack should be empty if balanced
}

int main() {
    printf("%d\n", isBalanced("{[A+B]*C}"));    // 1 (balanced)
    printf("%d\n", isBalanced("((A+B)"));        // 0 (unbalanced)
    printf("%d\n", isBalanced("{(A+B])"));        // 0 (mismatched)
    return 0;
}

Logic: Push every opening bracket. On closing bracket, pop and check if it matches. If stack is empty at the end, expression is balanced.

Practice Questions — Recursion

Q1. Explain how the system stack is used during recursion. Draw the stack for `factorial(5)`.

When a function calls itself, each call creates a new stack frame containing:

Local variables
Parameters
Return address

The system pushes a frame for each call and pops it when the call returns.

factorial(5) call stack:

Call Phase (pushing):          Return Phase (popping):

factorial(5) → calls f(4)     factorial(1) returns 1
factorial(4) → calls f(3)     factorial(2) returns 2*1 = 2
factorial(3) → calls f(2)     factorial(3) returns 3*2 = 6
factorial(2) → calls f(1)     factorial(4) returns 4*6 = 24
factorial(1) → base case!     factorial(5) returns 5*24 = 120

Stack at maximum depth (when factorial(1) is executing):

| factorial(1) | n=1, returns 1     ← TOP
| factorial(2) | n=2, waiting
| factorial(3) | n=3, waiting
| factorial(4) | n=4, waiting
| factorial(5) | n=5, waiting       ← BOTTOM

Maximum stack depth = 5 → Space: $O(n)$

Q2. Write a recursive function to find the GCD of two numbers.

int gcd(int a, int b) {
    if (b == 0)
        return a;         // Base case
    return gcd(b, a % b); // Recursive case (Euclidean algorithm)
}

Trace for gcd(48, 18):

Call	a	b	a % b
gcd(48, 18)	48	18	12
gcd(18, 12)	18	12	6
gcd(12, 6)	12	6	0
gcd(6, 0)	6	0	base case

Returns: 6

Time: $O(\log(\min(a, b)))$, Space: $O(\log(\min(a, b)))$ (stack frames)

Q3. Write a recursive function to reverse a string.

#include <stdio.h>
#include <string.h>

void reverseString(char str[], int left, int right) {
    if (left >= right)      // Base case
        return;

    // Swap characters at left and right
    char temp = str[left];
    str[left] = str[right];
    str[right] = temp;

    reverseString(str, left + 1, right - 1); // Recursive case
}

int main() {
    char str[] = "hello";
    reverseString(str, 0, strlen(str) - 1);
    printf("%s\n", str);  // Output: "olleh"
    return 0;
}

Trace for “hello”:

Call	left	right	Swap	String
1	0	4	h↔o	“oellh”
2	1	3	e↔l	“olleh”
3	2	2	base case	“olleh”

Q4. Write a recursive function to check if a string is a palindrome.

int isPalindrome(char str[], int left, int right) {
    if (left >= right)           // Base case: single char or crossed
        return 1;                // It's a palindrome

    if (str[left] != str[right]) // Mismatch found
        return 0;

    return isPalindrome(str, left + 1, right - 1); // Check inner substring
}

Trace for “madam”:

Call	left	right	str[left]	str[right]	Match?
1	0	4	m	m	✓
2	1	3	a	a	✓
3	2	2	base case	—	✓

Returns: 1 (true)

Trace for “hello”:

Call	left	right	str[left]	str[right]	Match?
1	0	4	h	o	✗

Returns: 0 (false)

Q5. Solve the Tower of Hanoi for $n = 3$ disks. How many moves are needed?

Pegs: A (source), B (auxiliary), C (destination)

Disks: 1 (smallest) on top, 2, 3 (largest) on bottom — all on peg A.

Move #	Action	Peg A	Peg B	Peg C
Start	—	[3,2,1]	[]	[]
1	Move disk 1: A → C	[3,2]	[]	[1]
2	Move disk 2: A → B	[3]	[2]	[1]
3	Move disk 1: C → B	[3]	[2,1]	[]
4	Move disk 3: A → C	[]	[2,1]	[3]
5	Move disk 1: B → A	[1]	[2]	[3]
6	Move disk 2: B → C	[1]	[]	[3,2]
7	Move disk 1: A → C	[]	[]	[3,2,1]

Total moves: $2^3 - 1 = 7$

General formula: For $n$ disks, the minimum number of moves is $2^n - 1$.

Recurrence: $T(n) = 2T(n-1) + 1$, $T(1) = 1$

Q6. Compare recursion and iteration. When is recursion preferred?

Feature	Recursion	Iteration
Definition	Function calls itself	Uses loops (for, while)
Termination	Base case	Loop condition becomes false
Memory	Uses stack frames — $O(n)$ extra	Usually $O(1)$ extra
Speed	Slower (function call overhead)	Faster (no call overhead)
Code	Often simpler and more elegant	Can be verbose
Risk	Stack overflow for deep recursion	No stack overflow

When recursion is preferred:

Tree/Graph traversal — natural recursive structure (DFS, in-order traversal)
Divide and Conquer — Merge Sort, Quick Sort, Binary Search
Backtracking — N-Queens, Sudoku solver, maze solving
Problems with recursive definition — Fibonacci, Factorial, Tower of Hanoi
When code clarity matters more than raw performance

When iteration is preferred:

Simple linear traversals (summing an array)
Performance-critical code (no function call overhead)
Deep recursion that could cause stack overflow

Q7. What happens if you forget the base case?

Without a base case, the function calls itself infinitely, which causes:

Each call consumes stack memory (for parameters, local variables, return address)
Stack grows without bound until system memory is exhausted
Stack Overflow error — program crashes

Example:

// BAD — no base case!
int factorial(int n) {
    return n * factorial(n - 1);  // Never stops!
}

Calling factorial(3):

factorial(3) → factorial(2) → factorial(1) → factorial(0) → factorial(-1) → factorial(-2) → … → STACK OVERFLOW

Fixed version:

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

Q8. Convert recursive Fibonacci to iterative. Compare time complexity.

Recursive (exponential):

int fibRec(int n) {
    if (n <= 1) return n;
    return fibRec(n-1) + fibRec(n-2);  // O(2^n) time, O(n) space
}

Iterative (linear):

int fibIter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;  // O(n) time, O(1) space
}

Aspect	Recursive	Iterative
Time	$O(2^n)$ — exponential	$O(n)$ — linear
Space	$O(n)$ — stack frames	$O(1)$ — just 3 variables
fib(40)	~1 billion operations	40 operations
Readability	More intuitive	Slightly less intuitive
Problem	Massive redundant computation	None

The recursive version recomputes fib(3) millions of times for large $n$. The iterative version computes each value exactly once.

Practice Questions — Queue

Q1. Define Queue as an ADT. List all operations.

ADT Queue:
    Data:
        An ordered collection of elements following FIFO (First In, First Out)
        Two pointers: 'front' (removal end) and 'rear' (insertion end)

    Operations:
        create()           → Initialize an empty queue           — O(1)
        enqueue(element)   → Add element at the 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 has no elements — O(1)
        isFull()           → Return true if queue is at capacity  — O(1)
        size()             → Return number of elements            — O(1)

    Error Conditions:
        dequeue() on empty queue   → "Queue Underflow"
        enqueue() on full queue    → "Queue Overflow"

Q2. Implement a Linear Queue using arrays. Identify its drawback.

#include <stdio.h>
#define MAX 5

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

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

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

int dequeue(Queue *q) {
    if (isEmpty(q)) { printf("Queue Underflow!\n"); return -1; }
    int value = q->data[q->front];
    if (q->front == q->rear)  // Last element
        q->front = q->rear = -1;
    else
        q->front++;
    return value;
}

Major Drawback: After several enqueue/dequeue operations, front moves forward leaving wasted slots behind. Even if spaces are available at the beginning, isFull() returns true when rear == MAX - 1. This is called logical overflow.

Example with MAX=5:

After enqueue(1,2,3,4,5): [1][2][3][4][5]  front=0, rear=4
After dequeue 3 times:     [_][_][_][4][5]  front=3, rear=4
enqueue(6) → OVERFLOW! (rear=4=MAX-1) even though 3 slots are free!

Solution: Use a Circular Queue.

Q3. Implement a Circular Queue using arrays.

#include <stdio.h>
#define MAX 5

typedef struct {
    int data[MAX];
    int front, rear, count;
} 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;
}

How it solves the problem: The modulo operation % MAX wraps the index back to 0 when it reaches MAX. So after rear reaches the end, the next enqueue goes to index 0 (if available). No wasted space.

Q4. Implement a Queue using a linked list. What are the advantages?

#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) q->rear = NULL;  // Queue became empty
    free(temp);
    return value;
}

Advantages:

No overflow — grows dynamically
No wasted memory — no need for MAX size
No circular logic needed — simpler than circular array queue

Q5. Trace Circular Queue of size 4.

Operations: enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue(), enqueue(4), enqueue(5), enqueue(6)

Operation	Queue State	front	rear	count
init	[_, _, _, _]	0	-1	0
enqueue(1)	[1, _, _, _]	0	0	1
enqueue(2)	[1, 2, _, _]	0	1	2
enqueue(3)	[1, 2, 3, _]	0	2	3
dequeue()→1	[_, 2, 3, _]	1	2	2
dequeue()→2	[_, _, 3, _]	2	2	1
enqueue(4)	[_, _, 3, 4]	2	3	2
enqueue(5)	[5, _, 3, 4]	2	0	3
enqueue(6)	[5, 6, 3, 4]	2	1	4

Notice how enqueue(5) wraps rear from index 3 to index 0 — this is the circular behavior.

After enqueue(6), the queue is FULL (count = MAX = 4). Any further enqueue would cause overflow.

Reading order (front→rear): 3, 4, 5, 6

Q6. Compare Linear Queue and Circular Queue in detail.

Feature	Linear Queue	Circular Queue
Structure	front and rear move forward only	front and rear wrap around
Memory waste	Yes — dequeued slots can’t be reused	No — wraps around to reuse slots
Full condition	`rear == MAX - 1` (may be false full)	`count == MAX` (truly full)
Empty condition	`front == -1`	`count == 0`
Implementation	Simpler	Requires modulo arithmetic
Efficiency	Poor for frequent enqueue/dequeue	Optimal — $O(1)$ all operations
Use case	Only for simple, short-lived queues	General-purpose queue

Q7. What is the difference between a Stack and a Queue? Give real-world examples.

Feature	Stack	Queue
Principle	LIFO (Last In, First Out)	FIFO (First In, First Out)
Insert	push() — at top	enqueue() — at rear
Remove	pop() — from top	dequeue() — from front
Access	Only top element	Only front element
Ends used	One end (top)	Two ends (front and rear)

Stack examples:

Undo operation in text editors
Browser back button
Function call stack in programs
Parenthesis matching

Queue examples:

Printer queue
CPU task scheduling
BFS traversal
Customer service line

Q8. Can you implement a Queue using two Stacks? Write the algorithm.

Method: Use two stacks — S1 (for enqueue) and S2 (for dequeue).

enqueue(x):
    push x onto S1

dequeue():
    if S2 is not empty:
        return pop(S2)
    if S1 is also empty:
        error "Queue Underflow"
    while S1 is not empty:
        push pop(S1) onto S2
    return pop(S2)

Example: Enqueue 1, 2, 3, then dequeue:

enqueue(1): S1=[1], S2=[]
enqueue(2): S1=[2,1], S2=[]
enqueue(3): S1=[3,2,1], S2=[]

dequeue():
  S2 is empty → transfer all from S1 to S2
  pop S1→push S2: S1=[2,1], S2=[3]
  pop S1→push S2: S1=[1], S2=[2,3]
  pop S1→push S2: S1=[], S2=[1,2,3]
  pop S2 → returns 1 ✓ (FIFO!)

Complexity:

Enqueue: $O(1)$ always
Dequeue: $O(n)$ worst case (transfer), but $O(1)$ amortized — each element is transferred at most once

Comprehensive Unit III Practice Set

1. Define Stack and Queue. Give two real-world examples of each.

Stack: A linear data structure following LIFO — the last element inserted is the first removed.

Examples: Stack of plates, Undo operation in editors

Queue: A linear data structure following FIFO — the first element inserted is the first removed.

Examples: Printer queue, Ticketing line at a counter

2. What is LIFO and FIFO? How do they differ?

LIFO (Last In, First Out): The most recently added element is removed first. Used by: Stack.

FIFO (First In, First Out): The earliest added element is removed first. Used by: Queue.

LIFO (Stack)	FIFO (Queue)
Insert and remove from same end (top)	Insert at rear, remove from front
Like a stack of plates	Like a line at a counter

3. Explain overflow and underflow conditions for both stack and queue.

Condition	Stack	Queue
Overflow	`push()` when `top == MAX-1`	`enqueue()` when queue is full
Underflow	`pop()`/`peek()` when `top == -1`	`dequeue()`/`front()` when queue is empty

Overflow = trying to add to a full container. Underflow = trying to remove from an empty container.

4. What are the three types of expression notation? Why are postfix and prefix preferred by computers?

Notation	Format	Example	Precedence Rules
Infix	`A op B`	`A + B * C`	Needs precedence & parentheses
Prefix (Polish)	`op A B`	`+ A * B C`	No precedence needed
Postfix (Reverse Polish)	`A B op`	`A B C * +`	No precedence needed

Why computers prefer postfix/prefix:

No parentheses needed — operator position determines order
No precedence rules — evaluate left to right (postfix) or right to left (prefix)
Easy evaluation using stack — single left-to-right scan for postfix
No backtracking — each token is processed exactly once

5. Explain the role of the system stack in recursion.

The system stack stores a stack frame (activation record) for each function call containing:

Parameters passed to the function
Local variables declared inside
Return address — where to resume after the call returns
Return value slot

During recursion:

Each recursive call pushes a new frame onto the stack
When a base case is reached, the function returns and the frame is popped
Execution resumes at the return address in the previous frame

This is why deep recursion can cause stack overflow — each frame consumes memory.

6. Convert to postfix and evaluate: `(5 + 3) * 2 - 8 / 4`

Postfix conversion:

Token	Stack	Output
(	(
5	(	5
+	( +	5
3	( +	5 3
)		5 3 +
*	*	5 3 +
2	*	5 3 + 2
-	-	5 3 + 2 *
8	-	5 3 + 2 * 8
/	- /	5 3 + 2 * 8
4	- /	5 3 + 2 * 8 4
end		5 3 + 2 * 8 4 / -

Postfix: 5 3 + 2 * 8 4 / -

Evaluation:

Token	Stack
5	[5]
3	[5, 3]
+	[8]
2	[8, 2]
*	[16]
8	[16, 8]
4	[16, 8, 4]
/	[16, 2]
-	[14]

Result: 14

7. Convert to prefix: `A * B + C / D - E`

Step 1: Parenthesize: ((A * B) + (C / D)) - E

Step 2: Convert inside-out:

A * B → * A B
C / D → / C D
(* A B) + (/ C D) → + * A B / C D
(+ * A B / C D) - E → - + * A B / C D E

Prefix: - + * A B / C D E

8. Evaluate postfix: `3 4 * 2 5 * + 1 -`

Token	Stack	Action
3	[3]	push
4	[3, 4]	push
*	[12]	3*4=12
2	[12, 2]	push
5	[12, 2, 5]	push
*	[12, 10]	2*5=10
+	[22]	12+10=22
1	[22, 1]	push
-	[21]	22-1=21

Result: 21

9. Trace recursion for `fibonacci(5)`. Draw the call tree and show stack frames.

Call Tree:

                    fib(5)
                   /      \
              fib(4)        fib(3)
             /    \         /    \
         fib(3)  fib(2)  fib(2)  fib(1)
         /   \    /  \    /  \      |
     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) 1
      / \     |      |      |      |      |
  fib(1) fib(0) 1    1      0      1      0
    |      |
    1      0

Values (bottom-up):

fib(0) = 0, fib(1) = 1
fib(2) = fib(1) + fib(0) = 1
fib(3) = fib(2) + fib(1) = 2
fib(4) = fib(3) + fib(2) = 3
fib(5) = fib(4) + fib(3) = 5

Total function calls: 15 (massive redundancy!)

Note: fib(3) is computed 2 times, fib(2) is computed 3 times, fib(1) is computed 5 times.

10. Trace Circular Queue (size 5).

Operations: enqueue(A), enqueue(B), enqueue(C), dequeue(), dequeue(), enqueue(D), enqueue(E), enqueue(F), enqueue(G), dequeue()

#	Operation	front	rear	count	Queue Content
0	init	0	-1	0	[_, _, _, _, _]
1	enqueue(A)	0	0	1	[A, _, _, _, _]
2	enqueue(B)	0	1	2	[A, B, _, _, _]
3	enqueue(C)	0	2	3	[A, B, C, _, _]
4	dequeue()→A	1	2	2	[_, B, C, _, _]
5	dequeue()→B	2	2	1	[_, _, C, _, _]
6	enqueue(D)	2	3	2	[_, _, C, D, _]
7	enqueue(E)	2	4	3	[_, _, C, D, E]
8	enqueue(F)	2	0	4	[F, _, C, D, E]
9	enqueue(G)	2	1	5	[F, G, C, D, E]
10	dequeue()→C	3	1	4	[F, G, _, D, E]

Note step 8: rear wraps from 4 to 0 using (4+1) % 5 = 0.

Note step 9: Queue is FULL (count=5).

11. Write a C program that converts infix to postfix and evaluates it.

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

#define MAX 100

// ---- Character Stack (for conversion) ----
char cstack[MAX]; int ctop = -1;
void cpush(char c) { cstack[++ctop] = c; }
char cpop() { return cstack[ctop--]; }
char cpeek() { return cstack[ctop]; }
int cisEmpty() { return ctop == -1; }

// ---- Integer Stack (for evaluation) ----
int istack[MAX]; int itop = -1;
void ipush(int v) { istack[++itop] = v; }
int ipop() { return istack[itop--]; }

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void infixToPostfix(char* infix, char* postfix) {
    int j = 0;
    for (int i = 0; infix[i]; i++) {
        char c = infix[i];
        if (c == ' ') continue;
        if (isdigit(c)) {
            postfix[j++] = c;
        } else if (c == '(') {
            cpush(c);
        } else if (c == ')') {
            while (!cisEmpty() && cpeek() != '(')
                postfix[j++] = cpop();
            cpop();
        } else {
            while (!cisEmpty() && precedence(cpeek()) >= precedence(c))
                postfix[j++] = cpop();
            cpush(c);
        }
    }
    while (!cisEmpty()) postfix[j++] = cpop();
    postfix[j] = '\0';
}

int evaluatePostfix(char* postfix) {
    for (int i = 0; postfix[i]; i++) {
        char c = postfix[i];
        if (isdigit(c)) {
            ipush(c - '0');
        } else {
            int b = ipop(), a = ipop();
            switch (c) {
                case '+': ipush(a + b); break;
                case '-': ipush(a - b); break;
                case '*': ipush(a * b); break;
                case '/': ipush(a / b); break;
            }
        }
    }
    return ipop();
}

int main() {
    char infix[] = "(5+3)*2-8/4";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("Postfix: %s\n", postfix);
    printf("Result: %d\n", evaluatePostfix(postfix));
    return 0;
}
// Output: Postfix: 53+2*84/-   Result: 14

12. Implement a Stack that supports `getMin()` in $O(1)$ time (Min Stack).

Idea: Use an auxiliary stack that tracks the current minimum at each level.

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int minStack[MAX];  // Auxiliary stack tracking minimums
    int top;
} MinStack;

void init(MinStack *s) { s->top = -1; }
int isEmpty(MinStack *s) { return s->top == -1; }

void push(MinStack *s, int value) {
    s->top++;
    s->data[s->top] = value;
    if (s->top == 0)
        s->minStack[s->top] = value;
    else
        s->minStack[s->top] = (value < s->minStack[s->top - 1])
                               ? value : s->minStack[s->top - 1];
}

int pop(MinStack *s) {
    if (isEmpty(s)) { printf("Underflow!\n"); return -1; }
    return s->data[(s->top)--];
}

int getMin(MinStack *s) {
    if (isEmpty(s)) { printf("Stack Empty!\n"); return -1; }
    return s->minStack[s->top];  // O(1)!
}

Trace:

Operation	data stack	min stack	getMin()
push(5)	[5]	[5]	5
push(3)	[5,3]	[5,3]	3
push(7)	[5,3,7]	[5,3,3]	3
push(1)	[5,3,7,1]	[5,3,3,1]	1
pop()→1	[5,3,7]	[5,3,3]	3

All operations: $O(1)$ time, $O(n)$ extra space.

13. Implement a Queue using two Stacks. Analyze the time complexity.

#include <stdio.h>
#define MAX 100

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

void init(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
void push(Stack *s, int v) { s->data[++(s->top)] = v; }
int pop(Stack *s) { return s->data[(s->top)--]; }

typedef struct {
    Stack s1;  // For enqueue
    Stack s2;  // For dequeue
} QueueUsing2Stacks;

void qInit(QueueUsing2Stacks *q) {
    init(&q->s1);
    init(&q->s2);
}

void enqueue(QueueUsing2Stacks *q, int value) {
    push(&q->s1, value);
}

int dequeue(QueueUsing2Stacks *q) {
    if (isEmpty(&q->s2)) {
        if (isEmpty(&q->s1)) {
            printf("Queue Underflow!\n");
            return -1;
        }
        while (!isEmpty(&q->s1))
            push(&q->s2, pop(&q->s1));
    }
    return pop(&q->s2);
}

Time Complexity:

Operation	Worst Case	Amortized
enqueue	$O(1)$	$O(1)$
dequeue	$O(n)$ (transfer)	$O(1)$

Amortized $O(1)$ explanation: Each element is pushed and popped from S1 exactly once, and pushed and popped from S2 exactly once. So each element undergoes exactly 4 operations total, giving $O(1)$ per element amortized.

14. Compare array-based and linked-list-based implementations of Stack and Queue.

Feature	Array-Based	Linked-List-Based
Size	Fixed (needs MAX)	Dynamic (no limit except memory)
Overflow	Possible (when array is full)	Unlikely (only if system memory exhausted)
Memory usage	May waste memory (unused slots)	Extra memory for pointers per node
Access time	All ops $O(1)$ with indexing	All ops $O(1)$ with pointer
Cache	Better (contiguous memory)	Worse (nodes scattered in heap)
Implementation	Simpler	More complex (pointer management)
Resize	Not possible (or expensive realloc)	Automatic

When to use Array-based: Known max size, need cache-friendly access, simpler code.

When to use Linked-List-based: Unknown/varying size, frequent resize, no size limit needed.

15. Explain recursion with examples: Factorial, Fibonacci, Tower of Hanoi.

1. Factorial:

Recurrence: $F(n) = n \times F(n-1)$, $F(0) = 1$
Call tree: linear chain (no branching)
Time: $O(n)$, Space: $O(n)$

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

2. Fibonacci:

Recurrence: $F(n) = F(n-1) + F(n-2)$, $F(0) = 0, F(1) = 1$
Call tree: binary tree (each call branches into two)
Time: $O(2^n)$, Space: $O(n)$

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

3. Tower of Hanoi:

Recurrence: $T(n) = 2T(n-1) + 1$, $T(1) = 1$
Moves: $2^n - 1$
Time: $O(2^n)$, Space: $O(n)$

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

Problem	Recurrence	Time	Space	Tree Shape
Factorial	$T(n) = T(n-1) + 1$	$O(n)$	$O(n)$	Linear
Fibonacci	$T(n) = T(n-1) + T(n-2)$	$O(2^n)$	$O(n)$	Binary
Tower of Hanoi	$T(n) = 2T(n-1) + 1$	$O(2^n)$	$O(n)$	Binary

16. Explain the Circular Queue completely.

Why it’s needed: Linear queues waste memory — dequeued slots are never reused. Circular queues solve this by wrapping indices.

How it works: The array is treated as a circle using modulo arithmetic: index = (index + 1) % MAX.

Key formulas:

rear advances: rear = (rear + 1) % MAX
front advances: front = (front + 1) % MAX
Full: count == MAX
Empty: count == 0

Complete C implementation:

#include <stdio.h>
#define MAX 5

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

void init(CQueue *q) { q->front = 0; q->rear = -1; q->count = 0; }
int isEmpty(CQueue *q) { return q->count == 0; }
int isFull(CQueue *q) { return q->count == MAX; }

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

int dequeue(CQueue *q) {
    if (isEmpty(q)) { printf("Underflow!\n"); return -1; }
    int val = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    q->count--;
    return val;
}

void display(CQueue *q) {
    if (isEmpty(q)) { printf("Empty!\n"); return; }
    int i = q->front;
    for (int c = 0; c < q->count; c++) {
        printf("%d ", q->data[i]);
        i = (i + 1) % MAX;
    }
    printf("\n");
}

Trace example (MAX=5):

Operation	Array	front	rear	count
enqueue(10)	[10,,,,]	0	0	1
enqueue(20)	[10,20,,,_]	0	1	2
enqueue(30)	[10,20,30,,]	0	2	3
dequeue()→10	[,20,30,,_]	1	2	2
enqueue(40)	[,20,30,40,]	1	3	3
enqueue(50)	[_,20,30,40,50]	1	4	4
enqueue(60)	[60,20,30,40,50]	1	0	5 ← wraps!

📝 Back to Unit III Notes →

← Back to DSA Index

🔒 Private Site