Unit 2: Queues

Question 1

Queue ADT

Answer 1

Definition: A queue is a linear data structure that follows the First In First Out (FIFO) principle.
Basic Operations:

Enqueue: Add an item to the end.
Dequeue: Remove an item from the front.
Front/Peek: View the front item without removing it.

Question 2

Array Implementation of Queue

Answer 2

define MAX 100

Structure:

c

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

Question 3

Types of Queues

Answer 3

Simple Queue: Basic FIFO structure.
Circular Queue: Connects the end of the queue back to the front.
Deque (Double-Ended Queue): Allows insertion and deletion at both ends.
Priority Queue: Elements are processed based on priority rather than order.

Question 3

Queue Operations in C

Answer 3

Enqueue Function:

c

void enqueue(Queue *q, int value) {
if (q->rear == MAX - 1) {
printf(“Queue Overflow\n”);
return;
}
q->arr[++q->rear] = value;
}

Dequeue Function:

c

int dequeue(Queue *q) {
if (q->front > q->rear) {
printf(“Queue Underflow\n”);
return -1;
}
return q->arr[q->front++];
}

Question 4

Circular Queue Implementation

Answer 4

Structure:

c

typedef struct {
int front;
int rear;
int arr[MAX];
} CircularQueue;

Enqueue Function:

c

void enqueue(CircularQueue *q, int value) {
if ((q->rear + 1) % MAX == q->front) {
printf(“Queue Overflow\n”);
return;
}
q->rear = (q->rear + 1) % MAX;
q->arr[q->rear] = value;
}

Question 5

Singly Linked List Structure

Answer 5

Structure:

c

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

Question 6

Linked Lists

Answer 6

Definition: A linked list is a linear data structure where each element is a separate object, with each element (node) containing a data part and a reference (link) to the next node.
Types:

Singly Linked List: Each node points to the next node.
Doubly Linked List: Each node points to both the next and previous nodes.
Circular Linked List: The last node points back to the first node.

Question 7

Insertion in Singly Linked List

Answer 7

Insertion at Beginning:
void insertAtBeginning(Node **head, int newData) {
Node newNode = (Node)malloc(sizeof(Node));
newNode->data = newData;
newNode->next = *head;
*head = newNode;
}

Insertion at End:
void insertAtEnd(Node head, int newData) {
Node *newNode = (Node)malloc(sizeof(Node));
newNode->data = newData;
newNode->next = NULL;
if (head == NULL) {
*head = newNode;
return;
}
Node *last = *head;
while (last->next != NULL) {
last = last->next;
}
last->next = newNode;
}

Question 8

Doubly Linked List Structure

Answer 8

Structure:

c

typedef struct DNode {
int data;
struct DNode *next;
struct DNode *prev;
} DNode;

Question 8

Deletion in Singly Linked List

Answer 8

Deletion at Beginning:
void deleteAtBeginning(Node **head) {
if (*head == NULL) return;
Node *temp = *head;
head = (head)->next;
free(temp);
}

Deletion at End:
void deleteAtEnd(Node head) {
if (head == NULL) return;
if ((head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
Node *secondLast = *head;
while (secondLast->next->next != NULL) {
secondLast = secondLast->next;
}
free(secondLast->next);
secondLast->next = NULL;
}

Question 9

Doubly Linked List Insertion

Answer 9

Insertion at Beginning:

c

void insertDAtBeginning(DNode head, int newData) {
DNode *newNode = (DNode)malloc(sizeof(DNode));
newNode->data = newData;
newNode->next = head;
newNode->prev = NULL;
if (head != NULL) (head)->prev = newNode;
*head = newNode;
}

Insertion at End:

c

void insertDAtEnd(DNode head, int newData) {
DNode *newNode = (DNode)malloc(sizeof(DNode));
newNode->data = newData;
newNode->next = NULL;
if (head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
DNode *last = *head;
while (last->next != NULL) last = last->next;
last->next = newNode;
newNode->prev = last;
}

Question 10

Circular Linked List

Answer 10

Definition: A circular linked list is a linked list where all nodes are connected in a circle, with the last node pointing back to the first node.
Structure:

c

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

Question 11

Linked List Applications

Answer 11

Applications:

Dynamic Memory Allocation: Can grow and shrink as needed.
Implementing Stacks and Queues: Using linked lists.
Polynomial Arithmetic: Storing polynomial terms.

Question 12

Hashing

Answer 12

Definition: Hashing is the process of mapping data to a fixed-size table using a hash function.
Hash Function: A function that takes an input and produces a fixed-size string of characters.

Question 13

Hash Table

Answer 13

Structure: A hash table stores key-value pairs, allowing for efficient data retrieval.
Collision Resolution: Techniques to handle situations when two keys hash to the same index.

Chaining: Each table index points to a linked list.
Open Addressing: Find the next available slot.

Question 14

Hash Function Example

Answer 14

Simple Hash Function:

c

int hash(int key) {
return key % TABLE_SIZE;
}

Question 15

Collision Resolution by Chaining

Answer 15

typedef struct HashNode {
int key;
int value;
struct HashNode *next;
} HashNode;

typedef struct HashTable {
HashNode **table;
} HashTable;

Question 16

Search Function in Hash Table

Answer 16

Chaining Method:
int search(HashTable *ht, int key) {
int index = hash(key);
HashNode *node = ht->table[index];
while (node) {
if (node->key == key) {
return node->value;
}
node = node->next;
}
return -1; // Not found
}

Question 17

Deletion in Hash Table

Answer 17

Chaining Method:
void delete(HashTable *ht, int key) {
int index = hash(key);
HashNode *node = ht->table[index];
HashNode *prev = NULL;

while (node) {
    if (node->key == key) {
        if (prev) {
            prev->next = node->next;
        } else {
            ht->table[index] = node->next;
        }
        free(node);
        return;
    }
    prev = node;
    node = node->next;
} }