Queues
Concept of Queues
A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Think of a queue as a line of people waiting for a service - the person who arrives first gets served first.
Queues are used in various applications in computer science, including process scheduling in operating systems, handling of interrupts in real-time systems, and breadth-first search algorithm in graphs.
Visual Representation of a Queue
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ A │ │ B │ │ C │ │ D │
└───┘ └───┘ └───┘ └───┘
↑ ↑
Front Rear
(First Out) (Last In)
Key Characteristics of Queues
- FIFO (First In First Out): The first element inserted is the first one to be removed.
- Dynamic Size: The size of the queue can grow and shrink as elements are enqueued and dequeued.
- Two Points of Access: Elements are inserted at the rear and removed from the front.
- Restricted Operations: Only a limited set of operations are allowed on a queue.
Primitive Operations
A queue supports the following basic operations:
1. Enqueue
The enqueue operation adds an element to the rear of the queue. If the queue is full, this operation may result in a queue overflow.
Enqueue Operation
Before Enqueue(E): After Enqueue(E):
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ A │ │ B │ │ A │ │ B │ │ E │
└───┘ └───┘ └───┘ └───┘ └───┘
↑ ↑ ↑ ↑
Front Rear Front Rear
2. Dequeue
The dequeue operation removes the element from the front of the queue and returns it. If the queue is empty, this operation may result in a queue underflow.
Dequeue Operation
Before Dequeue(): After Dequeue():
┌───┐ ┌───┐ ┌───┐
│ A │ │ B │ │ B │
└───┘ └───┘ └───┘
↑ ↑ ↑ ↑
Front Rear Front Rear
3. Front (or Peek)
The front operation returns the element at the front of the queue without removing it. If the queue is empty, this operation may return an error or a special value.
Front Operation
Queue: Front() returns A
┌───┐ ┌───┐ (Queue remains unchanged)
│ A │ │ B │
└───┘ └───┘
↑ ↑
Front Rear
4. isEmpty
The isEmpty operation checks if the queue is empty. It returns true if the queue has no elements, and false otherwise.
5. isFull
The isFull operation checks if the queue is full. It returns true if the queue cannot accommodate any more elements, and false otherwise. This operation is relevant only for queues with a fixed size.
6. Size
The size operation returns the number of elements currently in the queue.
Abstract Data Type
A queue is an abstract data type (ADT) that specifies a collection of elements with specific operations but does not specify how these operations are implemented. The ADT defines what operations are allowed on the data structure, but not how these operations are implemented.
Queue ADT Specification
The Queue ADT can be defined as follows:
ADT Queue {
// Data
A collection of elements with FIFO access
// Operations
void enqueue(element) // Add element to the rear of the queue
element dequeue() // Remove and return the front element
element front() // Return the front element without removing it
boolean isEmpty() // Check if the queue is empty
boolean isFull() // Check if the queue is full
int size() // Return the number of elements in the queue
}
This ADT specification defines what a queue is and what operations it supports, but it does not specify how these operations are implemented. The implementation can vary depending on the underlying data structure used (e.g., array, linked list).
Representation of Queues Using Arrays
One of the most common ways to implement a queue is using an array. In this implementation, we use an array to store the elements and two variables to keep track of the front and rear of the queue.
Array Implementation of Queue
Here's a C++ implementation of a queue using an array:
#include <iostream>
using namespace std;
class Queue {
private:
int* arr; // Array to store queue elements
int capacity; // Maximum capacity of the queue
int front; // Index of the front element
int rear; // Index of the rear element
int size; // Current size of the queue
public:
// Constructor
Queue(int capacity) {
this->capacity = capacity;
arr = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
// Destructor
~Queue() {
delete[] arr;
}
// Enqueue operation
void enqueue(int x) {
if (isFull()) {
cout << "Queue Overflow" << endl;
return;
}
rear = (rear + 1) % capacity;
arr[rear] = x;
size++;
cout << x << " enqueued to queue" << endl;
}
// Dequeue operation
int dequeue() {
if (isEmpty()) {
cout << "Queue Underflow" << endl;
return -1;
}
int x = arr[front];
front = (front + 1) % capacity;
size--;
return x;
}
// Front operation
int getFront() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[front];
}
// Rear operation
int getRear() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[rear];
}
// Check if queue is empty
bool isEmpty() {
return size == 0;
}
// Check if queue is full
bool isFull() {
return size == capacity;
}
// Get size of queue
int getSize() {
return size;
}
// Display queue elements
void display() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue elements: ";
int count = 0;
int i = front;
while (count < size) {
cout << arr[i] << " ";
i = (i + 1) % capacity;
count++;
}
cout << endl;
}
};
int main() {
Queue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.display();
cout << "Front element: " << q.getFront() << endl;
cout << "Rear element: " << q.getRear() << endl;
cout << q.dequeue() << " dequeued from queue" << endl;
q.display();
cout << "Queue size: " << q.getSize() << endl;
return 0;
}
Advantages of Array Implementation
- Simple and Easy to Implement: Array implementation of a queue is straightforward.
- Memory Efficient: No extra memory is required for pointers as in linked list implementation.
- Cache Friendly: Arrays have good locality of reference, which can lead to better cache performance.
Disadvantages of Array Implementation
- Fixed Size: The size of the queue is fixed and cannot be changed during runtime.
- Queue Overflow: If the queue is full, enqueuing more elements will result in a queue overflow.
- Memory Wastage: If the queue is not fully utilized, memory is wasted.
Circular Queue
A circular queue is a variation of a queue in which the last position is connected back to the first position to form a circle. This allows for better memory utilization as we can reuse the empty spaces created by dequeued elements.
Why Circular Queue?
In a simple queue implementation using an array, once the rear reaches the end of the array, we cannot insert more elements even if there is space at the front of the array (due to dequeued elements). This leads to inefficient use of space.
A circular queue solves this problem by connecting the last position to the first position, allowing us to reuse the empty spaces.
Circular Queue Visualization
┌───┐
│ 3 │ ← Rear
└───┘
┌───┐
│ 2 │
└───┘
┌───┐
│ 1 │
└───┘
┌───┐
│ │
└───┘
┌───┐
│ │
└───┘
┌───┐
│ 6 │
└───┘
┌───┐
│ 5 │
└───┘
┌───┐
│ 4 │ ← Front
└───┘
Implementation of Circular Queue
Here's a C++ implementation of a circular queue:
#include <iostream>
using namespace std;
class CircularQueue {
private:
int* arr; // Array to store queue elements
int capacity; // Maximum capacity of the queue
int front; // Index of the front element
int rear; // Index of the rear element
int size; // Current size of the queue
public:
// Constructor
CircularQueue(int capacity) {
this->capacity = capacity;
arr = new int[capacity];
front = -1;
rear = -1;
}
// Destructor
~CircularQueue() {
delete[] arr;
}
// Enqueue operation
void enqueue(int x) {
// Check if the queue is full
if ((front == 0 && rear == capacity - 1) || (rear == (front - 1) % (capacity - 1))) {
cout << "Queue Overflow" << endl;
return;
}
// If queue is empty
else if (front == -1) {
front = rear = 0;
arr[rear] = x;
}
// If rear is at the end of the array
else if (rear == capacity - 1 && front != 0) {
rear = 0;
arr[rear] = x;
}
// Normal case
else {
rear++;
arr[rear] = x;
}
cout << x << " enqueued to queue" << endl;
}
// Dequeue operation
int dequeue() {
// Check if the queue is empty
if (front == -1) {
cout << "Queue Underflow" << endl;
return -1;
}
int x = arr[front];
// If there is only one element
if (front == rear) {
front = rear = -1;
}
// If front is at the end of the array
else if (front == capacity - 1) {
front = 0;
}
// Normal case
else {
front++;
}
return x;
}
// Front operation
int getFront() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[front];
}
// Rear operation
int getRear() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[rear];
}
// Check if queue is empty
bool isEmpty() {
return front == -1;
}
// Check if queue is full
bool isFull() {
return (front == 0 && rear == capacity - 1) || (rear == (front - 1) % (capacity - 1));
}
// Display queue elements
void display() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue elements: ";
if (rear >= front) {
for (int i = front; i <= rear; i++) {
cout << arr[i] << " ";
}
} else {
for (int i = front; i < capacity; i++) {
cout << arr[i] << " ";
}
for (int i = 0; i <= rear; i++) {
cout << arr[i] << " ";
}
}
cout << endl;
}
};
int main() {
CircularQueue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.display();
cout << "Front element: " << q.getFront() << endl;
cout << "Rear element: " << q.getRear() << endl;
cout << q.dequeue() << " dequeued from queue" << endl;
q.display();
q.enqueue(50);
q.enqueue(60);
q.display();
return 0;
}
Advantages of Circular Queue
- Better Memory Utilization: Circular queues allow for reuse of empty spaces, leading to better memory utilization.
- Efficient for Fixed-Size Applications: Circular queues are efficient for applications where the queue size is fixed and known in advance.
Disadvantages of Circular Queue
- Fixed Size: Like simple queues, circular queues also have a fixed size.
- Complex Implementation: The implementation of a circular queue is more complex than a simple queue.
Double-Ended Queue (Deque)
A double-ended queue, or deque (pronounced "deck"), is a queue that allows insertion and deletion of elements from both the front and the rear. This provides more flexibility than a standard queue.
Operations on Deque
- insertFront: Adds an element to the front of the deque.
- insertRear: Adds an element to the rear of the deque.
- deleteFront: Removes and returns the front element of the deque.
- deleteRear: Removes and returns the rear element of the deque.
- getFront: Returns the front element of the deque without removing it.
- getRear: Returns the rear element of the deque without removing it.
- isEmpty: Checks if the deque is empty.
- isFull: Checks if the deque is full.
Deque Visualization
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ A │ │ B │ │ C │ │ D │
└───┘ └───┘ └───┘ └───┘
↑ ↑
Front Rear
Operations:
- insertFront(X): Add X to the front
- insertRear(X): Add X to the rear
- deleteFront(): Remove from the front
- deleteRear(): Remove from the rear
Implementation of Deque
Here's a C++ implementation of a deque using an array:
#include <iostream>
using namespace std;
class Deque {
private:
int* arr; // Array to store deque elements
int capacity; // Maximum capacity of the deque
int front; // Index of the front element
int rear; // Index of the rear element
int size; // Current size of the deque
public:
// Constructor
Deque(int capacity) {
this->capacity = capacity;
arr = new int[capacity];
front = -1;
rear = 0;
size = 0;
}
// Destructor
~Deque() {
delete[] arr;
}
// Check if deque is full
bool isFull() {
return ((front == 0 && rear == capacity - 1) || front == rear + 1);
}
// Check if deque is empty
bool isEmpty() {
return (front == -1);
}
// Insert at the front
void insertFront(int x) {
// Check if deque is full
if (isFull()) {
cout << "Deque Overflow" << endl;
return;
}
// If deque is empty
if (front == -1) {
front = 0;
rear = 0;
}
// If front is at the beginning of the array
else if (front == 0) {
front = capacity - 1;
}
// Normal case
else {
front--;
}
arr[front] = x;
size++;
cout << x << " inserted at the front" << endl;
}
// Insert at the rear
void insertRear(int x) {
// Check if deque is full
if (isFull()) {
cout << "Deque Overflow" << endl;
return;
}
// If deque is empty
if (front == -1) {
front = 0;
rear = 0;
}
// If rear is at the end of the array
else if (rear == capacity - 1) {
rear = 0;
}
// Normal case
else {
rear++;
}
arr[rear] = x;
size++;
cout << x << " inserted at the rear" << endl;
}
// Delete from the front
int deleteFront() {
// Check if deque is empty
if (isEmpty()) {
cout << "Deque Underflow" << endl;
return -1;
}
int x = arr[front];
// If there is only one element
if (front == rear) {
front = -1;
rear = -1;
}
// If front is at the end of the array
else if (front == capacity - 1) {
front = 0;
}
// Normal case
else {
front++;
}
size--;
return x;
}
// Delete from the rear
int deleteRear() {
// Check if deque is empty
if (isEmpty()) {
cout << "Deque Underflow" << endl;
return -1;
}
int x = arr[rear];
// If there is only one element
if (front == rear) {
front = -1;
rear = -1;
}
// If rear is at the beginning of the array
else if (rear == 0) {
rear = capacity - 1;
}
// Normal case
else {
rear--;
}
size--;
return x;
}
// Get the front element
int getFront() {
if (isEmpty()) {
cout << "Deque is empty" << endl;
return -1;
}
return arr[front];
}
// Get the rear element
int getRear() {
if (isEmpty() || rear < 0) {
cout << "Deque is empty" << endl;
return -1;
}
return arr[rear];
}
// Get the size of the deque
int getSize() {
return size;
}
// Display deque elements
void display() {
if (isEmpty()) {
cout << "Deque is empty" << endl;
return;
}
cout << "Deque elements: ";
int i = front;
while (true) {
cout << arr[i] << " ";
if (i == rear) {
break;
}
i = (i + 1) % capacity;
}
cout << endl;
}
};
int main() {
Deque dq(5);
dq.insertFront(10);
dq.insertRear(20);
dq.insertFront(30);
dq.insertRear(40);
dq.display();
cout << "Front element: " << dq.getFront() << endl;
cout << "Rear element: " << dq.getRear() << endl;
cout << dq.deleteFront() << " deleted from the front" << endl;
cout << dq.deleteRear() << " deleted from the rear" << endl;
dq.display();
cout << "Deque size: " << dq.getSize() << endl;
return 0;
}
Applications of Deque
- Undo Operations: Deques can be used to implement undo operations in applications.
- Job Scheduling: In job scheduling algorithms, deques can be used to efficiently manage jobs with different priorities.
- Web Browser History: Deques can be used to implement the forward and backward navigation in web browsers.
- Palindrome Checking: Deques can be used to check if a string is a palindrome.
Applications of Queues
Queues have numerous applications in computer science and real-world scenarios. Let's explore some of the most common ones:
1. Applications in Scheduling
Queues are widely used in various scheduling algorithms:
CPU Scheduling
In operating systems, queues are used to manage processes waiting for CPU time. Different scheduling algorithms use different types of queues:
- First-Come, First-Served (FCFS): Uses a simple queue where processes are executed in the order they arrive.
- Round Robin: Uses a circular queue where each process gets a fixed time slice.
- Priority Scheduling: Uses a priority queue where processes with higher priority are executed first.
- Multilevel Queue: Uses multiple queues for different types of processes.
Disk Scheduling
Queues are used to manage disk I/O requests. Different disk scheduling algorithms use different types of queues to optimize disk access time.
Job Scheduling
In batch processing systems, queues are used to manage jobs waiting to be processed. Jobs are typically processed in the order they are submitted (FIFO).
2. Other Applications
Breadth-First Search
Queues are used in the implementation of breadth-first search algorithm for traversing or searching tree or graph data structures.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Graph represented as an adjacency list
class Graph {
private:
int V; // Number of vertices
vector> adj; // Adjacency list
public:
Graph(int V) {
this->V = V;
adj.resize(V);
}
// Add an edge to the graph
void addEdge(int v, int w) {
adj[v].push_back(w);
}
// Breadth-First Search traversal
void BFS(int s) {
// Mark all vertices as not visited
vector visited(V, false);
// Create a queue for BFS
queue q;
// Mark the current node as visited and enqueue it
visited[s] = true;
q.push(s);
cout << "Breadth-First Search starting from vertex " << s << ": ";
while (!q.empty()) {
// Dequeue a vertex from queue and print it
s = q.front();
cout << s << " ";
q.pop();
// Get all adjacent vertices of the dequeued vertex s
// If an adjacent has not been visited, mark it visited and enqueue it
for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
q.push(*i);
}
}
}
cout << endl;
}
};
int main() {
// Create a graph
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
// Perform BFS traversal starting from vertex 0
g.BFS(0);
return 0;
}
Print Queue Management
In printer spooling, documents are printed in the order they are submitted. A queue is used to manage the print jobs.
Message Queues
In inter-process communication, message queues are used to pass messages between processes. Messages are typically processed in the order they are received.
Buffer for Devices
Queues are used as buffers for devices like keyboards. Characters are stored in the order they are typed and processed in the same order.
Traffic Management
In traffic management systems, queues are used to manage vehicles at traffic signals, toll booths, etc.
Customer Service
In customer service systems, queues are used to manage customer requests. Customers are typically served in the order they arrive.
Summary
In this section, we covered queues, a fundamental data structure in computer science:
- Concept of queues and their FIFO (First In First Out) property
- Primitive operations on queues: enqueue, dequeue, front, isEmpty, isFull, size
- Queue as an Abstract Data Type (ADT)
- Implementation of queues using arrays
- Circular queues and their implementation
- Double-ended queues (deques) and their implementation
- Applications of queues in scheduling and other areas
Queues are versatile data structures with numerous applications in computer science and real-world scenarios. Understanding queues is essential for solving many algorithmic problems and implementing various features in software applications.
Practice Questions
- Implement a queue using a linked list in C++.
- Write a C++ program to reverse the first k elements of a queue.
- Implement a queue using two stacks.
- Write a C++ program to implement a priority queue.
- Implement a function to check if a queue can be sorted into another queue using a stack.
- Write a C++ program to implement a sliding window maximum using a deque.
- Implement a function to interleave the first half of the queue with the second half.
- Write a C++ program to implement a queue that supports getMin() operation in O(1) time.
- Implement a function to reverse a queue using recursion.
- Write a C++ program to implement a circular tour problem (find the first petrol pump from where a circular tour is possible).
Next Steps
Now that you understand queues and their applications, you're ready to learn about another important data structure: linked lists.
Continue to the next section: Linked Lists