Queue in Data Structures - Types & Algorithm (With Example)
Data Structures & Algorithms Free Course
Queue in Data Structures: An Overview
Queue in Data Structures is a type of non-primitive, linear, and dynamic data structure. It works according to the FIFO
principle. In this DSA tutorial, we will see queue data structure in detail i.e. its features, working, implementation, etc. To further enhance your understanding and application of queue concepts, consider enrolling in the Dsa Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.
What is a Queue in Data Structures?
A queue
is an ordered list in which insertion is done at one end called REAR
and deletion at another end called FRONT
. The first inserted element is available first for the operations to be performed and is the first one to be deleted. Hence, it is known as First In First Out, FIFO
, or Last In Last Out, LILO
.
Real-life examples of queues are a ticket queue outside a ticket counter, students standing in a queue for assembly prayer on the school grounds, queue of persons standing outside the booking counter of a theatre. In all these examples, the person standing first in the line is the first one for access.
Representation of a Queue in Data Structures
We know that a queue can be accessed from both sides i.e. at the front
for deletion and back or rear
for insertion.
Before moving forward, make sure that you are thorough with the concept of pointers
. If not refer to the Pointers in C++ tutorial and come back.
Standard Operations on Queue in Data Structures
- Insertion: enqueue()
The enqueue()
operation is used to insert an element at the back of a queue or to the end of a queue or the rear end of the queue.
Algorithm
Step 1: START
Step 2: Check if the queue is full.
Step 3: If the queue is full, produce an overflow error and exit.
Step 4: If the queue is not full, increment the rear pointer to point to the next space.
Step 5: Add a data element to the queue location, where the rear is pointing.
Step 6: End the process and exit.
- Deletion: dequeue()
The dequeue()
operation is used to remove and return the element from the front of a queue.
Algorithm
Step 1: START
Step 2: Check if the queue is empty.
Step 3: If the queue is empty, print underflow and exit.
Step 4: If the queue is not empty, access the data where the front is pointing.
Step 5: Increment the front pointer to point to the next available data element.
Step 6: Set the front and rear as -1 for the last element.
Step 7: End the process and exit.
- peek()
The peek()
operation returns the value at the front end of the queue without removing it.
Algorithm
Step 1: START
Step 2: Check if the Queue is empty.
Step 3: Return the element at the front of the queue
Step 4: End the process and exit.
- isFull()
The isFull()
operation is used to determine if the queue is full or not. A queue is said to be full if it has reached its maximum capacity and there is no more space to add new elements to it.
Algorithm
Step 1: START
Step 2: If the count of queue elements equals the queue size, return true.
Step 3: Otherwise, return false
Step 4: End the process and exit.
- isEmpty()
The isEmpty()
operation is used to check if the queue is empty or not. It returns a boolean value, true when the queue is empty, otherwise false.
Algorithm
Step 1: START
Step 2: If the count of queue elements equals zero, return true.
Step 3: Otherwise, return false
Step 4: End the process and exit.
Read More - DSA Interview Questions and Answers
Working of Queue in Data Structures
Queue operations work as follows:
- Two pointers are there denoting two ends,
FRONT
andREAR
. FRONT
tracks the first element of the queue.REAR
tracks the last element of the queue.- Initially, set the value of
FRONT
andREAR
to-1
. - Afterward, follow the above-given algorithms for the basic operations.
Types of Queues in Data Structures
- Simple Queue/Linear Queue: Here, elements are inserted from one end i.e. rear end, and removed from the other end i.e. front.
It follows the
FIFO
(First In First Out) order. - Circular Queue: It is similar to a simple queue, but the last element is connected to the first element, creating a circular structure. This allows for efficient use of memory.
- Priority Queue: It is a special type of queue in which each element has a priority assigned to it. The element with the highest priority is removed first. This is useful in situations where certain elements need to be processed before others.
Read More: Priority Queue in Data Structures
- Dequeue (Double-Ended Queue): In this, the elements can be added or removed from both ends,
front
andrear
of the queue.
Implementation of Queue in Different Programming Languages
There are three ways to implement Queues in Data Structures, using a 1D Array, a Single Linked List, and vectors. We will look at array and linked list implementation in detail.
- Implementation of Queue Using a 1D Array
It is the simplest implementation of a Queue in Data Structures. We usually use arrays
to implement queues in Java and C++. In the case of Python, we use lists.
The time complexity of all the operations is the same i.e. O(1)
here.
class Queue:
def __init__(self, capacity):
self.capacity = capacity
self.front = self.size = 0
self.rear = capacity - 1
self.array = [0] * self.capacity
def is_full(self):
return self.size == self.capacity
def is_empty(self):
return self.size == 0
def enqueue(self, item):
if self.is_full():
return
self.rear = (self.rear + 1) % self.capacity
self.array[self.rear] = item
self.size += 1
print(f"{item} enqueued to queue")
def dequeue(self):
if self.is_empty():
return float('-inf')
item = self.array[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
def get_front(self):
return self.array[self.front] if not self.is_empty() else float('-inf')
def get_rear(self):
return self.array[self.rear] if not self.is_empty() else float('-inf')
if __name__ == "__main__":
# Create a queue with a capacity of 100
queue = Queue(100)
# Enqueue elements into the queue
queue.enqueue(10)
queue.enqueue(15)
queue.enqueue(20)
queue.enqueue(25)
queue.enqueue(30)
# Dequeue elements from the queue
print(f"{queue.dequeue()} dequeued from queue")
print(f"{queue.dequeue()} dequeued from queue")
print(f"{queue.dequeue()} dequeued from queue")
# Display the front and rear elements of the queue
print("Front item is", queue.get_front())
print("Rear item is", queue.get_rear())
public class Queue {
int front, rear, size;
int capacity;
int[] array;
// Function to create a queue of given capacity
public Queue(int capacity) {
this.capacity = capacity;
this.front = this.size = 0;
this.rear = capacity - 1;
this.array = new int[this.capacity];
}
// Function to check if the queue is full
boolean isFull() {
return (this.size == this.capacity);
}
// Function to check if the queue is empty
boolean isEmpty() {
return (this.size == 0);
}
// Function to enqueue an item
void enqueue(int item) {
if (isFull())
return;
this.rear = (this.rear + 1) % this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item + " enqueued to queue");
}
// Function to dequeue an item
int dequeue() {
if (isEmpty())
return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1) % this.capacity;
this.size = this.size - 1;
return item;
}
// Function to get the front item of the queue
int front() {
if (isEmpty())
return Integer.MIN_VALUE;
return this.array[this.front];
}
// Function to get the rear item of the queue
int rear() {
if (isEmpty())
return Integer.MIN_VALUE;
return this.array[this.rear];
}
public static void main(String[] args) {
// Create a queue with a capacity of 100
Queue queue = new Queue(100);
// Enqueue elements into the queue
queue.enqueue(10);
queue.enqueue(15);
queue.enqueue(20);
queue.enqueue(25);
queue.enqueue(30);
// Dequeue elements from the queue
System.out.println(queue.dequeue() + " dequeued from queue");
System.out.println(queue.dequeue() + " dequeued from queue");
System.out.println(queue.dequeue() + " dequeued from queue");
// Display the front and rear elements of the queue
System.out.println("Front item is " + queue.front());
System.out.println("Rear item is " + queue.rear());
}
}
#include <iostream>
using namespace std;
class Queue {
public:
int front, rear, size;
unsigned capacity;
int* array;
};
// Function to create a queue of given capacity
Queue* createQueue(unsigned capacity) {
Queue* queue = new Queue();
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->array = new int[queue->capacity];
return queue;
}
// Function to check if the queue is full
int isFull(Queue* queue) {
return (queue->size == queue->capacity);
}
// Function to check if the queue is empty
int isEmpty(Queue* queue) {
return (queue->size == 0);
}
// Function to enqueue an item
void enqueue(Queue* queue, int item) {
if (isFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueued to queue\n";
}
// Function to dequeue an item
int dequeue(Queue* queue) {
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get the front item of the queue
int front(Queue* queue) {
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get the rear item of the queue
int rear(Queue* queue) {
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main() {
// Create a queue with a capacity of 100
Queue* queue = createQueue(100);
// Enqueue elements into the queue
enqueue(queue, 10);
enqueue(queue, 15);
enqueue(queue, 20);
enqueue(queue, 25);
enqueue(queue, 30);
// Dequeue elements from the queue
cout << dequeue(queue) << " dequeued from queue\n";
cout << dequeue(queue) << " dequeued from queue\n";
cout << dequeue(queue) << " dequeued from queue\n";
// Display the front and rear elements of the queue
cout << "Front item is " << front(queue) << endl;
cout << "Rear item is " << rear(queue) << endl;
return 0;
}
Output
10 enqueued to queue
15 enqueued to queue
20 enqueued to queue
25 enqueued to queue
30 enqueued to queue
10 dequeued from queue
15 dequeued from queue
20 dequeued from queue
Front item is 25
Rear item is 30
Advantages of Array Implementation
- Easy to implement.
- A large amount of data can be managed efficiently with ease.
- Operations such as insertion and deletion can be performed with ease as a queue follows the
FIFO
rule.
Limitations of Array Implementation
- The maximum size of the queue must be defined beforehand.
- The size of the array cannot be changed during the run time because it is not dynamic.
- If the queue has a large number of
enqueue
anddequeue
operations, at some point (in case of linear increment offront
andrear
indexes) it may happen that we may not be able to insert elements in the queue even if the queue is empty.
- Implementation of a Queue Using a Linked List
We discussed the disadvantages of array implementation above. Due to this, the array cannot be used for large-scale applications of queues. One of the solutions to overcome this limitation is linked list
implementation of queues in data structures
The storage requirement of the linked representation of a queue with n elements is O(n)
. The time complexity of all the operations is the same i.e. O(1)
here.
In a linked queue, each node of the queue consists of two parts i.e. data
part and the link
part. Each element of the queue points to its immediate next element in the memory. There are two pointers maintained in the memory i.e. front
pointer and rear
pointer. The front
pointer contains the address of the starting element of the queue while the rear
pointer contains the address of the last element of the queue.
Example of Queue Implementation in Different Languages Using a Linked List
class QNode:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = self.rear = None
def enQueue(self, x):
temp = QNode(x)
if self.rear is None:
self.front = self.rear = temp
return
self.rear.next = temp
self.rear = temp
def deQueue(self):
if self.front is None:
return
temp = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
del temp
if __name__ == "__main__":
q = Queue()
q.enQueue(10)
q.enQueue(15)
q.enQueue(20)
q.enQueue(25)
q.enQueue(30)
q.deQueue()
q.deQueue()
q.deQueue()
q.enQueue(35)
q.enQueue(40)
q.enQueue(45)
q.deQueue()
print("Front element is:", q.front.data if q.front is not None else -1)
print("Rear element is:", q.rear.data if q.rear is not None else -1)
class QNode {
int data;
QNode next;
public QNode(int d) {
data = d;
next = null;
}
}
class Queue {
QNode front, rear;
public Queue() {
front = rear = null;
}
void enQueue(int x) {
QNode temp = new QNode(x);
if (rear == null) {
front = rear = temp;
return;
}
rear.next = temp;
rear = temp;
}
void deQueue() {
if (front == null)
return;
QNode temp = front;
front = front.next;
if (front == null)
rear = null;
// free up the memory
temp = null;
}
}
class Main {
public static void main(String[] args) {
Queue q = new Queue();
q.enQueue(10);
q.enQueue(15);
q.enQueue(20);
q.enQueue(25);
q.enQueue(30);
q.deQueue();
q.deQueue();
q.deQueue();
q.enQueue(35);
q.enQueue(40);
q.enQueue(45);
q.deQueue();
System.out.println("Front element is: " + ((q.front != null) ? q.front.data : -1));
System.out.println("Rear element is : " + ((q.rear != null) ? q.rear.data : -1));
}
}
#include <iostream>
using namespace std;
struct QNode {
int data;
QNode* next;
QNode(int d)
{
data = d;
next = NULL;
}
};
struct Queue {
QNode* front, * rear;
Queue() { front = rear = NULL; }
void enQueue(int x)
{
QNode* temp = new QNode(x);
if (rear == NULL) {
front = rear = temp;
return;
}
rear->next = temp;
rear = temp;
}
void deQueue()
{
if (front == NULL)
return;
QNode* temp = front;
front = front->next;
if (front == NULL)
rear = NULL;
delete (temp);
}
};
int main()
{
Queue q;
q.enQueue(10);
q.enQueue(15);
q.enQueue(20);
q.enQueue(25);
q.enQueue(30);
q.deQueue();
q.deQueue();
q.deQueue();
q.enQueue(35);
q.enQueue(40);
q.enQueue(45);
q.deQueue();
cout << "Front element is: " << ((q.front != NULL) ? (q.front)->data : -1) << endl;
cout << "Rear element is : " << ((q.rear != NULL) ? (q.rear)->data : -1);
return 0;
}
Output
Front element is: 30
Rear element is : 45
If you are facing any difficulty in understanding the linked list implementation of the queue in data structures refer to the previous tutorial, Linked Lists in Data Structures.
Complexity Analysis of Queue Operations
Stack Vs Queue
Parameters | Stack | Queue |
Working Principle | It follows the | It follows the |
Pointers | It has only one end, known as the | It has two ends, |
Operations | The insertion operation is known as | The insertion operation is known as |
Empty Condition | The condition for checking whether the stack is empty is | The condition for checking whether the queue is empty is |
Full Condition | The condition for checking if the stack is full is | The condition for checking if the queue is full is |
Variants | There are no other variants or types of the stack. | There are three types of queues: |
Implementation | It has a simple implementation compared to queues as no two pointers are involved. | It has a complex implementation compared to stacks as two pointers |
Data Representation | Often implemented with | Can also be implemented with |
Example | the Undo/Redo operation in Word or Excel. | operating system process scheduling queues. |
Application | It is used to solve | It is used to solve sequential processing-based problems. |
Visualization | A stack can be visualized as a vertical collection. | Queue can be visualized as a horizontal collection. |
Applications of Queue
- Multi-programming: It is essential to organize the multiple programs running in the main memory so they are organized as queues.
- Network: In a network, a queue is used in devices such as a router or a switch.
- Job Scheduling: The computer has a task to execute a particular number of jobs that are scheduled to be executed one after another. These jobs are assigned to the processor one by one which is organized using a queue. E.g. CPU scheduling, Disk Scheduling
- Synchronization: The queue is used for synchronization when data is transferred asynchronously between two processes. E.g. IO Buffers, pipes, file IO, etc
- Interrupts: Handling of interrupts in real-time systems.
- Shared resources: Queues are used as waiting lists for a single shared resource.
- Operation on data structures: Certain operations like BFS (Breadth First Search), and tree traversal use Queue. The sequence of traversal of inputs is set using queues.
Advantages of Queue
- Efficient data processing: A queue can be used to efficiently process data in the order it was received. For example, in a computer system, a queue can be used to schedule processes in the order they were submitted.
- Resource management: A queue can be used to manage resources that are shared among multiple processes or threads. For example, a printer can use a queue to manage print jobs.
- Buffering: A queue can be used to buffer incoming data so that it can be processed at a later time. For example, a network device can use a queue to buffer incoming data packets before forwarding them to their destination.
- Memory management: A queue can be used to manage memory by allocating and deallocating memory blocks in sequential order.
Disadvantages of Queue
- Limited flexibility: Queues follow a strict
FIFO
order, meaning the element that enters first is the first one to be removed. This lack of flexibility can be a disadvantage in some use cases where other priorities or requirements must be considered. - No random access: Unlike arrays or linked lists, queues do not allow random access to the elements. The user can only access the first element in the queue, and to access any other element, they need to remove all the elements that come before it. This can be a disadvantage when the user needs to access an element in the middle of the queue.
- Overhead: Queues require extra overhead to maintain the order of elements. Whenever an element is added or removed from the queue, all the other elements must be shifted accordingly, which can be time-consuming for large queues.
- Limited size: In some implementations, queues have a limited size, which can be a disadvantage when dealing with large amounts of data. Once the queue reaches its maximum size, it can no longer accept new elements.
- No search operation: Queues do not provide a search operation. The user cannot search for a specific element in the queue they can only remove the elements in the order they were added and hope to find the element they are looking for.
Summary
So, here we saw every aspect of a queue in data structures. You might have got at least some idea regarding queues and their applications. I know it's quite difficult to understand the whole topic in a single go. Therefore, refer to it again and again till you get thorough with the queue in data structures. To test your knowledge of queue, enroll in our Best Data Structures And Algorithms Course.
FAQs
Q1. Name the two pointers for denoting two ends of a queue?
Q2. What are the types of Queues?
- Simple Queue/Linear Queue
- Circular Queue
- Priority Queue
- Dequeue (Double-Ended Queue)