With C Code, Diagrams, Examples, and Problem Solving

Complete Notes on Stacks and Queues

With C Code, Diagrams, Examples, and Problem Solving

1. STACK – Abstract Data Type (ADT)

Stack is a linear data structure that follows LIFO (Last In, First Out) principle.

Analogy

A stack of plates: You push a plate on top, pop from the top.

    [Plate 3] ← Top
    [Plate 2]
    [Plate 1]

Primitive Operations

Operation	Description	Time
`push(x)`	Insert `x` at top	O(1)
`pop()`	Remove and return top	O(1)
`peek()` / `top()`	View top element	O(1)
`isEmpty()`	Check if empty	O(1)
`isFull()`	Check if full (array)	O(1)

2. Array Implementation of Stack

#include <stdio.h>
#define MAX 100

typedef struct {
    int arr[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 x) {
    if (isFull(s)) {
        printf("Stack Overflow!\n");
        return;
    }
    s->arr[++s->top] = x;
}

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

int peek(Stack* s) {
    if (isEmpty(s)) return -1;
    return s->arr[s->top];
}

3. Linked List Implementation of Stack

#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;
}

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

int pop(Stack* s) {
    if (s->top == NULL) return -1;
    Node* temp = s->top;
    int x = temp->data;
    s->top = s->top->next;
    free(temp);
    return x;
}

4. Applications of Stack

A. Expression Evaluation

Type	Example
Infix	`A + B * C`
Prefix (Polish)	`+ A * B C`
Postfix (RPN)	`A B C * +`

Postfix Evaluation (Using Stack)

Algorithm:

Scan expression left to right
If operand → push
If operator → pop two operands, apply, push result
Final result = top of stack

**Example: `2 3 1 * + 9 -`**

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

Result: -4

C Code: Postfix Evaluation

#include <stdio.h>
#include <ctype.h>
#include "stack.h"  // Use array or linked stack

int evaluatePostfix(char* exp) {
    Stack s;
    init(&s);

    for (int i = 0; exp[i]; i++) {
        if (isdigit(exp[i]))
            push(&s, exp[i] - '0');
        else {
            int val1 = pop(&s);
            int val2 = pop(&s);
            switch (exp[i]) {
                case '+': push(&s, val2 + val1); break;
                case '-': push(&s, val2 - val1); break;
                case '*': push(&s, val2 * val1); break;
                case '/': push(&s, val2 / val1); break;
            }
        }
    }
    return pop(&s);
}

5. Recursion vs Iteration

Feature	Recursion	Iteration
Mechanism	Function calls itself	Loops
Memory	Stack (call stack)	Constant
Speed	Slower (function call overhead)	Faster
Readability	Elegant for tree problems	Clear control flow
Risk	Stack overflow	Infinite loop

Example 1: Fibonacci

Recursive

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

Time: O(2ⁿ) → Exponential!

Iterative

int fib(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;
}

Time: O(n)

Example 2: Binary Search

Recursive

int binarySearch(int arr[], int l, int r, int x) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x)
        return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
}

Iterative

int binarySearch(int arr[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

Example 3: Tower of Hanoi

Recursive

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);
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n-1, aux, to, from);
}

Time: O(2ⁿ − 1)

Tail Recursion → Iteration

Tail Recursive Fibonacci:

int fib_tail(int n, int a, int b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fib_tail(n-1, b, a + b);
}
// Call: fib_tail(n, 0, 1)

Converted to Iteration:

int fib(int n) {
    return fib_tail(n, 0, 1);
}

6. QUEUE – Abstract Data Type

FIFO (First In, First Out)

Operations

Operation	Description
`enqueue(x)`	Add at rear
`dequeue()`	Remove from front
`front()`	View front
`rear()`	View rear
`isEmpty()`	Check empty

7. Array Implementation (Simple Queue)

#define MAX 100
typedef struct {
    int arr[MAX];
    int front, rear;
} Queue;

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

void enqueue(Queue* q, int x) {
    if (q->rear == MAX - 1) {
        printf("Queue Full!\n");
        return;
    }
    if (q->front == -1) q->front = 0;
    q->arr[++q->rear] = x;
}

int dequeue(Queue* q) {
    if (q->front == -1) return -1;
    int x = q->arr[q->front];
    if (q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front++;
    return x;
}

Problem: Space wastage → Use Circular Queue

8. Circular Queue

void enqueue(Queue* q, int x) {
    if ((q->rear + 1) % MAX == q->front) {
        printf("Full!\n"); return;
    }
    if (q->front == -1) q->front = 0;
    q->rear = (q->rear + 1) % MAX;
    q->arr[q->rear] = x;
}

int dequeue(Queue* q) {
    if (q->front == -1) return -1;
    int x = q->arr[q->front];
    if (q->front == q->rear)
        q->front = q->rear = -1;
    else
        q->front = (q->front + 1) % MAX;
    return x;
}

Circular Queue Diagram

Index:  0   1   2   3   4
      [D]  [] [A] [B] [C]
           ↑        ↑
        front     rear

9. Linked List Queue

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

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

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

10. Deque (Double-Ended Queue)

Insert/delete from both ends
Can simulate stack and queue

pushFront(), pushBack(), popFront(), popBack()

11. Priority Queue

Elements removed by priority, not insertion order.

Implementation

Binary Heap → O(log n) insert/extract
Array → O(n) extract
Linked List → O(n) insert

Min-Heap Priority Queue (Array)

void insert(PQ* pq, int x) {
    pq->heap[++pq->size] = x;
    int i = pq->size;
    while (i > 1 && pq->heap[i] < pq->heap[i/2]) {
        swap(&pq->heap[i], &pq->heap[i/2]);
        i /= 2;
    }
}

12. Tradeoffs: Iteration vs Recursion

Factor	Recursion	Iteration
Memory	O(n) stack	O(1)
Speed	Slower	Faster
Code	Clean	Verbose
Best For	Trees, Divide & Conquer	Loops, large n

Prefer iteration when:

Performance critical

Large input

Stack overflow risk

13. Summary Table

Feature	Stack	Queue
Order	LIFO	FIFO
Insert	Top	Rear
Delete	Top	Front
Use	Recursion, Expressions	BFS, Scheduling
Circular	No	Yes
Priority	Can be	Common

14. Problem Solving Examples

1. Reverse String using Stack

void reverse(char* str) {
    Stack s; init(&s);
    for(int i = 0; str[i]; i++) push(&s, str[i]);
    for(int i = 0; str[i]; i++) str[i] = pop(&s);
}

2. Next Greater Element

void nextGreater(int arr[], int n) {
    Stack s; init(&s);
    for(int i = n-1; i >= 0; i--) {
        while(!isEmpty(&s) && peek(&s) <= arr[i]) pop(&s);
        int nge = isEmpty(&s) ? -1 : peek(&s);
        printf("%d ", nge);
        push(&s, arr[i]);
    }
}

15. Practice Problems

Infix to Postfix Conversion
Check balanced parentheses
Implement stack using two queues
Implement queue using two stacks
Stock Span Problem
LRU Cache using stack + hash

Key Takeaways

Concept	Insight
Stack	Use for depth, undo, expressions
Queue	Use for breadth, order, scheduling
Recursion	Elegant, but risky
Iteration	Safe, fast, preferred in production
Circular Queue	Solves space wastage
Priority Queue	Essential for Dijkstra, Huffman

End of Notes

With C Code, Diagrams, Examples, and Problem Solving

Complete Notes on Stacks and Queues

1. STACK – Abstract Data Type (ADT)

Analogy

Primitive Operations

2. Array Implementation of Stack

3. Linked List Implementation of Stack

4. Applications of Stack

A. Expression Evaluation

Postfix Evaluation (Using Stack)

Example: 2 3 1 * + 9 -

C Code: Postfix Evaluation

5. Recursion vs Iteration

Example 1: Fibonacci

Recursive

Iterative

Example 2: Binary Search

Recursive

Iterative

Example 3: Tower of Hanoi

Recursive

Tail Recursion → Iteration

6. QUEUE – Abstract Data Type

Operations

7. Array Implementation (Simple Queue)

8. Circular Queue

Circular Queue Diagram

9. Linked List Queue

10. Deque (Double-Ended Queue)

11. Priority Queue

Implementation

Min-Heap Priority Queue (Array)

12. Tradeoffs: Iteration vs Recursion

13. Summary Table

14. Problem Solving Examples

1. Reverse String using Stack

2. Next Greater Element

15. Practice Problems

Key Takeaways

**Example: `2 3 1 * + 9 -`**