Queue is one of the most important linear data structures used in computer science and software development. It follows a specific rule called First In First Out (FIFO). According to this principle, the element inserted first into the queue is removed first.
Queues are widely used in operating systems, process scheduling, printer management, network communication, CPU scheduling, resource allocation, and many real-world applications. Understanding queues is essential for mastering Data Structures and Algorithms.
Unlike stacks that follow the Last In First Out (LIFO) principle, queues work exactly like waiting lines in daily life where the person who arrives first gets served first.
A Queue is a linear data structure in which insertion takes place at one end called the REAR and deletion takes place at another end called the FRONT.
Because insertion and deletion occur at opposite ends, queues maintain the First In First Out order.
A Queue is a linear data structure that follows the FIFO (First In First Out) principle where insertion is performed from the rear end and deletion is performed from the front end.
People standing in a ticket line are served in the same order in which they arrive.
The customer who joins the queue first gets service before others.
Print jobs are processed according to the order in which they are received.
Calls are generally handled according to arrival order.
Many applications require tasks to be processed in the same sequence in which they arrive. Queue provides an efficient solution for such situations.
FIFO stands for First In First Out. The first element inserted into the queue becomes the first element removed.
Enqueue(10) Enqueue(20) Enqueue(30) Enqueue(40) FRONT → 10 20 30 40 ← REAR
If a dequeue operation is performed, 10 will be removed first because it entered the queue before all other elements.
| Term | Description |
|---|---|
| Queue | Linear data structure following FIFO. |
| Front | Position from where deletion occurs. |
| Rear | Position where insertion occurs. |
| Enqueue | Insertion operation. |
| Dequeue | Deletion operation. |
| Overflow | Queue is full. |
| Underflow | Queue is empty. |
Enqueue is used to insert an element at the rear of the queue.
Dequeue removes an element from the front of the queue.
Peek displays the front element without removing it.
Checks whether the queue contains elements or not.
Checks whether the queue has reached maximum capacity.
The standard queue implementation that follows FIFO order.
The last position connects back to the first position, improving memory utilization.
Elements are processed according to priority instead of arrival order.
Insertion and deletion can occur from both ends.
A Queue is a linear data structure that follows FIFO order.
First In First Out means the first inserted element is removed first.
Enqueue, Dequeue, Peek, IsEmpty and IsFull.
Stack follows LIFO whereas Queue follows FIFO.
A queue where the last position is connected back to the first position.
One of the most common methods of implementing a queue is by using an array. In this approach, elements are stored in contiguous memory locations, and two variables called FRONT and REAR are used to manage the queue.
The FRONT pointer indicates the position of the first element, while the REAR pointer indicates the position of the last element.
#define MAX 100 int queue[MAX]; int front = -1; int rear = -1;
Initially, both FRONT and REAR are set to -1, indicating that the queue is empty.
The enqueue operation inserts a new element at the rear end of the queue.
Step 1: Check if queue is full. Step 2: If full, display Overflow. Step 3: If queue is empty, set FRONT = 0. Step 4: Increment REAR. Step 5: Insert element at REAR.
Enqueue(10) FRONT → 10 ← REAR
Enqueue(20) FRONT → 10 20 ← REAR
Every new element is inserted from the rear side.
The dequeue operation removes an element from the front of the queue.
Step 1: Check if queue is empty. Step 2: If empty, display Underflow. Step 3: Remove FRONT element. Step 4: Increment FRONT.
Before Dequeue FRONT → 10 20 30 40 ← REAR
After removing 10:
FRONT → 20 30 40 ← REAR
Since queues follow FIFO, the oldest element is always removed first.
Queue Overflow occurs when an insertion operation is attempted on a completely full queue.
Maximum Size = 5 Queue: 10 20 30 40 50 Enqueue(60) Result: Queue Overflow
Overflow indicates that no additional element can be inserted until space becomes available.
Queue Underflow occurs when a deletion operation is performed on an empty queue.
Queue Empty Dequeue() Result: Queue Underflow
Underflow indicates that there is no element available for removal.
Although simple queues are easy to implement, they have certain limitations.
To solve these problems, Circular Queue was introduced.
A Circular Queue is an advanced form of queue in which the last position is connected back to the first position. This structure allows efficient utilization of memory.
Instead of treating the queue as a straight line, the positions are arranged in a circular manner.
1 → 2 → 3 → 4 → 5 ↑ ↓ └─────────────┘
When the REAR reaches the last position, it can move back to the first available position.
A Priority Queue is a special type of queue where each element is assigned a priority value. Elements with higher priority are processed before lower-priority elements.
Unlike simple queues, processing order depends on priority rather than arrival time.
| Process | Priority |
|---|---|
| P1 | 3 |
| P2 | 1 |
| P3 | 5 |
P3 will be processed first because it has the highest priority.
Deque stands for Double Ended Queue. It is a special queue where insertion and deletion can occur from both ends.
It combines the features of both stacks and queues.
Insertion is allowed only from one end, while deletion can occur from both ends.
Deletion is allowed only from one end, while insertion can occur from both ends.
Queues can also be implemented using linked lists. This method allows dynamic memory allocation and removes the fixed-size limitation of arrays.
Each node contains data and a pointer to the next node.
struct Node
{
int data;
struct Node *next;
};
The FRONT points to the first node, and REAR points to the last node.
| Operation | Time Complexity |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| IsEmpty | O(1) |
| IsFull | O(1) |
Most queue operations require constant time because only the front and rear positions are accessed.
| Queue | Stack |
|---|---|
| FIFO | LIFO |
| Front and Rear | Top |
| Deletion from Front | Deletion from Top |
| Insertion at Rear | Insertion at Top |
| Used in Scheduling | Used in Recursion |
Queues are one of the most widely used data structures in modern computing systems. They help manage tasks, processes, requests, and resources in an organized manner. Because queues follow the FIFO principle, they ensure fairness and maintain the correct order of execution.
Many operating systems, web applications, databases, networking devices, and software applications use queues internally to handle large amounts of data efficiently.
In a multitasking operating system, multiple processes compete for CPU time. The operating system uses queues to manage these processes and decide which process should execute next.
When a process enters the ready state, it is placed in the ready queue. The scheduler selects processes from the queue according to the scheduling algorithm being used.
Ready Queue P1 → P2 → P3 → P4
The CPU executes P1 first because it entered the queue before the other processes.
Printer spooling is one of the most common real-world applications of queues. When multiple users send print requests simultaneously, the printer cannot print all documents at the same time.
Instead, print jobs are stored in a queue and processed one by one according to their arrival order.
Print Queue Document A Document B Document C Document D
The printer prints Document A first and then proceeds to the next documents.
Computer networks continuously transfer data packets between devices. Routers and switches receive thousands of packets every second.
These packets are temporarily stored in queues before they are processed and forwarded to their destinations.
Without queues, network devices would not be able to handle heavy traffic efficiently.
When multiple users access a website simultaneously, requests arrive faster than they can be processed.
Web servers use queues to manage incoming requests and process them in an organized manner.
This helps maintain system stability and ensures that requests are handled fairly.
Customer support systems use queues to manage incoming calls. When all representatives are busy, new callers are placed in a waiting queue.
Calls are connected according to their arrival order, ensuring fairness among customers.
Banks use queue-based systems to manage customers waiting for services. Token systems commonly used in banks are practical examples of queue implementation.
The customer receiving the first token gets served before customers with later token numbers.
Popular ticket booking platforms use queues when a large number of users attempt to book tickets simultaneously.
The system places users in a virtual queue and processes requests one at a time.
This prevents server overload and ensures fair access to available tickets.
Modern applications often use message queues to exchange information between different services.
For example, an e-commerce website may use queues for:
Message queues improve performance and reliability in distributed systems.
Breadth First Search (BFS) is an important graph traversal algorithm that uses a queue.
The algorithm explores all neighboring vertices before moving to the next level.
A
/ \
B C
/ \ \
D E F
BFS Traversal:
A → B → C → D → E → F
A queue stores vertices that need to be explored next.
Step 1: Insert starting node into queue. Step 2: Remove node from front. Step 3: Visit node. Step 4: Insert unvisited neighbors. Step 5: Repeat until queue becomes empty.
This algorithm guarantees level-by-level traversal of a graph.
Many software applications execute tasks in the background. Queues help organize these tasks efficiently.
Examples include:
Tasks are placed in a queue and executed according to their order.
Operating systems use multiple queues internally for process management.
Stores processes waiting for CPU allocation.
Stores processes waiting for I/O operations.
Stores requests for hardware devices.
These queues help operating systems manage resources effectively.
A Queue is a linear data structure that follows the FIFO principle where insertion occurs at the rear and deletion occurs at the front.
FIFO stands for First In First Out.
Enqueue, Dequeue, Peek, IsEmpty, and IsFull.
Enqueue is the operation used to insert an element into the queue.
Dequeue is the operation used to remove an element from the queue.
Queue Overflow occurs when insertion is attempted on a full queue.
Queue Underflow occurs when deletion is attempted on an empty queue.
A Circular Queue connects the last position back to the first position for efficient memory usage.
A Priority Queue processes elements according to priority instead of arrival order.
Deque is a Double Ended Queue where insertion and deletion can occur from both ends.
O(1)
O(1)
Breadth First Search (BFS).
Round Robin Scheduling uses Circular Queue.
Queue follows FIFO, whereas Stack follows LIFO.
Queue is one of the most important linear data structures in computer science. It follows the FIFO principle and is extensively used in operating systems, networking, web servers, process scheduling, BFS traversal, printer management, and many other real-world applications. Understanding queue operations, implementations, types, complexities, and practical uses is essential for mastering Data Structures and Algorithms and for performing well in technical interviews and university examinations.
Introduction to Data Structure | Array | One-Dimensional Array | Two-Dimensional Array | Linked List | Stack | Tree Data Structure | Graph Data Structure | Searching Techniques | Sorting Techniques | Hashing | File Structure