A queue in data structures is a linear data structure that follows the First In First Out (FIFO) principle. This means that the element inserted first is the one that gets removed first. Imagine a line of people at a ticket counter: the first person to arrive is the first to get served. This behavior is exactly how a queue operates in data structures. Queues are widely used in operating systems for task scheduling, in printers where documents are lined up, and in network traffic handling. Understanding queues is essential for students studying B.Tech Data Structures Notes 2025 or pursuing Unit 2 Notes Data Structures as a part of their curriculum.
Characteristics of Queue
A queue has the following important characteristics:
- FIFO Order: Elements are inserted at the rear and deleted from the front.
- Linear Structure: It stores data in a sequential manner.
- Two Pointers: Typically involves two pointers — front and rear — to keep track of the insertion and deletion positions.
- Dynamic or Static Implementation: Can be implemented using arrays (static) or linked lists (dynamic).
Basic Operations on Queue
The fundamental operations that can be performed on a queue are:
- Enqueue: Inserting an element at the rear of the queue.
- Dequeue: Removing an element from the front of the queue.
- Peek/Front: Getting the element at the front without removing it.
- IsFull: Checking if the queue is full (only applicable to static queues).
- IsEmpty: Checking if the queue is empty.
Types of Queues
There are several types of queues, each with unique behavior and use cases. These are crucial for any student referring to Engineering Study Material for Data Structures:
1. Simple Queue (Linear Queue): The simplest form where insertion is done at the rear and deletion at the front. The major disadvantage is that space is wasted when elements are dequeued but the array still has unused space at the beginning.
2. Circular Queue: In this type, the last position is connected back to the first position to make a circle. It resolves the problem of unused space in simple queues. Insert diagram here to illustrate Circular Queue wrap-around.
3. Priority Queue: Elements are inserted based on priority. Higher-priority elements are dequeued before lower-priority ones, regardless of their insertion time.
4. Double-Ended Queue (Deque): In this structure, insertion and deletion can take place from both ends — front and rear.
Queue Implementation Using Array
In an array-based implementation, a queue is represented using an array with two indices: front and rear. Initially, both are set to -1. The insertion is done by incrementing rear and adding an element there, while deletion is done by incrementing front. One major drawback is the inefficient use of space — once the rear reaches the end, no further elements can be added even if there is space at the beginning.
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if (rear == SIZE - 1)
printf("Queue is Full");
else {
if (front == -1) front = 0;
rear++;
queue[rear] = value;
}
}
void dequeue() {
if (front == -1 || front > rear)
printf("Queue is Empty");
else
front++;
}Queue Implementation Using Linked List
To overcome the limitations of static queues, dynamic implementation using linked lists is preferred. Each node contains data and a pointer to the next node.
struct Node {
int data;
struct Node* next;
};
struct Node *front = NULL, *rear = NULL;
void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
void dequeue() {
if (front == NULL) {
printf("Queue is Empty");
return;
}
struct Node* temp = front;
front = front->next;
if (front == NULL) rear = NULL;
free(temp);
}Applications of Queue
Queues have broad applications across various domains:
- Operating Systems: Used in job scheduling and managing processes in multitasking.
- Networking: Packet routing and traffic management use queues.
- CPU Task Scheduling: Maintains the order of execution.
- Data Stream Management: Useful for managing real-time data streams.
- Breadth-First Search (BFS): Essential in graph algorithms.
Comparison: Queue vs Stack
| Feature | Queue | Stack |
|---|---|---|
| Principle | FIFO | LIFO |
| Insertion | Rear | Top |
| Deletion | Front | Top |
| Real-life Example | Line at a bank | Stack of books |
| Application | Task Scheduling, BFS | Undo Operations, DFS |
Circular Queue in Detail
A circular queue is a more efficient form of a linear queue. Once the rear reaches the end of the array, it wraps around to the beginning, if space is available. This prevents wastage of space and optimizes the use of the array. Insert diagram here showing the wrap-around of Circular Queue.
Priority Queue in Detail
In a priority queue, each element is associated with a priority. Elements with higher priority are dequeued first. If two elements have the same priority, they are served based on FIFO order. There are multiple ways to implement a priority queue:
- Using array with sorting after every insertion
- Using heap (min-heap or max-heap)
- Using linked list with ordered insertion
Deque (Double Ended Queue)
In Deque, elements can be inserted and removed from both front and rear ends. There are two types of deques:
- Input-restricted deque: Insertion at one end only.
- Output-restricted deque: Deletion at one end only. This structure is useful in complex scheduling algorithms and palindrome checking.
Short Answer Questions (2-3 Marks)
Q1: What is a queue in data structures? A queue is a linear data structure that follows the FIFO principle, where elements are inserted at the rear and removed from the front.
Q2: Differentiate between stack and queue. A stack follows LIFO (Last In First Out), while a queue follows FIFO (First In First Out).
Q3: Mention two applications of queues. Queues are used in CPU scheduling and BFS traversal of graphs.
Q4: Define circular queue. A circular queue connects the last position back to the first to form a circle, optimizing space usage.
Q5: What is dequeue operation? It is the removal of an element from the front of the queue.
Long Answer Questions (5-10 Marks)
Q1: Explain different types of queues with examples. There are four main types: Simple Queue, Circular Queue, Priority Queue, and Deque. A simple queue allows insertion at the rear and deletion at the front. Circular Queue overcomes the limitation of unused spaces. Priority Queue manages elements based on their priority. Deque allows insertion and deletion from both ends.
Q2: Implement a queue using linked list and explain its operations. (Refer to code above under Linked List Implementation). We define a node structure with data and a pointer. Enqueue adds a node at the rear, while dequeue removes from the front. If the queue becomes empty, both pointers are set to NULL.
Q3: Compare and contrast stack and queue. Both are linear structures but differ in data access methodology. A stack is LIFO where the last element is removed first, whereas a queue is FIFO. Stacks are used in function calls and expression evaluations; queues are used in task management and data streaming.
Q4: Write the algorithm for enqueue and dequeue operations in a circular queue.
- Enqueue: Check if the queue is full using
(rear + 1) % SIZE == front. If not, update rear as(rear + 1) % SIZEand insert. - Dequeue: Check if the queue is empty using
front == -1. If not, update front as(front + 1) % SIZE.
Chapter Summary
Queue is a linear data structure based on FIFO principle Basic operations include enqueue, dequeue, and peek Types include simple, circular, priority queue, and deque Circular queue avoids space wastage found in linear queues Priority queues serve elements based on priority rather than insertion order Deques allow insertion and deletion at both ends Static implementation uses arrays, while dynamic uses linked lists Queues are used in scheduling, routing, and graph algorithms Efficient implementations prevent overflow and underflow conditions Comparison with stacks highlights difference in access methodology
Model Questions / Sample Internal Exam Questions
- Define Queue and explain its types with examples.
- Write a program to implement queue using array.
- Differentiate between Circular Queue and Priority Queue.
- Explain the advantages of using a linked list for queue implementation.
- Describe real-world applications where queues are used.
- Write algorithms for insertion and deletion in a deque.
- Compare Queue and Stack with respect to memory usage and time complexity.
- Discuss the use of Queue in Breadth-First Search traversal.
