Queue
Lecture Note: Queue
Definition:
A Queue is a linear data structure that follows the First In First Out (FIFO) principle.
This means the element inserted first will be removed first.
Characteristics:
Property Description
Linear Structure Elements arranged in a sequence
FIFO Order First element added = First removed
Two Ends Insertion (rear), Deletion (front)
Operations enqueue(), dequeue()
Real-life Examples:
• Waiting line at a ticket counter
• CPU scheduling in Operating System
• Print queue in printer
• Call center service system
Applications:
• CPU & disk scheduling
• Data buffering
• Breadth-First Search (BFS)
• Handling requests in web servers
Basic Queue Operations
Operation Description
enqueue() Insert element at rear
dequeue() Remove element from front
peek() View front element without removing
isEmpty() Check if queue is empty
isFull() Check if queue is full (array-based)
Queue Implementation Types
1. Using Array
2. Using Linked List
3. Circular Queue
4. Double-Ended Queue (Deque)
5. Priority Queue
Queue Operations Using Array
Algorithm: Enqueue (Insertion)
1. If rear == SIZE - 1
Queue is Full (Overflow)
2. Else
rear = rear + 1
queue[rear] = value
Algorithm: Dequeue (Deletion)
1. If front > rear
Queue is Empty (Underflow)
2. Else
value = queue[front]
front = front + 1
C Code: Queue Using Array
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = 0, rear = -1;
// Enqueue
void enqueue(int value) {
if (rear == SIZE - 1) {
printf("Queue Overflow\n");
} else {
rear++;
queue[rear] = value;
printf("%d inserted\n", value);
// Dequeue
void dequeue() {
if (front > rear) {
printf("Queue Underflow\n");
} else {
printf("%d removed\n", queue[front]);
front++;
// Peek
void peek() {
if (front > rear) {
printf("Queue is empty\n");
} else {
printf("Front element: %d\n", queue[front]);
// Display
void display() {
if (front > rear) {
printf("Queue is empty\n");
} else {
printf("Queue elements: ");
for (int i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
peek();
dequeue();
display();
return 0;
Queue Using Linked List (Summary)
struct Node {
int data;
struct Node* next;
};
struct Node* front = NULL;
struct Node* rear = NULL;
Enqueue: Create new node → rear->next = new node → rear = new node
Dequeue: temp = front → front = front->next → free(temp)
Lecture Note: Circular Queue
What is a Circular Queue?
A Circular Queue is a linear data structure that uses an array in a circular manner to overcome
the limitation of the regular (linear) queue.
In a linear queue, after some dequeue() operations, the front moves forward and unused space
is wasted at the beginning.
A circular queue solves this by wrapping around when the end of the array is reached.
Key Concept:
In a circular queue:
• Last position is connected back to the first position.
• Positions are updated using the formula:
(position + 1) % size
Advantages Over Linear Queue:
Feature Linear Queue Circular Queue
Space utilization Poor (unused front) Efficient (wrap-around)
Overflow Even when space exists Only when truly full
Implementation Simpler Slightly more complex
Operations in Circular Queue:
Operation Description
enqueue() Add an element at the rear
dequeue() Remove an element from the front
peek() View the front element
Operation Description
isFull() Check if the queue is full
isEmpty() Check if the queue is empty
Conditions in Circular Queue
• Full: (rear + 1) % SIZE == front
• Empty: front == -1
Algorithm (Circular Queue Using Array)
Enqueue:
1. Check if (rear + 1) % SIZE == front
→ Queue is full (Overflow)
2. If empty (front == -1)
→ front = rear = 0
Else
→ rear = (rear + 1) % SIZE
3. Insert element at queue[rear]
Dequeue:
1. Check if front == -1
→ Queue is empty (Underflow)
2. Store value at queue[front]
3. If front == rear
→ Only one element; set front = rear = -1
Else
→ front = (front + 1) % SIZE
C Code: Circular Queue Using Array
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
int isFull() {
return ((rear + 1) % SIZE == front);
int isEmpty() {
return (front == -1);
void enqueue(int value) {
if (isFull()) {
printf("Queue Overflow\n");
return;
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % SIZE;
}
queue[rear] = value;
printf("%d inserted\n", value);
void dequeue() {
if (isEmpty()) {
printf("Queue Underflow\n");
return;
printf("%d removed\n", queue[front]);
if (front == rear) {
// Only one element was present
front = rear = -1;
} else {
front = (front + 1) % SIZE;
void display() {
if (isEmpty()) {
printf("Queue is empty\n");
return;
printf("Queue elements: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
printf("\n");
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Should show overflow
display();
dequeue();
dequeue();
display();
enqueue(60);
enqueue(70); // Should be accepted now
display();
return 0;
Sample Output:
10 inserted
20 inserted
30 inserted
40 inserted
Queue Overflow
Queue elements: 10 20 30 40
10 removed
20 removed
Queue elements: 30 40
60 inserted
70 inserted
Queue elements: 30 40 60 70