Unit 3: Queues
3.1 Definition and Concept of Queue
3.2 Representation – static
3.3 Operations- Insert, Delete
3.4 Circular queue : Concept, Operations – insert, delete
3.5 DeQue : Concept
3.6 Priority queues : Concept
Introduction :-
A queue is a linear data structure where elements are stored in the FIFO (First In First Out) principle
where the first element inserted would be the first element to be accessed. A queue is an Abstract
Data Type (ADT) similar to stack, the thing that makes queue different from stack is that a queue is
open at both its ends. The data is inserted into the queue through one end and deleted from it using
the other end. Queue is very frequently used in most programming languages.
FIFO Principle in Queue:
FIFO Principle states that the first element added to the Queue will be the first one to be removed or
processed. So, Queue is like a line of people waiting to purchase tickets, where the first person in line
is the first person served. (i.e. First Come First Serve).
A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits
first. More real-world examples can be seen as queues at the ticket windows and bus-stops.
3.1 Definition and Concept of Queue
The Queue is a linear data structure or an abstract data type. Queue follows the FIFO – “first in, first
out” method to process the data. The data which is inserted first will be accessed first. Unlike Stack,
Queue has two ends REAR and FRONT. The REAR end is always used to insert the data i.e., enqueue,
and the FRONT end is used to remove the data inserted i.e. dequeue.
Basic Operations of Queue
A queue is an object (an abstract data structure - ADT) that allows the following operations: Basic
Some of the basic operations for Queue in Data Structure are:
• enqueue() - Insertion of elements to the queue.
• dequeue() - Removal of elements from the queue.
• getFront()- Acquires the data element available at the front node of the queue without
deleting it.
• getRear() - This operation returns the element at the rear end without removing it.
• isFull() - Validates if the queue is full.
• isEmpty() - Checks if the queue is empty.
• size() - This operation returns the size of the queue i.e. the total number of elements it
contains.
Representation of Queues
Similar to the stack ADT, a queue ADT can also be implemented using arrays, linked lists, or pointers.
As a small example in this tutorial, we implement queues using a one-dimensional array.
Representation of queues
Some common applications of Queue data structure :
1. Task Scheduling: Queues can be used to schedule tasks based on priority or the order in
which they were received.
2. Resource Allocation: Queues can be used to manage and allocate resources, such as
printers or CPU processing time.
3. Batch Processing: Queues can be used to handle batch processing jobs, such as data
analysis or image rendering.
4. Message Buffering: Queues can be used to buffer messages in communication systems,
such as message queues in messaging systems or buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven systems, such as GUI
applications or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in transportation systems,
such as airport control systems or road networks.
7. Operating systems: Operating systems often use queues to manage processes and
resources. For example, a process scheduler might use a queue to manage the order in which
processes are executed.
8. Network protocols: Network protocols like TCP and UDP use queues to manage packets that
are transmitted over the network. Queues can help to ensure that packets are delivered in the
correct order and at the appropriate rate.
9. Printer queues :In printing systems, queues are used to manage the order in which print
jobs are processed. Jobs are added to the queue as they are submitted, and the printer
processes them in the order they were received.
10. Web servers: Web servers use queues to manage incoming requests from clients. Requests
are added to the queue as they are received, and they are processed by the server in the order
they were received.
Static Queue Representation (Using an Array)
In a static implementation, the queue is typically represented by:
• An array of fixed size.
• Two integer variables:
o front – index of the front element.
o rear – index of the last element.
Operations on Queue Following the FIFO approach, data structure queue supports the following
operations:
• ENQUEUE: is used to insert a new element to the queue at the rear end. We can insert elements
in the queue till there is space in the queue for adding more elements. Inserting elements beyond
capacity of the queue will result in an exception - known as Overflow.
• DEQUEUE: is used to remove one element at a time from the front of the queue. We can delete
elements from a queue until it is empty, trying to delete an element from an empty queue will result
in exception - known as Underflow. To perform enqueue and dequeue efficiently on a queue, following
operations are also required:
• IS EMPTY : used to check whether the queue has any element or not, so as to avoid Underflow
exception while performing dequeue operation
3 Operations- Insert, Delete
1. Inserting Elements
New elements can only be inserted at back of the queue using push() function. The process of
inserting elements in a queue is also called enqueue.
Example
#include <bits/stdc++.h>
using namespace std;
int main()
{
queue<int> q;
// Pushing elements into the queue
q.push(3);
q.push(4);
q.push(5);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
Deleting Elements
Elements can only be deleted from the front of the queue using the pop() function. This operation is
also called dequeue.
Example
#include <bits/stdc++.h>
using namespace std;
int main() {
queue<int> q;
q.push(3);
q.push(4);
q.push(5);
// Deleting elements from front side
// of the queue
q.pop();
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
3.4 Circular queue : Concept, Operations – insert, delete
A circular queue is the extended version of a regular queue where the last element is connected to
the first element. Thus forming a circle-like structure.
What is Circular Queue?
A circular queue is a type of queue in which the last position is connected back to the first position to
make a circle. It is also known as a Ring Buffer. In a normal queue, once the queue becomes full, we
cannot insert the next element even if there is a space in front of the queue. But using a circular
queue, we can use the space to insert elements.
It is a linear data structure that follows the FIFO mechanism. The circular queue is a more efficient
way to implement a queue in a fixed size array. In a circular queue, the last element points to the
first element making a circular link.
The circular queue solves the major limitation of the normal queue. In a normal queue, after a bit of
insertion and deletion, there will be non-usable empty space.
Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This
reduces the actual size of the queue.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e. when we try to increment the pointer
and we reach the end of the queue, we start from the beginning of the queue.
Here, the circular increment is performed by modulo division with the queue size. That is,
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Circular Queue Operations
The circular queue work as follows:
• two pointers FRONT and REAR
• FRONT track the first element of the queue
• REAR track the last elements of the queue
• initially, set value of FRONT and REAR to -1
1. Enqueue Operation
• check if the queue is full
• for the first element, set value of FRONT to 0
• circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at
the start of the queue)
• add the new element in the position pointed to by REAR
2. Dequeue Operation
• check if the queue is empty
• return the value pointed by FRONT
• circularly increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1
However, the check for full queue has a new additional case:
• Case 1: FRONT = 0 && REAR == SIZE - 1
• Case 2: FRONT = REAR + 1
The second case happens when REAR starts from 0 due to circular increment and when its value is
just 1 less than FRONT, the queue is full.
Circular Queue Implementations
#include <iostream>
using namespace std;
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
// Check if the queue is full
int isFull() {
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}// Check if the queue is empty
int isEmpty() {
if(front == -1) return 1;
return 0;
}// Adding an element
void enQueue(int element) {
if(isFull()) cout << "Queue is full\n";
else {
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl << "Inserted " << element << endl;
}}
// Display the queue
void display() {
int i;
if(isEmpty()) cout << endl << "Empty Queue" << endl;
else {
cout << "Items";
for(i = front; i!=rear; i=(i+1)%SIZE) {
cout << items[i] << " ";
}
cout << items[i];
}
}
int main() {
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
display();
return 0;
}
3.5 DeQue : Concept
Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and
delete at both ends. Deque is a hybrid data structure that combines the features of a stack and
a queue. It allows us to insert and delete elements from both ends of the queue. The name Deque is
an abbreviation of Double-Ended Queue.
Imagine an event where you have two gates to enter and exit a place. People are entering from
the front gate and some are entering from the side gate. Now, when people are leaving, they are
leaving from the front gate and some sneak from the side gate. Now, we need to manage flow of
people from both ends. This is where Deque comes into play.
.
Operations on Deque
Following are the major operations on Deque −
• push_front(x): Insert element x at the front of the deque.
• push_back(x): Insert element x at the back of the deque.
• pop_front(): Remove the element from the front of the deque.
• pop_back(): Remove the element from the back of the deque.
• peek_front(): Get the element from the front of the deque.
• peek_back(): Get the element from the back of the deque.
• size(): Get the number of elements in the deque.
• isEmpty(): Check if the deque is emp
#include <iostream>
using namespace std;
#define SIZE 5
int deque[SIZE];
int front = -1, rear = -1;
// Check if the deque is full
bool isFull() {
return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
}
// Check if the deque is empty
bool isEmpty() {
return front == -1;
}
// Insert element at the front
void push_front(int element) {
if (isFull()) {
cout << "Deque is full" << endl;
return;
}
if (isEmpty()) { // First element being inserted
front = rear = 0;
}
else if (front == 0) { // Wrap around
front = SIZE - 1;
}
else {
front--;
}
deque[front] = element;
cout << "Inserted -> " << element << endl;
}
// Display the deque
void display() {
if (isEmpty()) {
cout << "Empty Deque" << endl;
return;
}
cout << "Elements -> ";
int i = front;
while (true) {
cout << deque[i] << " ";
if (i == rear) break; // Stop at last element
i = (i + 1) % SIZE; // Circular increment
}
cout << endl;
}
int main() {
push_front(1);
push_front(2);
push_front(3);
push_front(4);
push_front(5);
display();
return 0;
}
3.6 Priority queues : Concept
A priority queue is a type of queue that arranges elements based on their priority values.
• Each element has a priority associated. When we add an item, it is inserted in a position based
on its priority.
• Elements with higher priority are typically retrieved or removed before elements with lower
priority.
• Binary heap is the most common method to implement a priority queue. In binary heaps, we
have easy access to the min (in min heap) or max (in max heap) and binary heap being a
complete binary tree are easily implemented using arrays. Since we use arrays, we have cache
friendliness advantage also.
• Priority Queue is used in algorithms such as Dijkstra's algorithm, Prim's algorithm,
and Huffman Coding
Types of Priority Queue
• Ascending Order Priority Queue : In this queue, elements with lower values have higher
priority. For example, with elements 4, 6, 8, 9, and 10, 4 will be dequeued first since it has
the smallest value, and the dequeue operation will return 4.
• Descending order Priority Queue : Elements with higher values have higher priority. The root
of the heap is the highest element, and it is dequeued first. The queue adjusts by maintaining
the heap property after each insertion or deletion.
How Priority is Determined in a Priority Queue?
In a priority queue, generally, the value of an element is considered for assigning the priority. For
example, the element with the highest value is assigned the highest priority and the element with
the lowest value is assigned the lowest priority. The reverse case can also be used i.e., the element
with the lowest value can be assigned the highest priority. Also, the priority can be assigned
according to our needs.
Operations on a Priority Queue
A typical priority queue supports the following operations:
1) Insertion : If the newly inserted item is of the highest priority, then it is inserted at the top.
Otherwise, it is inserted in such a way that it is accessible after all higher priority items are accessed.
2) Deletion : We typically remove the highest priority item which is typically available at the top.
Once we remove this item, we need not move next priority item at the top.
3) Peek : This operation only returns the highest priority item (which is typically available at the
top) and does not make any change to the priority queue.
Difference between Priority Queue and Normal Queue
There is no priority attached to elements in a queue, the rule of first-in-first-out(FIFO) is
implemented whereas, in a priority queue, the elements have a priority. The elements with higher
priority are served first.
Example
// Priority Queue implementation in C++
#include <iostream>
#include <vector>
using namespace std;
// Function to swap position of two elements
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}
// Function to heapify the tree
void heapify(vector<int> &hT, int i) {
int size = hT.size();
// Find the largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && hT[l] > hT[largest])
largest = l;
if (r < size && hT[r] > hT[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&hT[i], &hT[largest]);
heapify(hT, largest);
}}
// Function to insert an element into the tree
void insert(vector<int> &hT, int newNum) {
int size = hT.size();
if (size == 0) {
hT.push_back(newNum);
} else {
hT.push_back(newNum);
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(hT, i);
}}}
// Function to delete an element from the tree
void deleteNode(vector<int> &hT, int num) {
int size = hT.size();
int i;
for (i = 0; i < size; i++) {
if (num == hT[i])
break;
}
swap(&hT[i], &hT[size - 1]);
hT.pop_back();
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(hT, i);
}}
// Print the tree
void printArray(vector<int> &hT) {
for (int i = 0; i < hT.size(); ++i)
cout << hT[i] << " ";
cout << "\n";
}// Driver code
int main() {
vector<int> heapTree;
insert(heapTree, 3);
insert(heapTree, 4);
insert(heapTree, 9);
insert(heapTree, 5);
insert(heapTree, 2);
cout << "Max-Heap array: ";
printArray(heapTree);
deleteNode(heapTree, 4);
cout << "After deleting an element: ";
printArray(heapTree);
}
Question
1 marks
What is queue?
What is circular queue?
How many types in queue?
Which is operation of queue
Broad Question
Explain queue with example ?
Explain Queue operation with example
Explain priority queue with example
Exline circular queue with example
