Queues are a fundamental data structure in computer science, widely used in various applications such as scheduling tasks, managing resources, and handling asynchronous data. A queue operates on a First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed. However, there are different types of queues designed to address specific needs. In this blog post, we will delve into the various types of queues, including simple queues, circular queues, priority queues, and deques, along with relevant examples.
Simple Queue
A simple queue, also known as a linear queue, is the most basic form of a queue. It follows the FIFO principle where elements are added at the rear and removed from the front.
Characteristics
- Insertion (Enqueue): Occurs at the rear end.
- Deletion (Dequeue): Occurs at the front end.
- Overflow: Happens when the queue is full.
- Underflow: Happens when attempting to dequeue from an empty queue.
Example
Consider a ticket counter where people line up to buy tickets. The first person in line is the first one to get the ticket and leave the queue, followed by the second person, and so on.
Python Example:
Python
class SimpleQueue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
return "Queue is empty"
def is_empty(self):
return len(self.queue) == 0
def display(self):
return self.queue
# Usage
queue = SimpleQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.display()) # Output: [1, 2, 3]
print(queue.dequeue()) # Output: 1
print(queue.display()) # Output: [2, 3]C Example:
C
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if (rear == SIZE - 1)
printf("Queue is Full\n");
else {
if (front == -1) front = 0;
rear++;
items[rear] = value;
printf("Inserted %d\n", value);
}
}
int dequeue() {
if (front == -1) {
printf("Queue is Empty\n");
return -1;
} else {
int item = items[front];
front++;
if (front > rear) front = rear = -1;
return item;
}
}
int main() {
enqueue(1);
enqueue(2);
printf("Deleted %d\n", dequeue());
printf("Deleted %d\n", dequeue());
printf("Deleted %d\n", dequeue());
return 0;
}C++ Example:
C++
#include <iostream>
#define SIZE 5
class Queue {
int items[SIZE], front, rear;
public:
Queue() : front(-1), rear(-1) {}
void enqueue(int value) {
if (rear == SIZE - 1)
std::cout << "Queue is Full\n";
else {
if (front == -1) front = 0;
items[++rear] = value;
std::cout << "Inserted " << value << std::endl;
}
}
int dequeue() {
if (front == -1) {
std::cout << "Queue is Empty\n";
return -1;
} else {
int item = items[front];
if (front >= rear)
front = rear = -1;
else
front++;
return item;
}
}
};
int main() {
Queue q;
q.enqueue(1);
q.enqueue(2);
std::cout << "Deleted " << q.dequeue() << std::endl;
std::cout << "Deleted " << q.dequeue() << std::endl;
std::cout << "Deleted " << q.dequeue() << std::endl;
return 0;
}Java Example:
Java
import java.util.LinkedList;
import java.util.Queue;
public class SimpleQueue {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(1);
System.out.println("Inserted 1");
q.add(2);
System.out.println("Inserted 2");
System.out.println("Deleted " + q.poll());
System.out.println("Deleted " + q.poll());
System.out.println("Deleted " + q.poll());
}
}JavaScript Example:
JavaScript
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
console.log(`Inserted ${element}`);
}
dequeue() {
if (this.items.length === 0) {
return "Queue is Empty";
}
return this.items.shift();
}
}
let q = new Queue();
q.enqueue(1);
q.enqueue(2);
console.log(`Deleted ${q.dequeue()}`);
console.log(`Deleted ${q.dequeue()}`);
console.log(`Deleted ${q.dequeue()}`);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. This allows for efficient utilization of space as it overcomes the limitation of the simple queue where the space at the front is wasted after dequeuing.
Characteristics
- Insertion and Deletion: Elements are added and removed in a circular manner.
- Efficient Space Utilization: No memory wastage as in the simple queue.
- Overflow Condition: Occurs when the queue is full.
- Underflow Condition: Occurs when the queue is empty.
Example
Circular queues are useful in buffering systems where memory needs to be reused, such as in streaming applications.
Python Example:
Python
class CircularQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = self.rear = -1
def enqueue(self, item):
if (self.rear + 1) % self.size == self.front:
return "Queue is full"
elif self.front == -1:
self.front = 0
self.rear = 0
self.queue[self.rear] = item
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = item
def dequeue(self):
if self.front == -1:
return "Queue is empty"
elif self.front == self.rear:
temp = self.queue[self.front]
self.front = self.rear = -1
return temp
else:
temp = self.queue[self.front]
self.front = (self.front + 1) % self.size
return temp
def display(self):
if self.front == -1:
return "Queue is empty"
elif self.rear >= self.front:
return self.queue[self.front:self.rear + 1]
else:
return self.queue[self.front:] + self.queue[:self.rear + 1]
# Usage
c_queue = CircularQueue(5)
c_queue.enqueue(1)
c_queue.enqueue(2)
c_queue.enqueue(3)
print(c_queue.display()) # Output: [1, 2, 3]
c_queue.dequeue()
print(c_queue.display()) # Output: [2, 3]C Example:
C
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if ((rear + 1) % SIZE == front)
printf("Queue is Full\n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = value;
printf("Inserted %d\n", value);
}
}
int dequeue() {
if (front == -1) {
printf("Queue is Empty\n");
return -1;
} else {
int item = items[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
return item;
}
}
int main() {
enqueue(1);
enqueue(2);
printf("Deleted %d\n", dequeue());
printf("Deleted %d\n", dequeue());
printf("Deleted %d\n", dequeue());
return 0;
}C++ Example:
C++
#include <iostream>
#define SIZE 5
class CircularQueue {
int items[SIZE], front, rear;
public:
CircularQueue() : front(-1), rear(-1) {}
void enqueue(int value) {
if ((rear + 1) % SIZE == front)
std::cout << "Queue is Full\n";
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = value;
std::cout << "Inserted " << value << std::endl;
}
}
int dequeue() {
if (front == -1) {
std::cout << "Queue is Empty\n";
return -1;
} else {
int item = items[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
return item;
}
}
};
int main() {
CircularQueue q;
q.enqueue(1);
q.enqueue(2);
std::cout << "Deleted " << q.dequeue() << std::endl;
std::cout << "Deleted " << q.dequeue() << std::endl;
std::cout << "Deleted " << q.dequeue() << std::endl;
return 0;
}Java Example:
Java
class CircularQueue {
private int size, front, rear;
private int[] queue;
public CircularQueue(int size) {
this.size = size;
this.queue = new int[size];
this.front = this.rear = -1;
}
public void enqueue(int value) {
if ((rear + 1) % size == front) {
System.out.println("Queue is Full");
} else {
if (front == -1) front = 0;
rear = (rear + 1) % size;
queue[rear] = value;
System.out.println("Inserted " + value);
}
}
public int dequeue() {
if (front == -1) {
System.out.println("Queue is Empty");
return -1;
} else {
int item = queue[front];
if (front == rear) front = rear = -1;
else front = (front + 1) % size;
return item;
}
}
public static void main(String[] args) {
CircularQueue q = new CircularQueue(5);
q.enqueue(1);
q.enqueue(2);
System.out.println("Deleted " + q.dequeue());
System.out.println("Deleted " + q.dequeue());
System.out.println("Deleted " + q.dequeue());
}
}JavaScript Example:
JavaScript
class CircularQueue {
constructor(size) {
this.size = size;
this.queue = new Array(size);
this.front = this.rear = -1;
}
enqueue(element) {
if ((this.rear + 1) % this.size === this.front) {
console.log("Queue is Full");
} else {
if (this.front === -1) this.front = 0;
this.rear = (this.rear + 1) % this.size;
this.queue[this.rear] = element;
console.log(`Inserted ${element}`);
}
}
dequeue() {
if (this.front === -1) {
return "Queue is Empty";
} else {
const item = this.queue[this.front];
if (this.front === this.rear) {
this.front = this.rear = -1;
} else {
this.front = (this.front + 1) % this.size;
}
return item;
}
}
}
let q = new CircularQueue(5);
q.enqueue(1);
q.enqueue(2);
console.log(`Deleted ${q.dequeue()}`);
console.log(`Deleted ${q.dequeue()}`);
console.log(`Deleted ${q.dequeue()}`);Priority Queue
A priority queue is a type of queue where each element is associated with a priority, and elements are dequeued in order of their priority. Elements with higher priority are dequeued before elements with lower priority.
Characteristics
- Priority-Based Deletion: Elements are dequeued based on priority rather than arrival order.
- Efficient Retrieval: Allows for quick access to the highest-priority element.
- Use Cases: Scheduling algorithms, Dijkstra’s shortest path algorithm.
Example
Priority queues are widely used in operating systems for task scheduling where some tasks have higher priority than others.
Python Example:
Python
import heapq
class PriorityQueue:
def __init__(self):
self.queue = []
def enqueue(self, item, priority):
heapq.heappush(self.queue, (priority, item))
def dequeue(self):
if not self.is_empty():
return heapq.heappop(self.queue)[1]
return "Queue is empty"
def is_empty(self):
return len(self.queue) == 0
def display(self):
return [item[1] for item in self.queue]
# Usage
p_queue = PriorityQueue()
p_queue.enqueue("Task1", 2)
p_queue.enqueue("Task2", 1)
p_queue.enqueue("Task3", 3)
print(p_queue.display()) # Output: ['Task2', 'Task1', 'Task3']
print(p_queue.dequeue()) # Output: 'Task2'
print(p_queue.display()) # Output: ['Task1', 'Task3']C++ Example:
C++
#include <iostream>
#include <queue>
#include <vector>
class PriorityQueue {
public:
void enqueue(int value) {
pq.push(value);
std::cout << "Inserted " << value << std::endl;
}
int dequeue() {
if (pq.empty()) {
std::cout << "Queue is Empty\n";
return -1;
} else {
int value = pq.top();
pq.pop();
return value;
}
}
private:
std::priority_queue<int> pq;
};
int main() {
PriorityQueue pq;
pq.enqueue(10);
pq.enqueue(30);
pq.enqueue(20);
std::cout << "Deleted " << pq.dequeue() << std::endl;
std::cout << "Deleted " << pq.dequeue() << std::endl;
std::cout << "Deleted " << pq.dequeue() << std::endl;
return 0;
}Java Example:
Java
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
System.out.println("Inserted 10");
pq.add(30);
System.out.println("Inserted 30");
pq.add(20);
System.out.println("Inserted 20");
System.out.println("Deleted " + pq.poll());
System.out.println("Deleted " + pq.poll());
System.out.println("Deleted " + pq.poll());
}
}JavaScript Example:
JavaScript
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(element) {
if (this.isEmpty()) {
this.queue.push(element);
} else {
let added = false;
for (let i = 0; i < this.queue.length; i++) {
if (element < this.queue[i]) {
this.queue.splice(i, 0, element);
added = true;
break;
}
}
if (!added) {
this.queue.push(element);
}
}
console.log(`Inserted ${element}`);
}
dequeue() {
if (this.isEmpty()) {
return "Queue is Empty";
}
return this.queue.shift();
}
isEmpty() {
return this.queue.length === 0;
}
}
let pq = new PriorityQueue();
pq.enqueue(10);
pq.enqueue(30);
pq.enqueue(20);
console.log(`Deleted ${pq.dequeue()}`);
console.log(`Deleted ${pq.dequeue()}`);
console.log(`Deleted ${pq.dequeue()}`);Deque (Double-Ended Queues)
A deque (pronounced “deck”) is a queue where insertion and deletion can occur at both ends. This flexibility allows it to be used as both a queue and a stack.
Characteristics
- Insertion/Deletion at Both Ends: Elements can be added or removed from both front and rear.
- Flexible Operations: Supports all operations of both stacks and queues.
- Use Cases: Implementing algorithms like the sliding window technique, palindromes checking.
Example
Deques are useful in applications where elements need to be processed from both ends, such as in certain parsing algorithms.
Python Example:
Python
class Deque:
def __init__(self):
self.deque = []
def add_front(self, item):
self.deque.insert(0, item)
def add_rear(self, item):
self.deque.append(item)
def remove_front(self):
if not self.is_empty():
return self.deque.pop(0)
return "Deque is empty"
def remove_rear(self):
if not self.is_empty():
return self.deque.pop()
return "Deque is empty"
def is_empty(self):
return len(self.deque) == 0
def display(self):
return self.deque
# Usage
deque = Deque()
deque.add_rear(1)
deque.add_rear(2)
deque.add_front(3)
deque.add_front(4)
print(deque.display()) # Output: [4, 3, 1, 2]
print(deque.remove_front()) # Output: 4
print(deque.display()) # Output: [3, 1, 2]
print(deque.remove_rear()) # Output: 2
print(deque.display()) # Output: [3, 1]C++ Example:
C++
#include <iostream>
#include <deque>
class Deque {
public:
void addFront(int value) {
dq.push_front(value);
std::cout << "Inserted " << value << " at front\n";
}
void addRear(int value) {
dq.push_back(value);
std::cout << "Inserted " << value << " at rear\n";
}
int removeFront() {
if (dq.empty()) {
std::cout << "Deque is Empty\n";
return -1;
} else {
int value = dq.front();
dq.pop_front();
return value;
}
}
int removeRear() {
if (dq.empty()) {
std::cout << "Deque is Empty\n";
return -1;
} else {
int value = dq.back();
dq.pop_back();
return value;
}
}
private:
std::deque<int> dq;
};
int main() {
Deque dq;
dq.addFront(10);
dq.addRear(20);
dq.addFront(5);
std::cout << "Removed from front: " << dq.removeFront() << std::endl;
std::cout << "Removed from rear: " << dq.removeRear() << std::endl;
std::cout << "Removed from front: " << dq.removeFront() << std::endl;
return 0;
}Java Example:
Java
import java.util.Deque;
import java.util.LinkedList;
public class DequeExample {
public static void main(String[] args) {
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(10);
System.out.println("Inserted 10 at front");
deque.addLast(20);
System.out.println("Inserted 20 at rear");
deque.addFirst(5);
System.out.println("Inserted 5 at front");
System.out.println("Removed from front: " + deque.removeFirst());
System.out.println("Removed from rear: " + deque.removeLast());
System.out.println("Removed from front: " + deque.removeFirst());
}
}JavaScript Example:
JavaScript
class Deque {
constructor() {
this.items = [];
}
addFront(element) {
this.items.unshift(element);
console.log(`Inserted ${element} at front`);
}
addRear(element) {
this.items.push(element);
console.log(`Inserted ${element} at rear`);
}
removeFront() {
if (this.isEmpty()) {
return "Deque is Empty";
}
return this.items.shift();
}
removeRear() {
if (this.isEmpty()) {
return "Deque is Empty";
}
return this.items.pop();
}
isEmpty() {
return this.items.length === 0;
}
}
let dq = new Deque();
dq.addFront(10);
dq.addRear(20);
dq.addFront(5);
console.log(`Removed from front: ${dq.removeFront()}`);
console.log(`Removed from rear: ${dq.removeRear()}`);
console.log(`Removed from front: ${dq.removeFront()}`);
Conclusion
Understanding the different types of queues and their applications is essential for efficient problem-solving in computer science. Simple queues are straightforward but can lead to inefficient space utilization, which is addressed by circular queues.
Priority queues allow for element processing based on importance, and deques offer the most flexibility with operations on both ends. Each type of queue has its unique advantages and is suited to specific use cases, making them indispensable tools in the world of data structures and algorithms.
Queues are versatile data structures with several variations to suit different needs:
- Simple Queue: Follows the FIFO principle.
- Circular Queue: Efficiently utilizes space by connecting the end to the front.
- Priority Queue: Elements are dequeued based on priority.
- Deque: Allows insertion and deletion from both ends.
Understanding these types and their implementations in various programming languages helps in choosing the right type of queue for specific applications.
Discover more from lounge coder
Subscribe to get the latest posts sent to your email.
