Complete Data Structures C++ Implementation Templates

Computer science54.36 KB

Summary

This document provides comprehensive C++ code templates and explanations for fundamental data structures and algorithms. It covers arrays, singly and doubly linked lists, circular lists, stacks, queues, recursion, and merge sort, complete with safety checks and edge cases for academic exams.

Key points

  • Arrays support operations like traversal, searching, insertion, deletion, and sorting with O(n) or O(n log n) complexities.
  • Singly and doubly linked lists manage dynamic data using pointers like head, tail, next, and prev.
  • Stacks follow the LIFO principle, implemented using arrays or linked lists, essential for expression evaluation and parentheses matching.
  • Queues follow the FIFO principle, featuring linear, circular, and linked queue implementations.
  • Recursion and divide-and-conquer techniques are demonstrated through factorial, Fibonacci, Towers of Hanoi, and merge sort.

Test yourself

Lecture 1 — Introduction to Data Structures

Is lecture mein mostly theory, ADT, data organization, time aur space complexity aati hai. Is mein koi specific data structure implementation template nahi.

Basic program template:

#include <iostream>
using namespace std;

int main()
{
    // Declare variables

    // Take input

    // Perform operation

    // Display output

    return 0;
}

Algorithm likhne ka template:

START
    Input data
    Perform required operation
    Display result
STOP

ADT (Abstract Data Type) ka answer likhne ke liye:

  • Data structure ka naam

  • Data kis tarah store hota hai

  • Available operations

  • Operations ka expected behaviour

Example: Stack ADT mein push, pop, top, isEmpty operations hoti hain.

Lecture 2 — Arrays

High priority

1. Array declaration and input/output

Ye sab se basic template hai.

#include <iostream>
using namespace std;

int main()
{
    int arr[100];
    int n;

    cout << "Enter size: ";
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Kis question mein? Array input lena, display karna, traverse karna.

2. Traversal

for (int i = 0; i < n; i++)
{
    cout << arr[i] << " ";
}

3. Sum of array

int sum = 0;

for (int i = 0; i < n; i++)
{
    sum = sum + arr[i];
}

cout << sum;

4. Maximum element

int maxValue = arr[0];

for (int i = 1; i < n; i++)
{
    if (arr[i] > maxValue)
    {
        maxValue = arr[i];
    }
}

cout << maxValue;

5. Minimum element

int minValue = arr[0];

for (int i = 1; i < n; i++)
{
    if (arr[i] < minValue)
    {
        minValue = arr[i];
    }
}

cout << minValue;

6. Linear Search

int key;
cin >> key;

int found = -1;

for (int i = 0; i < n; i++)
{
    if (arr[i] == key)
    {
        found = i;
        break;
    }
}

if (found != -1)
    cout << "Found at index " << found;
else
    cout << "Not found";

Kis question mein? Kisi value ko array mein search karna.

7. Insertion at a given index

int pos, value;
cin >> pos >> value;

for (int i = n; i > pos; i--)
{
    arr[i] = arr[i - 1];
}

arr[pos] = value;
n++;

Samjho: Right side se elements shift karte hain taake position empty ho jaye.

8. Deletion at a given index

int pos;
cin >> pos;

for (int i = pos; i < n - 1; i++)
{
    arr[i] = arr[i + 1];
}

n--;

Samjho: Left side se elements shift karke deleted position fill kar dete hain.

9. Bubble Sort — Ascending

for (int i = 0; i < n - 1; i++)
{
    for (int j = 0; j < n - i - 1; j++)
    {
        if (arr[j] > arr[j + 1])
        {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

Descending ke liye sirf condition change:

if (arr[j] < arr[j + 1])

10. Binary Search

Must prepare

Condition: Array sorted hona chahiye.

int key;
cin >> key;

int low = 0;
int high = n - 1;
int found = -1;

while (low <= high)
{
    int mid = low + (high - low) / 2;

    if (arr[mid] == key)
    {
        found = mid;
        break;
    }
    else if (arr[mid] < key)
    {
        low = mid + 1;
    }
    else
    {
        high = mid - 1;
    }
}

cout << found;

11. Reverse an array

int start = 0;
int end = n - 1;

while (start < end)
{
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;

    start++;
    end--;
}

12. Dynamic Array

int n;
cin >> n;

int* arr = new int[n];

for (int i = 0; i < n; i++)
{
    cin >> arr[i];
}

for (int i = 0; i < n; i++)
{
    cout << arr[i] << " ";
}

delete[] arr;

13. 2D Array

int arr[3][3];

for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < 3; j++)
    {
        cin >> arr[i][j];
    }
}

for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < 3; j++)
    {
        cout << arr[i][j] << " ";
    }

    cout << endl;
}

14. Vector Template

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    v.pop_back();

    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }

    return 0;
}

Array ke questions mein yaad rakho:

Question

Template

Display

Traversal

Total

Sum

Largest

Maximum

Smallest

Minimum

Find value

Linear/Binary Search

Add value

Insertion

Remove value

Deletion

Arrange values

Sorting

Reverse

Two pointers

DS Lec2-Arrays.pdf

Lecture 3 — Singly Linked List

Very high priority

Is lecture ka sab se important part Node aur pointers hain.

1. Node class — Ye sab se pehle likhni hai

class Node
{
public:
    int data;
    Node* next;

    Node(int value)
    {
        data = value;
        next = NULL;
    }
};

Meaning:

  • data = value store karta hai.

  • next = next node ka address store karta hai.

  • NULL = aage koi node nahi.

2. Linked List class ka basic structure

class LinkedList
{
    Node* head;

public:

    LinkedList()
    {
        head = NULL;
    }

};

head first node ka address rakhta hai.

3. Insertion at Beginning

void insertAtBeginning(int value)
{
    Node* newNode = new Node(value);

    newNode->next = head;

    head = newNode;
}

Diagram:

Before:
head → 10 → 20 → NULL

Insert 5

After:
head → 5 → 10 → 20 → NULL

4. Insertion at End

void insertAtEnd(int value)
{
    Node* newNode = new Node(value);

    if (head == NULL)
    {
        head = newNode;
        return;
    }

    Node* temp = head;

    while (temp->next != NULL)
    {
        temp = temp->next;
    }

    temp->next = newNode;
}

5. Insertion at Position

Yahan position 1-based hai.

void insertAtPosition(int value, int pos)
{
    Node* newNode = new Node(value);

    if (pos == 1)
    {
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* temp = head;

    for (int i = 1; i < pos - 1; i++)
    {
        temp = temp->next;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

6. Deletion from Beginning

void deleteFromBeginning()
{
    if (head == NULL)
        return;

    Node* temp = head;

    head = head->next;

    delete temp;
}

7. Deletion from End

void deleteFromEnd()
{
    if (head == NULL)
        return;

    if (head->next == NULL)
    {
        delete head;
        head = NULL;
        return;
    }

    Node* temp = head;

    while (temp->next->next != NULL)
    {
        temp = temp->next;
    }

    delete temp->next;

    temp->next = NULL;
}

8. Deletion at Position

void deleteAtPosition(int pos)
{
    if (head == NULL)
        return;

    if (pos == 1)
    {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* temp = head;

    for (int i = 1; i < pos - 1; i++)
    {
        temp = temp->next;
    }

    Node* delNode = temp->next;

    temp->next = delNode->next;

    delete delNode;
}

9. Traversal / Display

void display()
{
    Node* temp = head;

    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

10. Search

bool search(int key)
{
    Node* temp = head;

    while (temp != NULL)
    {
        if (temp->data == key)
            return true;

        temp = temp->next;
    }

    return false;
}

11. Count Nodes

int countNodes()
{
    int count = 0;
    Node* temp = head;

    while (temp != NULL)
    {
        count++;
        temp = temp->next;
    }

    return count;
}

12. Delete a Specific Value

void deleteValue(int value)
{
    if (head == NULL)
        return;

    if (head->data == value)
    {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* prev = head;
    Node* curr = head->next;

    while (curr != NULL && curr->data != value)
    {
        prev = curr;
        curr = curr->next;
    }

    if (curr == NULL)
        return;

    prev->next = curr->next;

    delete curr;
}

13. Concatenate Two Linked Lists

void concatenate(Node* head2)
{
    if (head == NULL)
    {
        head = head2;
        return;
    }

    Node* temp = head;

    while (temp->next != NULL)
    {
        temp = temp->next;
    }

    temp->next = head2;
}

Important linked list patterns:

Question

Kya use hoga?

Start par insert

newNode->next = head

End par insert

temp->next = newNode

Start se delete

head = head->next

End se delete

Second-last node find karo

Traverse

temp = temp->next

Search

temp->data == key

Specific delete

prev->next = curr->next

DS Lec 4-Doubly and Circular Linked Lists.pdf

Lecture 4 — Doubly and Circular Linked Lists

High priority

Part A: Doubly Linked List

Singly linked list mein aik pointer hota hai: next.

Doubly linked list mein two pointers hote hain:

  • next = next node ka address

  • prev = previous node ka address

Diagram:

NULL ← 10 ⇄ 20 ⇄ 30 → NULL
       head          tail

1. Node Class

class Node
{
public:
    int data;
    Node* next;
    Node* prev;

    Node(int value)
    {
        data = value;
        next = NULL;
        prev = NULL;
    }
};

2. Doubly Linked List Structure

class DoublyList
{
    Node* head;
    Node* tail;

public:

    DoublyList()
    {
        head = NULL;
        tail = NULL;
    }

};

3. Insert at Beginning

void insertAtBeginning(int value)
{
    Node* newNode = new Node(value);

    if (head == NULL)
    {
        head = tail = newNode;
        return;
    }

    newNode->next = head;
    head->prev = newNode;

    head = newNode;
}

4. Insert at End

void insertAtEnd(int value)
{
    Node* newNode = new Node(value);

    if (head == NULL)
    {
        head = tail = newNode;
        return;
    }

    tail->next = newNode;
    newNode->prev = tail;

    tail = newNode;
}

5. Delete from Beginning

void deleteFromBeginning()
{
    if (head == NULL)
        return;

    Node* temp = head;

    if (head == tail)
    {
        head = tail = NULL;
    }
    else
    {
        head = head->next;
        head->prev = NULL;
    }

    delete temp;
}

6. Delete from End

void deleteFromEnd()
{
    if (tail == NULL)
        return;

    Node* temp = tail;

    if (head == tail)
    {
        head = tail = NULL;
    }
    else
    {
        tail = tail->prev;
        tail->next = NULL;
    }

    delete temp;
}

7. Forward Traversal

void displayForward()
{
    Node* temp = head;

    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

8. Backward Traversal

void displayBackward()
{
    Node* temp = tail;

    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->prev;
    }
}

9. Delete a Specific Value

void deleteValue(int value)
{
    Node* temp = head;

    while (temp != NULL && temp->data != value)
    {
        temp = temp->next;
    }

    if (temp == NULL)
        return;

    if (temp == head)
    {
        deleteFromBeginning();
        return;
    }

    if (temp == tail)
    {
        deleteFromEnd();
        return;
    }

    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;

    delete temp;
}

Doubly linked list ka golden rule: Beech mein insertion/deletion karte waqt dono directions ke links update karne hain.

Part B: Circular Singly Linked List

Circular list mein last node ka next, NULL nahi hota. Woh first node ko point karta hai.

head → 10 → 20 → 30
        ↑         |
        └─────────┘

Lecture mein circular singly linked list ko tail pointer se implement kiya gaya hai.

tail->next first node hota hai.

1. Node Class

class Node
{
public:
    int data;
    Node* next;

    Node(int value)
    {
        data = value;
        next = NULL;
    }
};

2. Circular List Structure

class CircularList
{
    Node* tail;

public:

    CircularList()
    {
        tail = NULL;
    }

};

3. Insert at Beginning

void insertAtBeginning(int value)
{
    Node* newNode = new Node(value);

    if (tail == NULL)
    {
        tail = newNode;
        tail->next = tail;
    }
    else
    {
        newNode->next = tail->next;
        tail->next = newNode;
    }
}

4. Insert at End

void insertAtEnd(int value)
{
    Node* newNode = new Node(value);

    if (tail == NULL)
    {
        tail = newNode;
        tail->next = tail;
    }
    else
    {
        newNode->next = tail->next;
        tail->next = newNode;
        tail = newNode;
    }
}

5. Delete from Beginning

void deleteFromBeginning()
{
    if (tail == NULL)
        return;

    Node* head = tail->next;

    if (head == tail)
    {
        delete head;
        tail = NULL;
    }
    else
    {
        tail->next = head->next;
        delete head;
    }
}

6. Delete from End

void deleteFromEnd()
{
    if (tail == NULL)
        return;

    Node* head = tail->next;

    if (head == tail)
    {
        delete tail;
        tail = NULL;
        return;
    }

    Node* temp = head;

    while (temp->next != tail)
    {
        temp = temp->next;
    }

    temp->next = tail->next;

    delete tail;

    tail = temp;
}

7. Display Circular List

void display()
{
    if (tail == NULL)
        return;

    Node* temp = tail->next;

    do
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    while (temp != tail->next);
}

Important: Circular list mein normal while(temp != NULL) traversal nahi karte, kyun ke NULL aata hi nahi. Is liye do-while use hota hai.

Part C: Circular Doubly Linked List

Is mein har node ke next aur prev pointers hote hain, aur dono ends circularly connected hote hain.

10 ⇄ 20 ⇄ 30
↑          ↓
└──────────┘

Agar head aur tail dono available hon:

Insert at Beginning

void insertAtBeginning(int value)
{
    Node* newNode = new Node(value);

    if (head == NULL)
    {
        head = tail = newNode;
        newNode->next = newNode;
        newNode->prev = newNode;
    }
    else
    {
        newNode->next = head;
        newNode->prev = tail;

        head->prev = newNode;
        tail->next = newNode;

        head = newNode;
    }
}

Insert at End

void insertAtEnd(int value)
{
    Node* newNode = new Node(value);

    if (head == NULL)
    {
        head = tail = newNode;
        newNode->next = newNode;
        newNode->prev = newNode;
    }
    else
    {
        newNode->prev = tail;
        newNode->next = head;

        tail->next = newNode;
        head->prev = newNode;

        tail = newNode;
    }
}

Exam mein yaad rakhna:

Type

Node pointers

Last node

Singly

next

next = NULL

Doubly

prev, next

next = NULL

Circular Singly

next

next = head

Circular Doubly

prev, next

tail->next = head, head->prev = tail

DS Lec 4-Doubly and Circular Linked Lists.pdf

Lecture 5 — Stack

Very high priority

Stack LIFO follow karta hai:

Last In, First Out

Jo element last mein insert hota hai, woh pehle remove hota hai.

Important operations:

  • push() = insert

  • pop() = remove

  • top() / peek() = top element dekhna

  • isEmpty() = check empty

  • isFull() = check full

Part A: Stack Using Array

1. Complete Stack Class

#include <iostream>
using namespace std;

#define SIZE 5

class Stack
{
    int arr[SIZE];
    int top;

public:

    Stack()
    {
        top = -1;
    }

    bool isEmpty()
    {
        return top == -1;
    }

    bool isFull()
    {
        return top == SIZE - 1;
    }

    void push(int value)
    {
        if (isFull())
        {
            cout << "Stack Overflow\n";
            return;
        }

        top++;
        arr[top] = value;
    }

    int pop()
    {
        if (isEmpty())
        {
            cout << "Stack Underflow\n";
            return -1;
        }

        return arr[top--];
    }

    int peek()
    {
        if (isEmpty())
            return -1;

        return arr[top];
    }

    void display()
    {
        for (int i = top; i >= 0; i--)
        {
            cout << arr[i] << " ";
        }

        cout << endl;
    }
};

2. Main Function

int main()
{
    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);

    s.display();

    cout << s.peek() << endl;

    cout << s.pop() << endl;

    s.display();

    return 0;
}

Output:

30 20 10
30
30
20 10

Part B: Stack Using Linked List

1. Node Class

class Node
{
public:
    int data;
    Node* next;

    Node(int value)
    {
        data = value;
        next = NULL;
    }
};

2. Stack Class

class Stack
{
    Node* topNode;

public:

    Stack()
    {
        topNode = NULL;
    }

    bool isEmpty()
    {
        return topNode == NULL;
    }

    void push(int value)
    {
        Node* newNode = new Node(value);

        newNode->next = topNode;

        topNode = newNode;
    }

    int pop()
    {
        if (isEmpty())
            return -1;

        Node* temp = topNode;

        int value = temp->data;

        topNode = topNode->next;

        delete temp;

        return value;
    }

    int peek()
    {
        if (isEmpty())
            return -1;

        return topNode->data;
    }

    void display()
    {
        Node* temp = topNode;

        while (temp != NULL)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }

        cout << endl;
    }
};

Difference yaad rakho:

Array Stack

Linked List Stack

Fixed size

Dynamic size

top = -1

topNode = NULL

arr[++top]

New node at beginning

arr[top--]

Delete first node

Part C: Reverse a String Using Stack

string str = "HELLO";
Stack s;

for (int i = 0; i < str.length(); i++)
{
    s.push(str[i]);
}

while (!s.isEmpty())
{
    cout << (char)s.pop();
}

Output:

OLLEH

Part D: Parentheses Matching

Ye bohat common stack question hai.

bool isBalanced(string str)
{
    Stack s;

    for (int i = 0; i < str.length(); i++)
    {
        char ch = str[i];

        if (ch == '(' || ch == '[' || ch == '{')
        {
            s.push(ch);
        }
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (s.isEmpty())
                return false;

            char x = s.pop();

            if (ch == ')' && x != '(')
                return false;

            if (ch == ']' && x != '[')
                return false;

            if (ch == '}' && x != '{')
                return false;
        }
    }

    return s.isEmpty();
}

Example:

{[()]}  → Balanced
([)]    → Not Balanced
((())   → Not Balanced

Part E: Postfix Evaluation

Example:

23+

Is ka answer 5 hai.

Rule: Left operand pehle pop karo, right operand doosre pop karo.

int evaluatePostfix(string exp)
{
    Stack s;

    for (int i = 0; i < exp.length(); i++)
    {
        char ch = exp[i];

        if (ch >= '0' && ch <= '9')
        {
            s.push(ch - '0');
        }
        else
        {
            int b = s.pop();
            int a = s.pop();

            if (ch == '+')
                s.push(a + b);
            else if (ch == '-')
                s.push(a - b);
            else if (ch == '*')
                s.push(a * b);
            else if (ch == '/')
                s.push(a / b);
        }
    }

    return s.pop();
}

Ye basic template single-digit operands aur + - * / ke liye hai.

Part F: Infix to Postfix — Basic Template

Example:

A+B*C

Postfix:

ABC*+

Operator priority:

Operator

Priority

^

3

*, /

2

+, -

1

Priority function:

int priority(char ch)
{
    if (ch == '^')
        return 3;

    if (ch == '*' || ch == '/')
        return 2;

    if (ch == '+' || ch == '-')
        return 1;

    return 0;
}

Basic conversion logic:

string infixToPostfix(string exp)
{
    Stack s;
    string postfix = "";

    for (int i = 0; i < exp.length(); i++)
    {
        char ch = exp[i];

        if (ch >= 'A' && ch <= 'Z')
        {
            postfix += ch;
        }
        else if (ch == '(')
        {
            s.push(ch);
        }
        else if (ch == ')')
        {
            while (!s.isEmpty() && s.peek() != '(')
            {
                postfix += (char)s.pop();
            }

            s.pop();
        }
        else
        {
            while (!s.isEmpty() && s.peek() != '(' &&
                   priority(s.peek()) >= priority(ch))
            {
                postfix += (char)s.pop();
            }

            s.push(ch);
        }
    }

    while (!s.isEmpty())
    {
        postfix += (char)s.pop();
    }

    return postfix;
}

Important limitation: Ye basic conversion template ^ ki right associativity handle nahi karta. Agar paper mein exponent ^ ho, toh equal priority par >= ki jagah associativity check karni hogi. A^B^C ka correct postfix ABC^^ hota hai.

DS_Lec_5-Stack.pdf

Lecture 6 — Queues

Very high priority

Queue FIFO follow karti hai:

First In, First Out

  • enqueue() = insert from rear

  • dequeue() = remove from front

  • front = first element

  • rear = last element

Part A: Linear Queue Using Array

#include <iostream>
using namespace std;

#define SIZE 5

class Queue
{
    int arr[SIZE];
    int front, rear;

public:

    Queue()
    {
        front = -1;
        rear = -1;
    }

    bool isEmpty()
    {
        return front == -1;
    }

    bool isFull()
    {
        return rear == SIZE - 1;
    }

    void enqueue(int value)
    {
        if (isFull())
        {
            cout << "Queue Overflow\n";
            return;
        }

        if (front == -1)
            front = 0;

        rear++;
        arr[rear] = value;
    }

    int dequeue()
    {
        if (isEmpty())
        {
            cout << "Queue Underflow\n";
            return -1;
        }

        int value = arr[front];

        if (front == rear)
        {
            front = rear = -1;
        }
        else
        {
            front++;
        }

        return value;
    }

    void display()
    {
        if (isEmpty())
            return;

        for (int i = front; i <= rear; i++)
        {
            cout << arr[i] << " ";
        }

        cout << endl;
    }
};

Part B: Circular Queue Using Array

Must prepare

Circular queue mein empty spaces dobara use ho sakti hain.

Magic formula:

(rear + 1) % SIZE
(front + 1) % SIZE

Complete template:

#include <iostream>
using namespace std;

#define SIZE 5

class CircularQueue
{
    int arr[SIZE];
    int front, rear, count;

public:

    CircularQueue()
    {
        front = 0;
        rear = -1;
        count = 0;
    }

    bool isEmpty()
    {
        return count == 0;
    }

    bool isFull()
    {
        return count == SIZE;
    }

    void enqueue(int value)
    {
        if (isFull())
        {
            cout << "Queue Full\n";
            return;
        }

        rear = (rear + 1) % SIZE;

        arr[rear] = value;

        count++;
    }

    int dequeue()
    {
        if (isEmpty())
        {
            cout << "Queue Empty\n";
            return -1;
        }

        int value = arr[front];

        front = (front + 1) % SIZE;

        count--;

        return value;
    }

    void display()
    {
        for (int i = 0; i < count; i++)
        {
            cout << arr[(front + i) % SIZE] << " ";
        }

        cout << endl;
    }
};

Part C: Queue Using Linked List

1. Node Class

class Node
{
public:
    int data;
    Node* next;

    Node(int value)
    {
        data = value;
        next = NULL;
    }
};

2. Linked Queue Class

class LinkedQueue
{
    Node* front;
    Node* rear;

public:

    LinkedQueue()
    {
        front = rear = NULL;
    }

    bool isEmpty()
    {
        return front == NULL;
    }

    void enqueue(int value)
    {
        Node* newNode = new Node(value);

        if (isEmpty())
        {
            front = rear = newNode;
            return;
        }

        rear->next = newNode;

        rear = newNode;
    }

    int dequeue()
    {
        if (isEmpty())
            return -1;

        Node* temp = front;

        int value = temp->data;

        front = front->next;

        if (front == NULL)
            rear = NULL;

        delete temp;

        return value;
    }

    int getFront()
    {
        if (isEmpty())
            return -1;

        return front->data;
    }

    void display()
    {
        Node* temp = front;

        while (temp != NULL)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }

        cout << endl;
    }
};

Queue ke important differences

Linear Queue

Circular Queue

Linked Queue

Array

Circular array

Linked nodes

Fixed size

Fixed size

Dynamic

Empty spaces waste ho sakti hain

Empty spaces reuse hoti hain

Nodes as needed

Front/rear indexes

Front/rear with modulo

Front/rear pointers

Priority Queue aur Deque: Lecture mein inki types aur concepts bhi diye gaye hain. Inhein normal queue ke same code se implement nahi karna; priority queue mein priority ke hisaab se removal hota hai aur deque mein dono ends se insertion/deletion ho sakti hai.

DS_Lec_6-Queues.pdf

Lecture 7 — Recursion and Divide & Conquer

Very high priority

1. Basic Recursion Template

Har recursive question mein ye pattern yaad rakho:

returnType functionName(int n)
{
    if (baseCondition)
        return baseValue;

    return operation + functionName(smallerInput);
}

Do cheezein lazmi hain:

  1. Base case — recursion stop karne ke liye.

  2. Recursive call — smaller input ke saath function ko dobara call karna.

2. Factorial

int factorial(int n)
{
    if (n == 0)
        return 1;

    return n * factorial(n - 1);
}

3. Sum from 1 to n

int sum(int n)
{
    if (n == 1)
        return 1;

    return n + sum(n - 1);
}

4. Fibonacci

int fib(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

5. Power xⁿ

int power(int x, int n)
{
    if (n == 0)
        return 1;

    return x * power(x, n - 1);
}

6. GCD

int gcd(int a, int b)
{
    if (b == 0)
        return a;

    return gcd(b, a % b);
}

7. Recursive Binary Search

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);

    return binarySearch(arr, low, mid - 1, key);
}

8. Towers of Hanoi

void hanoi(int n, char from, char to, char spare)
{
    if (n == 0)
        return;

    hanoi(n - 1, from, spare, to);

    cout << from << " -> " << to << endl;

    hanoi(n - 1, spare, to, from);
}

Moves ka formula:

2ⁿ - 1

9. Find Maximum Using Divide and Conquer

int findMax(int arr[], int low, int high)
{
    if (low == high)
        return arr[low];

    int mid = low + (high - low) / 2;

    int left = findMax(arr, low, mid);

    int right = findMax(arr, mid + 1, high);

    if (left > right)
        return left;
    else
        return right;
}

10. Merge Sort

Must prepare complete code

Merge Sort Function

void mergeSort(int arr[], int low, int high)
{
    if (low >= high)
        return;

    int mid = low + (high - low) / 2;

    mergeSort(arr, low, mid);

    mergeSort(arr, mid + 1, high);

    merge(arr, low, mid, high);
}

Merge Function

void merge(int arr[], int low, int mid, int high)
{
    int temp[100];

    int i = low;
    int j = mid + 1;
    int k = low;

    while (i <= mid && j <= high)
    {
        if (arr[i] <= arr[j])
        {
            temp[k] = arr[i];
            i++;
        }
        else
        {
            temp[k] = arr[j];
            j++;
        }

        k++;
    }

    while (i <= mid)
    {
        temp[k] = arr[i];
        i++;
        k++;
    }

    while (j <= high)
    {
        temp[k] = arr[j];
        j++;
        k++;
    }

    for (int x = low; x <= high; x++)
    {
        arr[x] = temp[x];
    }
}

Main Function

int main()
{
    int arr[] = {38, 27, 43, 3};
    int n = 4;

    mergeSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

3 27 38 43

Lecture 7 ki complexities:

Algorithm

Complexity

Factorial

O(n)

Sum

O(n)

Fibonacci

O(2ⁿ) approximately

Power

O(n)

GCD

O(log n)

Binary Search

O(log n)

Hanoi

O(2ⁿ)

Find Maximum

O(n)

Merge Sort

O(n log n)

DS_Lec_7-Recursion.pdf

Master Revision — Question dekh kar kaunsa template likhna hai?

Ye table paper mein bohat help karegi.

Question mein ye words hon

Tumhara template

Insert element in array

Array insertion

Delete element from array

Array deletion

Find largest/smallest

Maximum/minimum

Search an element

Linear/Binary Search

Sort array

Bubble Sort / Merge Sort

Reverse array

Two pointers

Insert node at start

Linked List insertion beginning

Insert node at end

Linked List insertion end

Delete first node

Delete beginning

Delete last node

Delete end

Search in linked list

Linked List search

Print all nodes

Traversal

Previous and next pointer

Doubly Linked List

Last points to first

Circular Linked List

Add at top

Stack push

Remove from top

Stack pop

Last element first

Stack / LIFO

First element first

Queue / FIFO

Add at rear

Enqueue

Remove from front

Dequeue

Reuse empty queue positions

Circular Queue

Function calls itself

Recursion

Find factorial

Factorial recursion

Find GCD

Euclid recursion

Search sorted array recursively

Recursive Binary Search

Divide into halves and merge

Merge Sort

Move disks between rods

Towers of Hanoi

Most Important Patterns to Memorize

Ye 12 lines tumhare liye bohat valuable hain:

Arrays

arr[i] = value;

Array shifting

arr[i] = arr[i - 1];
arr[i] = arr[i + 1];

Singly Linked List

temp = temp->next;
newNode->next = head;
head = newNode;

Doubly Linked List

newNode->next = head;
head->prev = newNode;

Stack

arr[++top] = value;
arr[top--];

Queue

arr[++rear] = value;
arr[++front];

Circular Queue

rear = (rear + 1) % SIZE;
front = (front + 1) % SIZE;

Recursion

if (n == 0) return 1;
return n * factorial(n - 1);

Paper ke liye priority list

Agar time kam ho toh is order mein code practice karo:

Priority 1 — Pehle ye complete karo

  • Array insertion and deletion
  • Linear and Binary Search
  • Bubble Sort
  • Singly Linked List insertion/deletion
  • Doubly Linked List insertion/deletion
  • Stack push/pop
  • Queue enqueue/dequeue
  • Circular Queue
  • Factorial and Fibonacci
  • Recursive Binary Search
  • Merge Sort

Priority 2 — Iske baad

  • Circular Linked List
  • Linked Stack and Linked Queue
  • Parentheses Matching
  • Postfix Evaluation
  • Infix to Postfix
  • GCD and Towers of Hanoi
  • Find Maximum using Divide and Conquer

Ab ek important exam tip

Code likhte waqt har question mein ye 5 steps follow karna:

  1. Pehle data structure identify karo.

  2. Required variables/pointers declare karo.

  3. Empty condition check karo.

  4. Main operation perform karo.

  5. Result display ya return karo.

Aur ek baat: Is template book mein core lecture operations cover hain, lekin kuch templates basic versions hain. Jaise array insertion mein valid index aur capacity check, linked list mein invalid position check, aur stack expression conversion mein operator associativity jaise cases question ke mutabiq add karne honge.

Meri advice hai ke ab hum in templates ka exam-style practice paper solve karein: main tumhein question doon, tum template identify karo aur code likho; jahan mistake ho main Roman Urdu mein samjha doon. Is se tumhein actual paper mein template apply karna aa jayega.

1. Arrays — Insertion aur Deletion with Checks

A. Array mein insertion (valid position + capacity check)

#include <iostream>
using namespace std;

int main() {
    int arr[100], n, pos, value;
    int capacity = 100;

    cout << "Enter size: ";
    cin >> n;

    if (n < 0 || n > capacity) {
        cout << "Invalid size";
        return 0;
    }

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << "Enter position (0 to " << n << "): ";
    cin >> pos;

    cout << "Enter value: ";
    cin >> value;

    if (n == capacity) {
        cout << "Array is full";
    }
    else if (pos < 0 || pos > n) {
        cout << "Invalid position";
    }
    else {
        for (int i = n; i > pos; i--) {
            arr[i] = arr[i - 1];
        }

        arr[pos] = value;
        n++;

        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
    }

    return 0;
}

Samjho:

  • n == capacity check karta hai ke array full toh nahi.

  • pos < 0 || pos > n invalid position check karta hai.

  • i = n se shifting start hoti hai.

  • arr[i] = arr[i-1] elements ko right shift karta hai.

  • arr[pos] = value new value insert karta hai.

  • n++ size increase karta hai.

Example: [10, 20, 30] mein position 1 par 15 insert karna hai.

Result: [10, 15, 20, 30]

B. Array mein deletion (valid position check)

int pos;

cout << "Enter position: ";
cin >> pos;

if (pos < 0 || pos >= n) {
    cout << "Invalid position";
}
else {
    for (int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }

    n--;
}

Yaad rakho:

  • Insertion mein valid position 0 to n hoti hai.

  • Deletion mein valid position 0 to n-1 hoti hai.

  • Insertion mein right shift.

  • Deletion mein left shift.

2. Singly Linked List — Invalid Position Checks

Position-based insertion aur deletion mein sabse important cheez hai ke pointer NULL tak na pohanch jaye.

A. Insert at position (1-based indexing)

void insertAtPosition(int value, int pos) {

    if (pos < 1) {
        cout << "Invalid position";
        return;
    }

    Node* newNode = new Node(value);

    if (pos == 1) {
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* temp = head;

    for (int i = 1; i < pos - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        cout << "Invalid position";
        delete newNode;
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

Samjho:

  1. Position 1 se chhoti hai toh invalid.

  2. Agar position 1 hai toh beginning par insert.

  3. temp ko insertion wali position se ek node pehle le jao.

  4. Agar temp == NULL ho gaya toh position invalid.

  5. New node ko links ke darmiyan connect kar do.

Example:

10 → 20 → 30 → NULL

Position 2 par 15 insert:

10 → 15 → 20 → 30 → NULL

B. Delete at position (1-based indexing)

void deleteAtPosition(int pos) {

    if (head == NULL || pos < 1) {
        cout << "Invalid position";
        return;
    }

    if (pos == 1) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* temp = head;

    for (int i = 1; i < pos - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        cout << "Invalid position";
        return;
    }

    Node* delNode = temp->next;
    temp->next = delNode->next;

    delete delNode;
}

Important lines:

Node* delNode = temp->next;
temp->next = delNode->next;
delete delNode;

Pehle delete hone wale node ka address save hota hai, phir links connect hotay hain aur aakhir mein memory free hoti hai.

3. Doubly Linked List — Safe Deletion

Doubly linked list mein prev aur next dono links update karne hote hain.

Delete a node at a given position

void deleteAtPosition(int pos) {

    if (head == NULL || pos < 1) {
        cout << "Invalid position";
        return;
    }

    Node* temp = head;

    for (int i = 1; i < pos && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        cout << "Invalid position";
        return;
    }

    if (temp == head)
        head = temp->next;

    if (temp == tail)
        tail = temp->prev;

    if (temp->prev != NULL)
        temp->prev->next = temp->next;

    if (temp->next != NULL)
        temp->next->prev = temp->prev;

    delete temp;
}

Iska main concept:

Doubly linked list mein middle node delete karna

Delete 20 from this list:

10 ⇄ 20 ⇄ 30

10 ka next ab 30, aur 30 ka prev ab 10.

4. Stack — Overflow, Underflow aur Safe Operations

Array stack ka corrected template:

#define SIZE 5

class Stack {
    int arr[SIZE];
    int top;

public:

    Stack() {
        top = -1;
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == SIZE - 1;
    }

    void push(int value) {

        if (isFull()) {
            cout << "Stack Overflow";
            return;
        }

        arr[++top] = value;
    }

    int pop() {

        if (isEmpty()) {
            cout << "Stack Underflow";
            return -1;
        }

        return arr[top--];
    }

    int peek() {

        if (isEmpty()) {
            cout << "Stack is empty";
            return -1;
        }

        return arr[top];
    }
};

Do terms yaad rakho:

  • Overflow: full stack mein push karne ki koshish.

  • Underflow: empty stack se pop karne ki koshish.

5. Infix to Postfix — Operator Precedence aur Associativity

Ye exam ke liye bohat important hai, especially ^ operator.

Operator precedence

Operator

Priority

Associativity

^

3

Right to Left

* /

2

Left to Right

+ -

1

Left to Right

(

0

Special

A. Priority function

int priority(char ch) {

    if (ch == '^')
        return 3;

    if (ch == '*' || ch == '/')
        return 2;

    if (ch == '+' || ch == '-')
        return 1;

    return 0;
}

B. Correct operator popping condition

while (!s.empty() && s.top() != '(' &&
       (priority(s.top()) > priority(ch) ||
       (priority(s.top()) == priority(ch) && ch != '^'))) {

    postfix += s.top();
    s.pop();
}

Ye condition kyun important hai?

Normally equal priority par pehle wala operator pop hota hai, lekin ^ right-to-left hota hai. Isliye jab current operator ^ ho, equal priority par pop nahi karna.

Example:

Expression 1

A + B * C

ABC*+

Multiplication ki priority addition se zyada hai.

Expression 2

A ^ B ^ C

ABC^^

Pehle B^C, phir A^(B^C). Isliye right-to-left.

Expression 3

A - B - C

AB-C-

Minus left-to-right hota hai: (A-B)-C.

C. Complete infix-to-postfix function

Ye version single-character operands ke liye hai, jaise A+B*C:

#include <iostream>
#include <stack>
#include <string>
using namespace std;

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

string toPostfix(string infix) {

    stack<char> s;
    string postfix = "";

    for (int i = 0; i < infix.length(); i++) {

        char ch = infix[i];

        if (ch == ' ')
            continue;

        if ((ch >= 'A' && ch <= 'Z') ||
            (ch >= 'a' && ch <= 'z') ||
            (ch >= '0' && ch <= '9')) {

            postfix += ch;
        }

        else if (ch == '(') {
            s.push(ch);
        }

        else if (ch == ')') {

            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }

            if (!s.empty())
                s.pop();
        }

        else {

            while (!s.empty() && s.top() != '(' &&
                   (priority(s.top()) > priority(ch) ||
                   (priority(s.top()) == priority(ch) && ch != '^'))) {

                postfix += s.top();
                s.pop();
            }

            s.push(ch);
        }
    }

    while (!s.empty()) {
        if (s.top() != '(')
            postfix += s.top();

        s.pop();
    }

    return postfix;
}

int main() {

    string infix;

    cout << "Enter infix: ";
    cin >> infix;

    cout << "Postfix: " << toPostfix(infix);

    return 0;
}

6. Postfix Evaluation — Stack Empty Check

Postfix mein operator milne par do operands pop karte hain. Isliye check karna zaroori hai ke stack mein do operands available hain.

int evaluatePostfix(string exp) {

    stack<int> s;

    for (int i = 0; i < exp.length(); i++) {

        char ch = exp[i];

        if (ch >= '0' && ch <= '9') {
            s.push(ch - '0');
        }

        else {

            if (s.size() < 2) {
                cout << "Invalid Expression";
                return -1;
            }

            int b = s.top();
            s.pop();

            int a = s.top();
            s.pop();

            if (ch == '+') s.push(a + b);
            else if (ch == '-') s.push(a - b);
            else if (ch == '*') s.push(a * b);
            else if (ch == '/') {
                if (b == 0) {
                    cout << "Division by zero";
                    return -1;
                }
                s.push(a / b);
            }
            else {
                cout << "Invalid operator";
                return -1;
            }
        }
    }

    if (s.size() != 1) {
        cout << "Invalid Expression";
        return -1;
    }

    return s.top();
}

Important: b pehle pop hota hai aur a baad mein. Calculation hamesha a operator b hoti hai. Example 82- ka answer 8-2 = 6 hai, 2-8 nahi.

7. Queue — Overflow, Underflow aur Circular Conditions

A. Linear queue ke important checks

bool isEmpty() {
    return front == -1;
}

bool isFull() {
    return rear == SIZE - 1;
}

Enqueue:

if (isFull()) {
    cout << "Queue Overflow";
    return;
}

if (front == -1)
    front = 0;

arr[++rear] = value;

Dequeue:

if (isEmpty()) {
    cout << "Queue Underflow";
    return -1;
}

int value = arr[front];

if (front == rear)
    front = rear = -1;
else
    front++;

return value;

B. Circular queue ke checks

bool isEmpty() {
    return count == 0;
}

bool isFull() {
    return count == SIZE;
}

Enqueue:

if (isFull()) {
    cout << "Queue Full";
    return;
}

rear = (rear + 1) % SIZE;
arr[rear] = value;
count++;

Dequeue:

if (isEmpty()) {
    cout << "Queue Empty";
    return -1;
}

int value = arr[front];

front = (front + 1) % SIZE;
count--;

return value;

Circular queue ka formula yaad rakho:

(rear + 1) % SIZE

Is se rear last index ke baad dobara 0 par aa jata hai.

8. Recursion — Base Case aur Invalid Input

Recursion mein sabse important safety condition base case hai. Base case nahi hoga toh function continuously call hota rahega.

A. Factorial with negative input check

int factorial(int n) {

    if (n < 0)
        return -1;

    if (n == 0 || n == 1)
        return 1;

    return n * factorial(n - 1);
}

B. Power with negative exponent check

int power(int x, int n) {

    if (n < 0)
        return -1;

    if (n == 0)
        return 1;

    return x * power(x, n - 1);
}

C. Recursive binary search with valid bounds

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);

    return binarySearch(arr, low, mid - 1, key);
}

Call:

int result = binarySearch(arr, 0, n - 1, key);

Array sorted hona zaroori hai.

9. Exam ke liye final safety checklist

Isko achi tarah yaad kar lena. Question mein jab bhi operation likho, ye checks sochna.

Topic

Kya check karna hai?

Array insertion

Full array? Valid position?

Array deletion

Valid index?

Linked list insertion

Position valid?

Linked list deletion

List empty? Node exists?

Doubly linked list

prev aur next dono update?

Circular linked list

Last node ka link head par?

Stack push

isFull()

Stack pop

isEmpty()

Queue enqueue

isFull()

Queue dequeue

isEmpty()

Infix conversion

Precedence + associativity

Postfix evaluation

2 operands available?

Recursion

Base case present?

Binary search

Array sorted?

Meri advice: Har code mein sabse pehle boundary conditions check karna seekho. Exam mein sirf operation likhna kaafi nahi hota; empty list, full array, invalid position aur special cases handle karna bhi marks dilata hai.

Ab tumhari template book mein basic operations ke saath ye important edge cases bhi cover ho gaye hain. ❤️

Download

PDF Word HTML

FAQ

What is the difference between linear queues and circular queues?

Linear queues can suffer from wasted space after multiple deletions, whereas circular queues reuse empty spaces by utilizing the modulo operator for indices.

How do you implement a stack using an array in C++?

An array stack uses a top variable initialized to -1. The push operation increments top and stores the value, while the pop operation retrieves and decrements top.

Why are boundary checks important in linked list operations?

Boundary checks prevent segmentation faults by ensuring that pointers do not access null addresses and that insertion or deletion positions are valid.

Test yourself

Flashcards

Click a card to see the answer.

Quiz

1. Which data structure operates on the Last In, First Out (LIFO) principle?
2. What is the time complexity of Merge Sort?
3. In a circular queue implemented with an array of size SIZE, what is the formula to calculate the next rear position?
4. Which pointer points to the previous node in a doubly linked list?
5. What is the base case condition usually required in recursive functions to prevent infinite loops?

Questions generated by AI from the document: check the answers against the text.