.png)
DSA Series : Chapter 7 Circular Queue (Array Implementation) (C Version)
1. Introduction
A Circular Queue is an improved structure over the Linear Queue. In a normal linear queue implemented using arrays, after several enqueue and dequeue operations, empty spaces are created at the beginning but cannot be reused — causing false overflow.
Circular Queue solves this problem by treating the array as a circle.
2. Why Circular Queue? (Motivation)
Even though spaces exist at the beginning, we cannot insert.
✔ Circular Queue Solution
The queue becomes circular:
0 → 1 → 2 → 3 → 4
↑ ↓
└─────────────────┘
Thus rear can wrap around and use earlier empty cells.
3. Representation in C
#define SIZE 5
struct CircularQueue {
int items[SIZE];
int front;
int rear;
};
Meaning of Members
-
items[SIZE] → fixed-size array storing queue elements
-
front → index of the first element
-
rear → index of the last inserted element
Initial Condition
front = -1;
rear = -1;
This represents an empty queue.
4. Important Conditions
Queue is Full
(front == 0 && rear == SIZE-1) OR (rear + 1 == front)
Queue is Empty
front == -1
5. Enqueue Algorithm (Insert Element)
-
Check full
-
If empty → set both
front = 0andrear = 0 -
Else →
rear = (rear + 1) % SIZE -
Insert element at
items[rear]
6. Dequeue Algorithm (Delete Element)
-
Check empty
-
Retrieve
items[front] -
If removing last element → reset to
front = rear = -1 -
Else
front = (front + 1) % SIZE
7. Complete C Program (Circular Queue Using Arrays)
#include <stdio.h>
#define SIZE 5
struct CircularQueue {
int items[SIZE];
int front;
int rear;
};
// Function to check if queue is full
int isFull(struct CircularQueue *q) {
return ((q->front == 0 && q->rear == SIZE - 1) ||
(q->rear + 1 == q->front));
}
// Function to check if queue is empty
int isEmpty(struct CircularQueue *q) {
return (q->front == -1);
}
// Enqueue operation
void enqueue(struct CircularQueue *q, int value) {
if (isFull(q)) {
printf("Queue is FULL! Cannot insert %d\n", value);
return;
}
if (q->front == -1) { // First element
q->front = 0;
q->rear = 0;
} else {
q->rear = (q->rear + 1) % SIZE;
}
q->items[q->rear] = value;
printf("Inserted %d\n", value);
}
// Dequeue operation
int dequeue(struct CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is EMPTY! Cannot dequeue\n");
return -1;
}
int value = q->items[q->front];
if (q->front == q->rear) { // Queue becomes empty
q->front = -1;
q->rear = -1;
} else {
q->front = (q->front + 1) % SIZE;
}
printf("Deleted %d\n", value);
return value;
}
// Display operation
void display(struct CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is EMPTY!\n");
return;
}
printf("Circular Queue: ");
int i = q->front;
while (1) {
printf("%d ", q->items[i]);
if (i == q->rear)
break;
i = (i + 1) % SIZE;
}
printf("\n");
}
// Driver code
int main() {
struct CircularQueue q;
q.front = -1;
q.rear = -1;
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
enqueue(&q, 50); // Full
display(&q);
dequeue(&q);
dequeue(&q);
display(&q);
enqueue(&q, 60);
enqueue(&q, 70);
display(&q);
return 0;
}
8. Dry Run (Step-by-Step Simulation)
Let’s insert: 10, 20, 30, 40
front = 0
rear = 3
Queue: 10 20 30 40
Delete two elements:
front = 2
rear = 3
Queue: 30 40
Insert 50, 60 (wrap-around begins):
front = 2
rear = 1 (wrapped)
Queue: 30 40 50 60
9. Time & Space Complexity
Time Complexity
| Operation | Complexity |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Display | O(n) |
Space Complexity
O(n)
(n = size of array)
ALSO CHECK
ALSO CHECK
Comments
Post a Comment