Unit 2: Stacks

Stacks

A stack is a linear data structure that follows the principle:

LIFO – Last In First Out

Stack ADT Definition

Stack ADT defines:

Data objects: A set of elements
Operations: push, pop, peek, isEmpty, isFull

Stack ADT Operations

Operation	Description
push(x)	Insert element x
pop()	Remove top element
peek()	View top element
isEmpty()	Check if stack is empty
isFull()	Check if stack is full

Primitive Stack Operations

(a) PUSH Operation

Push inserts an element at the top of the stack.

Algorithm (Array Stack):

Check overflow (TOP == MAX − 1)
TOP = TOP + 1
STACK[TOP] = item

(b) POP Operation

Pop removes the element from the top of the stack.

Algorithm (Array Stack):

Check underflow (TOP == −1)
item = STACK[TOP]
TOP = TOP − 1

Stack Overflow and Underflow

Condition	Meaning
Overflow	Stack is full
Underflow	Stack is empty

Array Implementation of Stack in C

Stack Representation

Array: stack[MAX]
Variable: top

C Program: Array Stack


#include <stdio.h>
#define MAX 5

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

void push(int x) {
    if (top == MAX - 1)
        printf("Stack Overflow\n");
    else {
        top++;
        stack[top] = x;
        printf("%d pushed into stack\n", x);
    }
}

void pop() {
    if (top == -1)
        printf("Stack Underflow\n");
    else {
        printf("%d popped from stack\n", stack[top]);
        top--;
    }
}

void display() {
    if (top == -1)
        printf("Stack is empty\n");
    else {
        printf("Stack elements:\n");
        for (int i = top; i >= 0; i--)
            printf("%d\n", stack[i]);
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    display();
    pop();
    display();
    return 0;
}

Advantages of Array Stack

Simple implementation
Faster access

Disadvantages

Fixed size
Stack overflow problem

Linked List Implementation of Stack in C

Stack top is represented by head pointer
Insertion and deletion occur at beginning

Structure Definition


struct node {
    int data;
    struct node *next;
};

C Program: Linked Stack


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

struct node {
    int data;
    struct node *next;
};

struct node *top = NULL;

void push(int x) {
    struct node *newNode;
    newNode = (struct node*)malloc(sizeof(struct node));

    if (newNode == NULL)
        printf("Heap Overflow\n");
    else {
        newNode->data = x;
        newNode->next = top;
        top = newNode;
        printf("%d pushed into stack\n", x);
    }
}

void pop() {
    struct node *temp;
    if (top == NULL)
        printf("Stack Underflow\n");
    else {
        temp = top;
        printf("%d popped from stack\n", temp->data);
        top = temp->next;
        free(temp);
    }
}

void display() {
    struct node *temp;
    if (top == NULL)
        printf("Stack is empty\n");
    else {
        temp = top;
        printf("Stack elements:\n");
        while (temp != NULL) {
            printf("%d\n", temp->data);
            temp = temp->next;
        }
    }
}

int main() {
    push(5);
    push(15);
    push(25);
    display();
    pop();
    display();
    return 0;
}

Advantages of Linked Stack

Dynamic size
No overflow (until memory is full)

Disadvantages

Extra memory for pointer
Slower than array

Array Stack vs Linked Stack

Feature	Array Stack	Linked Stack
Size	Fixed	Dynamic
Memory	Contiguous	Non-contiguous
Overflow	Possible	Rare
Implementation	Simple	Complex

Applications of Stack

Function calls (Call Stack)
Expression evaluation
Parenthesis checking
Undo/Redo operations
Backtracking

Applications of Stack

(a) Infix Expression

Operator is written between operands
Example:
A + B

(b) Prefix Expression (Polish Notation)

Operator is written before operands
Example:
+ A B

(c) Postfix Expression (Reverse Polish Notation)

Operator is written after operands
Example: A B +

Advantages of Prefix and Postfix Expressions

No need for parentheses
Simple evaluation using stack
Faster computation by compiler

Evaluation of Postfix Expression Using Stack

Algorithm:

Initialize an empty stack
Scan postfix expression from left to right
If operand → push into stack

4. If operator →

Pop two operands
Perform operation
Push result back

5. Final element in stack is result

Example:

Postfix Expression:


23*54*+9-

Step-by-Step Evaluation:

Symbol	Action	Stack
2	Push	2
3	Push	2,3
*	2×3=6	6
5	Push	6,5
4	Push	6,5,4
*	5×4=20	6,20
+	6+20=26	26
9	Push	26,9
−	26−9=17	17

Result = 17

Iteration and Recursion

Iteration

Repetition using loops (for, while)
Uses explicit loop control
Faster and memory efficient

Recursion

Function calls itself
Uses system stack
Elegant but uses more memory

Principles of Recursion

A recursive function must have:

Base Condition – stops recursion
Recursive Call – function calls itself
Progress – moves toward base condition

Example (Factorial):


int fact(int n) {
    if(n == 0)
        return 1;
    return n * fact(n-1);
}

Tail Recursion

A recursion is called tail recursion if the recursive call is the last statement in the function.

Example:


int fact(int n, int res) {
    if(n == 0)
        return res;
    return fact(n-1, n*res);
}

Advantage:

Can be optimized into iteration
Saves stack space

Removal of Recursion

Recursion can be removed using:

Iteration
Stack simulation

Why Remove Recursion?

Avoid stack overflow
Improve performance

Problem Solving Using Iteration and Recursion

Binary Search

Condition:

List must be sorted

Binary Search Using Iteration


int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if(a[mid] == key)
            return mid;
        else if(a[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

Binary Search Using Recursion


int binarySearch(int a[], int low, int high, int key) {
    if(low <= high) {
        int mid = (low + high) / 2;
        if(a[mid] == key)
            return mid;
        else if(a[mid] < key)
            return binarySearch(a, mid+1, high, key);
        else
            return binarySearch(a, low, mid-1, key);
    }
    return -1;
}

Fibonacci Numbers

Fibonacci Series:


0, 1, 1, 2, 3, 5, 8, ...

Fibonacci Using Iteration


void fib(int n) {
    int a = 0, b = 1, c;
    printf("%d %d ", a, b);
    for(int i = 2; i < n; i++) {
        c = a + b;
        printf("%d ", c);
        a = b;
        b = c;
    }
}

Fibonacci Using Recursion


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

Tower of Hanoi

Problem Description:

Three rods: Source (A), Auxiliary (B), Destination (C)
Move all disks from A to C
Only one disk at a time
Larger disk cannot be placed on smaller disk

Recursive Algorithm:

Move n−1 disks from A to B using C
Move nth disk from A to C
Move n−1 disks from B to C using A

C Program:


void toh(int n, char A, char B, char C) {
    if(n == 1) {
        printf("Move disk 1 from %c to %c\n", A, C);
        return;
    }
    toh(n-1, A, C, B);
    printf("Move disk %d from %c to %c\n", n, A, C);
    toh(n-1, B, A, C);
}

Iteration vs Recursion

Basis	Iteration	Recursion
Speed	Faster	Slower
Memory	Less	More
Code	Longer	Shorter
Stack	Not used	Used

Queues

A queue is a linear data structure that follows the principle:

FIFO – First In First Out

Insertion is done at Rear
Deletion is done from Front

Example: People standing in a queue at a ticket counter.

Basic Operations on Queue

(a) Create Queue

Initialize front = -1, rear = -1
Allocate memory (array or linked list)

(b) Add Operation (Enqueue)

Inserts an element at the rear end.

Algorithm (Array Queue):

Check overflow → rear == MAX - 1
If empty, set front = 0
Increment rear
Insert element at queue[rear]

(c) Delete Operation (Dequeue)

Removes an element from the front end.

Algorithm (Array Queue):

Check underflow → front == -1
Remove element at queue[front]
If front == rear, set both to -1
Else increment front

(d) Full Condition

Queue is full when:


rear == MAX - 1

(e) Empty Condition

Queue is empty when:


front == -1

Array Implementation of Queue in C


#include <stdio.h>
#define MAX 5

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

void enqueue(int x) {
    if (rear == MAX - 1)
        printf("Queue Overflow\n");
    else {
        if (front == -1)
            front = 0;
        rear++;
        queue[rear] = x;
        printf("%d inserted\n", x);
    }
}

void dequeue() {
    if (front == -1)
        printf("Queue Underflow\n");
    else {
        printf("%d deleted\n", queue[front]);
        if (front == rear)
            front = rear = -1;
        else
            front++;
    }
}

void display() {
    if (front == -1)
        printf("Queue is empty\n");
    else {
        for (int i = front; i <= rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    dequeue();
    display();
    return 0;
}

Limitations of Simple Queue

Wastage of space
Once rear reaches end, queue cannot reuse freed space

Solution: Circular Queue

Circular Queue

In a circular queue, the last position is connected to the first position, forming a circle.

Condition:


rear = (rear + 1) % MAX

Full Condition:


(front == (rear + 1) % MAX)

Empty Condition:


front == -1

Advantages of Circular Queue

Efficient memory utilization
No space wastage

Circular Queue Implementation in C


#include <stdio.h>
#define MAX 5

int cq[MAX];
int front = -1, rear = -1;

void enqueue(int x) {
    if ((front == (rear + 1) % MAX))
        printf("Circular Queue Overflow\n");
    else {
        if (front == -1)
            front = rear = 0;
        else
            rear = (rear + 1) % MAX;
        cq[rear] = x;
        printf("%d inserted\n", x);
    }
}

void dequeue() {
    if (front == -1)
        printf("Circular Queue Underflow\n");
    else {
        printf("%d deleted\n", cq[front]);
        if (front == rear)
            front = rear = -1;
        else
            front = (front + 1) % MAX;
    }
}

Linked List Implementation of Queue

Front pointer → first node
Rear pointer → last node
Insertion at rear
Deletion at front

Structure Definition


struct node {
    int data;
    struct node *next;
};

Linked Queue Implementation in C


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

struct node {
    int data;
    struct node *next;
};

struct node *front = NULL, *rear = NULL;

void enqueue(int x) {
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = x;
    newNode->next = NULL;

    if (rear == NULL)
        front = rear = newNode;
    else {
        rear->next = newNode;
        rear = newNode;
    }
    printf("%d inserted\n", x);
}

void dequeue() {
    if (front == NULL)
        printf("Queue Underflow\n");
    else {
        struct node *temp = front;
        printf("%d deleted\n", temp->data);
        front = front->next;
        if (front == NULL)
            rear = NULL;
        free(temp);
    }
}

Deque (Double Ended Queue)

A deque allows insertion and deletion at both ends.

Types:

Input Restricted Deque
Output Restricted Deque

Priority Queue

In a priority queue, each element has a priority.
Higher priority elements are served before lower priority elements.

Types:

Ascending Priority Queue
Descending Priority Queue

Example:

Element	Priority
A	1
B	3
C	2

Service Order: B → C → A

Applications of Queue

CPU scheduling
Printer spooling
Breadth First Search (BFS)
Call center systems
Traffic management

Comparison of Queue Implementations

Feature	Array Queue	Circular Queue	Linked Queue
Memory	Fixed	Fixed	Dynamic
Space Use	Poor	Efficient	Efficient
Overflow	Possible	Less	Rare
Complexity	Simple	Moderate	Moderate

Searching

Searching is the process of finding the location of a specific element (key) in a collection of data.

Objectives:

Check whether an element exists
Find the position of an element
Retrieve required data efficiently

Example: Searching roll number 25 in a list of student records.

Sequential Search (Linear Search)

Sequential search checks each element one by one from the beginning until the required element is found or the list ends.

Characteristics:

Works on sorted or unsorted data
Simple to implement
Slow for large data

Algorithm:

Start from first element
Compare key with each element
If match found → return position
If end reached → element not found

C Program:


int linearSearch(int a[], int n, int key) {
    for(int i = 0; i < n; i++) {
        if(a[i] == key)
            return i;
    }
    return -1;
}

Time Complexity:

Best Case: O(1)
Worst Case: O(n)

Index Sequential Search

Index Sequential Search improves sequential search by using an index table.

Concept:

Data is divided into blocks
Index stores highest key of each block

Search is performed in two steps:

Search in index table
Sequential search within block

Example: Index Table

Index	Max Key	Address
1	20	Block 1
2	40	Block 2
3	60	Block 3

To search key 35, go to Block 2.

Advantages:

Faster than linear search
Efficient for large datasets

Disadvantages:

Extra memory for index
Data must be sorted

Binary Search

Binary search repeatedly divides the search space into two halves.

Condition: Data must be sorted

Algorithm:

Find middle element
If key == middle → found
If key < middle → search left half
If key > middle → search right half
Repeat until found or list ends

Iterative Binary Search (C):


int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while(low <= high) {
        mid = (low + high) / 2;
        if(a[mid] == key)
            return mid;
        else if(a[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

Time Complexity:

Best Case: O(1)
Worst Case: O(log n)

Comparison of Searching Techniques

Feature	Sequential	Index Sequential	Binary
Data Order	Any	Sorted	Sorted
Speed	Slow	Medium	Fast
Complexity	O(n)	O(√n) approx	O(log n)
Memory	Low	Extra index	Low

Concept of Hashing

Hashing is a technique used to map a key directly to a memory location using a hash function.

Purpose:

Fast data access
Reduce search time

Hash Function

A hash function converts a key into an index (address).

Example:


h(k) = k % 10

Key = 42
Hash Address = 2

Hash Table

A hash table is an array where data is stored using hash values.

Example:

Index	Value
2	42
5	25

Collision in Hashing

Collision occurs when two keys generate the same hash value.

Example:


h(12) = 2
h(22) = 2

Collision Resolution Techniques

(a) Linear Probing

Search next available slot.


Index = (h(k) + i) % size

(b) Quadratic Probing

Increase gap quadratically.


Index = h(k) + i²

(c) Chaining

Use linked list at each index.

Advantages of Hashing

Very fast search (O(1) average)
Efficient for large data

Disadvantages of Hashing

Collisions
Extra memory
Complex implementation

Hashing is a technique used to store and retrieve data quickly using a hash function.

It converts a key value into an index (address) of a hash table.

Goal:

Fast searching
Fast insertion
Fast deletion

(Time complexity close to O(1))

Hash Table

A hash table is a data structure that stores data in the form of key–value pairs.

Term	Meaning
Key	Input value (e.g., Roll No, Employee ID)
Hash Function	Converts key into index
Hash Table	Array that stores records

Hash Function

A function that maps a key to an index.

Example:


h(k) = k % 10

If key = 123
Index = 123 % 10 = 3

Collision in Hashing

A collision occurs when two or more keys generate the same hash value (index).

Example:


h(k) = k % 10
Keys: 25, 35
25 % 10 = 5
35 % 10 = 5
→ Collision occurs

Why Collision Occurs?

Hash table size is limited
Poor hash function
Large number of keys

Collision Resolution Techniques

Collision resolution techniques are methods used to handle collisions.

Main Categories

Open Addressing
Chaining (Closed Addressing)

Open Addressing

In open addressing, when a collision occurs, the algorithm searches for another empty slot in the hash table.

Types of Open Addressing

Linear Probing
Quadratic Probing
Double Hashing

Linear Probing

If collision occurs at index i, check:


i+1, i+2, i+3, ... until an empty slot is found

Formula


h(k, i) = (h(k) + i) % m

Where:

i = probe number
m = size of hash table

Example

Hash Table Size = 10
Hash Function: h(k) = k % 10

Insert keys: 23, 33, 43

Key	Hash Index	Final Index
23	3	3
33	3 (collision)	4
43	3 (collision)	5

Advantages

Simple to implement
No extra memory needed

Disadvantages

Primary clustering
Performance degrades when table is nearly full

Quadratic Probing

Instead of checking next slots linearly, we use square increments.

Formula


h(k, i) = (h(k) + i²) % m

Example

Hash Table Size = 10
Hash Function: h(k) = k % 10

i	Index
1	h(k)+1²
2	h(k)+2²
3	h(k)+3²

Advantages

Reduces primary clustering
Better than linear probing

Disadvantages

Secondary clustering
May not find empty slot if table size is small

Double Hashing

Uses two hash functions.

First hash function gives initial index
Second hash function gives step size

Formula


h(k, i) = (h1(k) + i × h2(k)) % m

Example


h1(k) = k % 10
h2(k) = 7 − (k % 7)

Advantages

Minimizes clustering
Best performance among open addressing

Disadvantages

More complex
Requires two hash functions

Chaining (Closed Addressing)

Each index of the hash table contains a linked list.
All keys that hash to the same index are stored in the list.

Example

Index	Data
3	23 → 33 → 43
5	15 → 25

Advantages

No overflow problem
Easy deletion
Handles large number of keys

Disadvantages

Extra memory for linked list
Cache performance is poor

Comparison of Collision Resolution Techniques

Technique	Memory	Clustering	Performance
Linear Probing	Low	High	Medium
Quadratic Probing	Low	Medium	Better
Double Hashing	Low	Very Low	Best
Chaining	High	No clustering	Good

Load Factor (α)


α = Number of keys / Hash table size

Importance

Higher load factor → More collisions
Ideal value: α ≤ 0.7

Applications of Hashing

Database indexing
Symbol tables in compilers
Password authentication
Caching
File systems

Exam Important Points (MCA)

✔ Definition of hashing
✔ Meaning of collision
✔ Linear vs Quadratic vs Double hashing
✔ Chaining vs Open Addressing
✔ Load factor
✔ Advantages and disadvantages
✔ Numerical examples