Queue is one of the most important linear data structures in computer science. It follows the First In First Out (FIFO) principle, which means that the element inserted first is removed first. In a standard queue, insertion takes place at the REAR and deletion takes place at the FRONT.
Queues are useful whenever multiple tasks, requests or data items need to be processed in an organized sequence. They are commonly used in operating systems, process scheduling, printer spooling, networking, web servers, task scheduling and graph traversal.
A queue is different from a stack because a stack follows LIFO, whereas a queue normally follows FIFO. This difference determines how elements enter and leave the data structure.
A Queue is a linear data structure in which insertion and deletion are performed at opposite ends. New elements are inserted at the rear, while elements are removed from the front.
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.
FIFO stands for First In First Out. It means that the element which enters the queue first gets the opportunity to leave first.
Enqueue(10) Enqueue(20) Enqueue(30) Enqueue(40) FRONT → 10 20 30 40 ← REAR
If a dequeue operation is performed, 10 is removed first because it was inserted before the other elements.
| Term | Description |
|---|---|
| Queue | A linear data structure that normally follows FIFO. |
| Front | Position from where deletion takes place. |
| Rear | Position where insertion takes place. |
| Enqueue | Operation used to insert an element. |
| Dequeue | Operation used to remove an element. |
| Peek | Operation used to view the front element without removing it. |
| Overflow | Condition that occurs when insertion is attempted on a full bounded queue. |
| Underflow | Condition that occurs when deletion is attempted on an empty queue. |
Many computer systems receive tasks or requests faster than they can process them immediately. A queue provides temporary storage and preserves the required processing order.
The main operations of a standard queue are used to insert, remove and inspect elements.
| Operation | Purpose |
|---|---|
| Enqueue | Inserts an element at the rear. |
| Dequeue | Removes an element from the front. |
| Peek | Returns or displays the front element without removing it. |
| IsEmpty | Checks whether the queue contains no elements. |
| IsFull | Checks whether a bounded array queue has reached its capacity. |
The Enqueue operation inserts a new element at the rear of the queue. In a standard FIFO queue, the new element becomes the newest item and remains behind the elements that were already waiting.
Before Enqueue FRONT → 10 20 30 ← REAR Enqueue(40) After Enqueue FRONT → 10 20 30 40 ← REAR
The Dequeue operation removes the element at the front of the queue. Therefore, the oldest element is removed first.
Before Dequeue FRONT → 10 20 30 40 ← REAR Dequeue() After Dequeue FRONT → 20 30 40 ← REAR
Removed Element = 10
The Peek operation returns or displays the front element without removing it. It is useful when a program needs to inspect the next element to be processed.
FRONT → 20 30 40 ← REAR Peek() Output = 20
Different queue structures are designed for different processing requirements. The commonly studied types are Simple Queue, Circular Queue, Priority Queue and Deque.
A Simple Queue is the basic FIFO queue. Elements are inserted at the rear and removed from the front.
A Circular Queue treats the last position as connected to the first position. This allows previously unused positions to be reused when space is available.
A Priority Queue processes elements according to their priority rather than strictly according to their arrival time.
A Deque, or Double Ended Queue, allows insertion and deletion at both ends.
A queue can be implemented using an array when a maximum capacity is known. Two variables, FRONT and REAR, are used to identify the positions needed for deletion and insertion.
#define MAX 100 int queue[MAX]; int front = -1; int rear = -1;
Initially, both FRONT and REAR are set to -1 to indicate that the queue is empty.
The array-based enqueue operation first checks whether the queue has reached its capacity. If space is available, the rear position is advanced and the new value is stored there.
Step 1: Check whether the queue is full. Step 2: If full, report Queue Overflow. Step 3: If the queue is empty, set FRONT = 0. Step 4: Increment REAR. Step 5: Insert the element at queue[REAR].
void enqueue(int value)
{
if (rear == MAX - 1)
{
printf("Queue Overflow");
}
else
{
if (front == -1)
front = 0;
rear++;
queue[rear] = value;
}
}
The array-based dequeue operation removes the element at FRONT and then advances FRONT to the next position.
Step 1: Check whether the queue is empty. Step 2: If empty, report Queue Underflow. Step 3: Store or remove queue[FRONT]. Step 4: Increment FRONT. Step 5: Reset FRONT and REAR when the queue becomes empty.
int dequeue()
{
int value;
if (front == -1 || front > rear)
{
printf("Queue Underflow");
return -1;
}
value = queue[front++];
if (front > rear)
{
front = -1;
rear = -1;
}
return value;
}
Queue Overflow occurs when an insertion operation is attempted on a bounded queue that has no available capacity.
Maximum Size = 5 Queue: 10 20 30 40 50 Enqueue(60) Result: Queue Overflow
Queue Underflow occurs when a deletion operation is attempted while the queue is empty.
Queue Empty Dequeue() Result: Queue Underflow
A simple array queue can leave unused positions at the beginning after several dequeue operations. If the implementation does not reuse those positions, the queue may report that it is full even though there are empty locations before the current FRONT.
A Circular Queue is a queue in which the positions are logically arranged in a circle. After the rear reaches the last array position, it can wrap around to the beginning when a free position is available.
1 → 2 → 3 → 4 → 5
↑ ↓
└───────────────┘
Circular queues are useful when a fixed-size buffer needs to reuse memory efficiently.
For an array of size MAX, the next position can be calculated using the modulo operator:
next = (rear + 1) % MAX;
A Priority Queue is a specialized queue in which each element has an associated priority. The next element to be processed is selected according to the priority rule used by the implementation.
For example, if a system treats a larger priority value as higher priority:
| Process | Priority |
|---|---|
| P1 | 3 |
| P2 | 1 |
| P3 | 5 |
Under this rule, P3 is processed before P1 and P2 because it has the highest priority.
Priority queues are commonly implemented using heaps, although arrays and other structures can also be used.
Deque stands for Double Ended Queue. It allows insertion and deletion from both the front and rear ends. Because of this flexibility, a deque can support behaviors similar to both stacks and queues.
Insertion is allowed at only one end, while deletion can be performed from both ends.
Deletion is allowed at only one end, while insertion can be performed from both ends.
A queue can also be implemented using a linked list. This approach does not require a fixed array capacity. Nodes are created dynamically as elements are inserted.
For efficient queue operations, FRONT points to the first node and REAR points to the last node. Enqueue can be performed at REAR and dequeue at FRONT.
struct Node
{
int data;
struct Node *next;
};
| Operation | Typical Time Complexity |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
| IsEmpty | O(1) |
| IsFull | O(1) |
For a properly implemented queue, enqueue, dequeue and peek operate in constant time because they work with the front or rear rather than searching through all elements.
Queues are used whenever tasks, requests or data items need to wait for processing. The following applications cover the major uses without repeating the same real-world example in multiple sections.
Operating systems maintain queues of processes waiting for CPU time. Depending on the scheduling algorithm, processes may be selected from a ready queue in a particular order.
Ready Queue P1 → P2 → P3 → P4
When several documents are sent to a printer, print jobs can be placed in a queue and processed according to the printer's scheduling policy.
Print Queue Document A Document B Document C Document D
Network devices may temporarily queue packets when incoming traffic cannot be processed immediately. Queuing helps manage bursts of traffic and controls the order in which packets are handled.
Customer-service systems can place waiting requests or calls into queues so that available agents can handle them according to the system's service policy.
Web applications and distributed systems use queues to manage asynchronous requests and messages. Examples include order processing, notifications, background jobs and other tasks that can be processed independently of the user's immediate request.
Breadth First Search uses a queue to visit graph vertices level by level. A vertex is visited, its unvisited neighbors are added to the queue, and the next vertex is then removed from the front.
A
/ \
B C
/ \ \
D E F
For this graph, one possible BFS traversal is:
A → B → C → D → E → F
Step 1: Insert the starting vertex into the queue. Step 2: Mark the starting vertex as visited. Step 3: Remove a vertex from the front. Step 4: Visit each unvisited adjacent vertex. Step 5: Insert those vertices into the queue. Step 6: Repeat until the queue becomes empty.
The queue ensures that vertices are processed in level order, which is the key idea behind BFS traversal.
Background-processing systems often place tasks in a queue before workers process them. Examples include email sending, report generation, video processing, data synchronization and image processing.
This approach can separate task submission from task execution and helps systems handle temporary increases in workload.
Operating systems use several kinds of queues to manage processes and resource requests. For example, processes waiting for CPU time can be kept in a ready queue, while processes waiting for I/O can be placed in appropriate waiting or device queues.
| Queue | Stack |
|---|---|
| Follows FIFO. | Follows LIFO. |
| Uses FRONT and REAR. | Uses TOP. |
| Insertion at REAR. | Insertion at TOP. |
| Deletion from FRONT. | Deletion from TOP. |
| Commonly used in scheduling and BFS. | Commonly used in recursion and expression processing. |
A Queue is a linear data structure that normally follows the FIFO principle, with insertion at the rear and deletion at the front.
FIFO means First In First Out. The first inserted element is removed first.
The main operations are Enqueue, Dequeue, Peek, IsEmpty and IsFull.
Enqueue inserts an element at the rear of the queue.
Dequeue removes an element from the front of the queue.
Queue Overflow occurs when an insertion is attempted on a full bounded queue.
Queue Underflow occurs when a deletion is attempted on an empty queue.
A Circular Queue logically connects the last position of the queue to the first position so that available positions can be reused.
A Priority Queue processes elements according to their priority rather than simply their arrival order.
A Deque is a Double Ended Queue that supports insertion and deletion from both ends.
For a properly implemented standard queue, both operations are typically O(1).
Breadth First Search (BFS) uses a queue to process vertices level by level.
Round Robin scheduling is commonly implemented using a circular queue structure.
A Queue can be implemented using an array or a linked list. Specialized queues may use other structures depending on the application.
A standard Queue follows FIFO, whereas a Stack follows LIFO. Queue insertion and deletion normally occur at different ends, while Stack insertion and deletion occur at the same end.
Queue is a fundamental linear data structure based on the FIFO principle. Elements are inserted at the rear and removed from the front. Its main operations include enqueue, dequeue and peek, and it can be implemented using arrays or linked lists.
Important queue variants include Circular Queue, Priority Queue and Deque. Queues are widely used in CPU scheduling, printer spooling, network packet processing, task scheduling, message processing and Breadth First Search. Understanding queue operations, implementations, complexity and applications provides a strong foundation for Data Structures and Algorithms.
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