.png)
DSA Series – Topic: QUEUE (C Version)
This covers,
* Queue theory
* Array implementation
* Linked-list implementation
* Queue operations
* Queue advantages
* Applications
* Queue C programs
1. Introduction to Queue
A Queue is like a line of people waiting for a service.
-
The person who arrives first gets served first.
-
Insertions happen at the rear.
-
Deletions happen at the front.
Queue Basic Operations
| Operation | Meaning |
|---|---|
enqueue() |
Insert an element at the rear |
dequeue() |
Remove element from the front |
peek() / front() |
View first element |
isEmpty() |
Check if queue is empty |
isFull() |
Check if queue is full (array queue) |
2. Queue Representation Using Array
A queue using an array uses the following variables:
Structure
#define SIZE 100
struct Queue {
int items[SIZE];
int front;
int rear;
};
Member Explanation
-
items[]– stores queue elements. -
front– index of the first element. -
rear– index of last inserted element.
Initialization
q.front = -1;
q.rear = -1;
Condition Checks
// Queue is full
rear == SIZE - 1
// Queue is empty
front == -1 || front > rear
3. C Program – Queue Using Array
#include <stdio.h>
#define SIZE 5
struct Queue {
int items[SIZE];
int front, rear;
};
// Function to initialize queue
void init(struct Queue *q) {
q->front = -1;
q->rear = -1;
}
// Check if full
int isFull(struct Queue *q) {
return q->rear == SIZE - 1;
}
// Check if empty
int isEmpty(struct Queue *q) {
return q->front == -1 || q->front > q->rear;
}
void enqueue(struct Queue *q, int value) {
if (isFull(q)) {
printf("Queue is FULL.\n");
return;
}
if (q->front == -1) q->front = 0;
q->items[++q->rear] = value;
printf("%d inserted.\n", value);
}
void dequeue(struct Queue *q) {
if (isEmpty(q)) {
printf("Queue is EMPTY.\n");
return;
}
printf("%d removed.\n", q->items[q->front++]);
}
void display(struct Queue *q) {
if (isEmpty(q)) {
printf("Queue is EMPTY.\n");
return;
}
printf("Queue: ");
for (int i = q->front; i <= q->rear; i++)
printf("%d ", q->items[i]);
printf("\n");
}
int main() {
struct Queue q;
init(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
display(&q);
dequeue(&q);
display(&q);
return 0;
}
4. Queue Using Linked List
Unlike arrays, linked-list queues do not overflow unless memory is full.
Structure
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node *front, *rear;
};
Member Explanation
-
front→ Points to first node (dequeue from here) -
rear→ Points to last node (enqueue here)
Detailed Explanation of the Code
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node *front, *rear;
};
1. What is a Node?
In any linked list–based data structure, a Node is the fundamental building block.
Meaning of struct Node
struct Node {
int data;
struct Node* next;
};
Breakdown
| Line | Explanation |
|---|---|
struct Node { |
Declares a new user-defined data type named Node. |
int data; |
This stores the actual value for the queue (e.g., 10, 20, 30). This is the payload. |
struct Node* next; |
This is a pointer to the next node in the queue. It creates the linked structure. |
}; |
End of the structure definition. |
Key Concept
A Node stores:
✔ A value
✔ A pointer to the next Node
Visualization
+---------+-------------------+
| data | next → |
+---------+-------------------+
A queue is just a chain of these nodes linked together.
2. Why use struct Node* next?
Because a queue implemented using linked list should not use a fixed size.
The next pointer helps chain nodes dynamically using memory allocation (malloc).
This makes the queue:
-
Dynamic in size
-
Efficient in insertion at rear
-
Efficient in deletion at front
3. Queue Structure
Now the queue is represented using:
struct Queue {
struct Node *front, *rear;
};
Breakdown
| Member | Type | Meaning |
|---|---|---|
front |
struct Node* |
Points to the first element of the queue (the one to be dequeued next). |
rear |
struct Node* |
Points to the last element of the queue (where new elements get inserted). |
Purpose of Queue Structure
This structure holds two pointers that define the entire queue.
Why are two pointers required?
Because in a queue:
-
Deletion happens from front
-
Insertion happens at rear
For efficient O(1) operations, we maintain both pointers.
If we kept only front, then insertion at rear would require traversing the whole queue every time → O(n)
Using both makes it O(1).
4. How Queue Nodes Are Connected
Imagine the queue contains:
10 → 20 → 30
front points to 10
rear points to 30
Visual representation:
front
↓
+------+ +------+ +------+
| 10 | → | 20 | → | 30 |
+------+ +------+ +------+
↑
rear
The queue uses a linked list internally:
-
Each node points to the next node.
-
rear->nextis always NULL because no element exists after it.
5. How It Works During Operations
✔ When Queue is EMPTY
Before inserting any node:
front = NULL
rear = NULL
Visualization:
front → NULL
rear → NULL
✔ During ENQUEUE (Insertion)
Example: Insert 10
-
Create a new node
-
If queue is empty → both front and rear point to this node
front → [10 | NULL] ← rear
Next insert 20:
front
↓
[10 | next ] → [20 | NULL]
↑
rear
Explanation:
-
rear->next = newNode -
rear = newNode
✔ During DEQUEUE (Deletion)
Remove element at front.
If queue = 10 → 20 → 30
Removing 10:
front moves to the next node
front → 20
When last element removed:
front = NULL
rear = NULL
Why this design is perfect for Queue?
Because:
-
No shifting of elements (unlike arrays)
-
No overflow unless memory full
-
Constant time insert/delete
-
Dynamic memory allocation using nodes
Summary in Simple Terms
Node
-
Holds data and pointer to next node.
Queue
-
Holds pointers to first and last nodes.
front
-
Where elements are removed.
rear
-
Where elements are added.
This structure guarantees fast, dynamic queue operations — perfect for BFS, scheduling, OS tasks, and more.
5. C Program – Queue Using Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node *front, *rear;
};
void init(struct Queue *q) {
q->front = q->rear = NULL;
}
void enqueue(struct Queue *q, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
printf("%d inserted.\n", value);
return;
}
q->rear->next = newNode;
q->rear = newNode;
printf("%d inserted.\n", value);
}
void dequeue(struct Queue *q) {
if (q->front == NULL) {
printf("Queue EMPTY.\n");
return;
}
struct Node* temp = q->front;
printf("%d removed.\n", temp->data);
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
free(temp);
}
void display(struct Queue *q) {
if (q->front == NULL) {
printf("Queue EMPTY.\n");
return;
}
struct Node* temp = q->front;
printf("Queue: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
struct Queue q;
init(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
display(&q);
dequeue(&q);
display(&q);
return 0;
}
6. Applications of Queue
Real-life & system applications
-
CPU scheduling (Round Robin)
-
Disk scheduling
-
Network packet buffering
-
Printers queue
-
Call center systems
-
Breadth-First Search (BFS)
-
OS interrupt handling
-
Resource allocation in distributed systems
ALSO CHECK
ALSO CHECK
Comments
Post a Comment