Queue Data Structure
A queue is linear data structure and collection of elements. A queue is another special kind of list, where items are inserted at one end called the rear and deleted at the other end called the front.
The principle of queue is a “FIFO” or “First-in-first-out”. Queue is an abstract data structure. A queue is a useful data structure in programming.
It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.
Key Features of Queue
Linear Structure: Data elements are arranged sequentially.
FIFO Order: The first element added is the first one to be removed.
Two Ends:
- Front: The end from where elements are dequeued (removed).
- Rear: The end where elements are enqueued (inserted).
Restricted Access: Insertions happen only at the rear, and deletions occur from the front.
Queues are used in real-world scenarios such as job scheduling, printer queue management, and data transmission in networks.
Queue Terminology
Enqueue: The operation of adding an element to the rear of the queue.
Dequeue: The operation of removing an element from the front of the queue.
Front: The first element in the queue, which is removed during the dequeue operation.
Rear: The last element in the queue, where new elements are inserted.
Underflow: A condition where an element is attempted to be removed from an empty queue.
Overflow: A condition where an element is attempted to be inserted into a full queue (in fixed-size queues).
FIFO (First In, First Out): The principle followed by queues, where the first inserted element is removed first.
Queue Representation in Memory
Queues can be implemented in two ways:
Using Arrays:
A fixed-size array is used to store queue elements.
The front and rear pointers help track element positions.
Can lead to wasted space after repeated deletions.
Using Linked Lists:
A dynamic memory allocation approach where nodes are linked together.
Efficient in memory usage as it grows dynamically.
Basic Queue Operations
1. Enqueue Operation (Insertion)
The Enqueue operation inserts an element at the rear of the queue.
- Before inserting, check if the queue is full (Queue Overflow).
- If not full, increment
rearand insert the element at the newrearposition.
2. Dequeue Operation (Deletion)
The Dequeue operation removes an element from the front of the queue.
- Before removing, check if the queue is empty (Queue Underflow).
- If not empty, remove the element at
front, then incrementfront.
3. Peek Operation (Front Element)
The Peek operation returns the element at the front of the queue without removing it.
4. isEmpty Operation
The isEmpty operation checks whether the queue is empty.
5. isFull Operation
The isFull operation checks whether the queue has reached its maximum size.
Applications of Queue
Task Scheduling in Operating Systems:
CPU and disk scheduling follow a queue-based approach.
Printer Job Scheduling:
Multiple print jobs are managed using a queue.
Call Center & Customer Support:
Calls and service requests are handled in a queue.
Data Transmission in Networks:
Queues manage data packets in routers and network buffers.
Breadth-First Search (BFS) Algorithm:
Used in graph traversal, where nodes are visited level by level.
Limitations of Simple Queue
A simple queue follows the FIFO (First In, First Out) principle, where elements are inserted at the rear and removed from the front. While simple queues are useful, they have certain limitations:
1. Fixed Size (Memory Waste in Static Implementation)
If a queue is implemented using an array, it has a fixed size, which can lead to wasted memory if the queue is not fully utilized.
Example: If an array-based queue has a size of 10 but only 3 elements are used, 7 spaces are wasted.
2. Inefficient Deletion (Wasted Space)
In a simple queue, when elements are dequeued, the front moves forward, but the empty spaces at the beginning of the array are not reused.
Example: If we insert A, B, C, D and remove A, B, there will be unused spaces at the beginning, which cannot be reclaimed.
3. Overflow Problem Despite Free Space
Even if there are free spaces at the beginning of the array due to deletions, the queue cannot use them because insertion happens only at the rear.
Example: If a queue of size 5 contains [_, _, C, D, E], trying to enqueue a new element results in Queue Overflow, even though there are empty slots at the front.
4. Slow Operations in Dynamic Queue Implementation
If a queue is implemented using linked lists, each enqueue or dequeue operation requires dynamic memory allocation, which takes extra time.
5. No Priority Handling
In simple queues, elements are processed in the order of arrival, but in some applications (e.g., emergency systems), priority-based processing is required.
6. Limited Performance in Multi-Tasking Systems
In systems that handle multiple processes, FIFO order may not always be efficient, requiring advanced queue variations.
Time and Space Complexity of Queue
In a straightforward (linear) queue implementation whether you use a fixed-size array (with front and rear indices) or a linked list the time and space complexities are:
Enqueue
- Time: O(1) You simply place the new element at the rear index (or tail pointer) and advance that pointer.
Dequeue
- Time: O(1) You remove the element at the front index (or head pointer) and advance that pointer.
Peek (access front element without removing it)
- Time: O(1) You just look at the element at front.
isEmpty / isFull checks
- Time: O(1) You compare front and rear (or count vs. capacity) in constant time.
Searching
- Time: O(n) You may have to scan through all n elements in the worst case.
Space Complexity
- O(n): Either you allocate an array of size n up front, or with a linked list you end up using one node per element, so total extra space grows linearly with the number of elements.
Because all of the standard operations (enqueue, dequeue, peek, checks) run in constant time, queues are very efficient for any situation where you need strict first-in, first-out processing.