Introduction to Queue in Data Structures
A queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning
the element inserted first is removed first. It is analogous to a real-world queue, like a line of
people waiting at a ticket counter.
Characteristics of a Queue
1. FIFO Structure:
● Elements are added at one end (rear) and removed from the other end (front).
2. Dynamic Size: The size of a queue can grow or shrink dynamically, depending on the
type of implementation.
3. Restricted Operations:
● Enqueue: Insert an element at the rear.
● Dequeue: Remove an element from the front.
Queue Representation
A queue can be visualized as:
Front -> [10, 20, 30, 40] <- Rear
● The element 10 will be the first to leave the queue when dequeued.
● New elements are added at the rear.
Types of Queues
1. Simple Queue:
● Standard FIFO behavior.
● Elements are added at the rear and removed from the front.
2. Circular Queue:
● The last position is connected back to the first position to make the queue
circular.
● Overcomes the limitation of unused spaces in a simple queue.
3. Priority Queue:
● Elements are dequeued based on priority rather than their order in the queue.
4. Double-Ended Queue (Deque):
● Elements can be added or removed from both ends.
Queue Operations
1. Enqueue (Insert): Adds an element at the rear of the queue.
2. Dequeue (Delete): Removes the element from the front of the queue.
3. Peek/Front: Retrieves the front element without removing it.
4. isEmpty: Checks if the queue is empty.
5. isFull: Checks if the queue is full (for fixed-size queues).
Queue Implementation
Queues can be implemented in two ways:
1. Array-Based Implementation:
● Uses a fixed-size array.
● Simple but limited by the array size.
2. Linked List-Based Implementation:
● Dynamically resizable.
● More flexible than arrays.
Applications of Queues
1. Task Scheduling:
● Used in operating systems to manage processes and threads.
2. Data Transmission:
● Managing packets in network communication.
3. Customer Service:
● Handling customer requests in order of arrival.
4. Breadth-First Search (BFS):
● Queue is used to traverse graphs or trees in BFS.
5. Printer Spooling:
● Queues manage print jobs in order of arrival.
Queue - Array Implementation
#include <iostream>
using namespace std;
class myQueue {
// Array to store queue elements.
int *arr;
// Maximum number of elements the queue can hold.
int capacity;
// Current number of elements in the queue.
int size;
public:
myQueue(int c) {
capacity = c;
arr = new int[capacity];
size = 0;
}
bool isEmpty()
{
return size == 0;
}
bool isFull()
{
return size == capacity;
}
// Adds an element x at the rear of the queue.
void enqueue(int x)
{
if (isFull())
{
cout << "Queue is full!\n";
return;
}
arr[size] = x;
size++;
}
// Removes the front element of the queue.
void dequeue()
{
if (isEmpty())
{
cout << "Queue is empty!\n";
return;
}
for (int i = 1; i < size; i++)
{
arr[i - 1] = arr[i];
}
size--;
}
// Returns the front element of the queue.
int getFront()
{
if (isEmpty())
{
cout << "Queue is empty!\n";
return -1;
}
return arr[0];
}
// Return the last element of queue
int getRear()
{
if (isEmpty())
{
cout << "Queue is empty!" << endl;
return -1;
}
return arr[size - 1];
}
};
int main()
{
myQueue q(3);
[Link](10);
[Link](20);
[Link](30);
cout << "Front: " << [Link]() << endl;
[Link]();
cout << "Front: " << [Link]() << endl;
cout << "Rear: " << [Link]() << endl;
[Link](40);
return 0;
}
Output
Front: 10
Front: 20
Rear: 30
Queue - Linked List Implementation
A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The
element inserted first is the first one to be removed.
Declaration of Queue using Linked List
To implement a queue with a linked list, we maintain:
A Node structure/class that contains:
● data → to store the element.
● next → pointer/reference to the next node in the queue.
Two pointers/references:
● front → points to the first node (head of the queue).
● rear → points to the last node (tail of the queue).
Queue - Linked List Implementation
#include <iostream>
using namespace std;
// Node class
class Node {
public:
int data;
Node* next;
Node(int new_data) {
data = new_data;
next = nullptr;
}
};
// Queue class
class myQueue {
private:
int currSize;
Node* front;
Node* rear;
public:
myQueue() {
currSize = 0;
front = rear= nullptr;
}
// Check if empty
bool isEmpty() {
return front == nullptr;
}
// Enqueue
void enqueue(int new_data) {
Node* node = new Node(new_data);
if (isEmpty()) {
front = rear = node;
} else {
rear->next = node;
rear = node;
}
currSize++;
}
// Dequeue
int dequeue() {
if (isEmpty()) {
cout << "Queue Underflow" << endl;
return -1;
}
Node* temp = front;
int removedData = temp->data;
front = front->next;
if (front == nullptr) rear = nullptr;
delete temp;
currSize--;
return removedData;
}
// Get front element
int getfront() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return front->data;
}
// Get size
int size() {
return currSize;
}
};
int main() {
myQueue q;
[Link](10);
[Link](20);
cout << "Dequeue: " << [Link]() << "\n";
[Link](30);
cout << "Front: " << [Link]() << endl;
cout << "Size: " << [Link]() << endl;
return 0;
}
Output
Dequeue: 10
Front: 20
Size: 2
Circular Queue
A Circular Queue is a data structure that improves memory utilization by connecting the end
of the queue back to the front, forming a circle. Unlike a linear queue, it reuses empty spaces
left by dequeued elements, making it an efficient option for scenarios with fixed memory
size.
Features of Circular Queue
1. Circular Connection: The last position is connected to the first position.
2. Efficient Memory Utilization: Reuses vacant spaces after dequeue operations.
3. Two Pointers:
1. Front: Tracks the first element in the queue.
2. Rear: Tracks the last element in the queue.
4. Full Condition: When (rear + 1) % SIZE == front.
5. Empty Condition: When front == -1.
Operations in Circular Queue
1. Enqueue: Adds an element at the rear of the queue.
2. Dequeue: Removes an element from the front of the queue.
3. Peek: Retrieves the element at the front without removing it.
4. IsEmpty: Checks if the queue is empty.
5. IsFull: Checks if the queue is full.
6. Display: Shows all elements in the queue.
Declaration using Array:
In this implementation, arr is used to store elements. some variables are maintained:
● arr[] : array to store elements.
● capacity : maximum size of the queue.
● front : index of the front element.
● size : current number of elements in the queue.
Complete Implementation: Circular Queue
#include <iostream>
using namespace std;
class myQueue {
private:
// fixed-size array
int* arr;
// index of front element
int front;
// current number of elements
int size;
// maximum capacity
int capacity;
public:
myQueue(int cap) {
capacity = cap;
arr = new int[capacity];
front = 0;
size = 0;
}
// Insert an element at the rear
void enqueue(int x) {
if (size == capacity) {
cout << "Queue is full!" << endl;
return;
}
int rear = (front + size) % capacity;
arr[rear] = x;
size++;
}
// Remove an element from the front
int dequeue() {
if (size == 0) {
cout << "Queue is empty!" << endl;
return -1;
}
int res = arr[front];
front = (front + 1) % capacity;
size--;
return res;
}
// Get the front element
int getFront() {
if (size == 0) return -1;
return arr[front];
}
// Get the rear element
int getRear() {
if (size == 0) return -1;
int rear = (front + size - 1) % capacity;
return arr[rear];
}
};
int main() {
myQueue q(5);
[Link](10);
[Link](20);
[Link](30);
cout << [Link]() << " " << [Link]() << endl;
[Link]();
cout << [Link]() << " " << [Link]() << endl;
[Link](40);
cout << [Link]() << " " << [Link]() << endl;
return 0;
}
Output
10 30
20 30
20 40
De-queue and Priority Queue
De-Queue (Double-Ended Queue)
A De-Queue (Double-Ended Queue) is a type of queue where elements can be added or
removed from both the front and the rear. It is more flexible than a standard queue.
Types of De-Queue
1. Input-Restricted De-Queue: Insertion is allowed only at the rear, but deletion is
allowed at both ends.
2. Output-Restricted De-Queue: Deletion is allowed only at the front, but insertion is
allowed at both ends.
Operations in De-Queue
1. InsertFront: Adds an element at the front.
2. InsertRear: Adds an element at the rear.
3. DeleteFront: Removes an element from the front.
4. DeleteRear: Removes an element from the rear.
5. Display: Prints the elements of the De-Queue
Priority Queue
A Priority Queue is a special type of queue where elements are dequeued based on priority
rather than their insertion order. Each element has an associated priority, and the element
with the highest priority is served first.
Operations in Priority Queue
1. Insert: Adds an element based on its priority.
2. Delete: Removes the element with the highest priority.
3. Display: Shows the elements of the queue along with their priorities.