Queue

• A queue can be defined as an ordered list

which enables insert operations to be
performed at one end called REAR and
delete operations to be performed at
another end called FRONT.

• Queue is referred to be as First In First Out

list.
 LINEAR QUEUE IMPLEMENTATION USING ARRAY
#include <iostream> bool isEmpty()
using namespace std; {
class Queue return front == rear;
{ }
private: bool isFull()
int size; {
int front; return rear == size;
int rear; }
int *arr;
public: void enqueue(int val)
Queue(int size) {
{ if (isFull())
this-> size = size; {
this-> front = 0; cout << "This Queue is full" << endl;
this-> rear = 0; }
arr = new int[size]; else
} {
arr[rear++] = val;
~Queue() cout << "Enqueued element: " << val << endl;
{ }
delete[] arr; }
}
 int dequeue() cout << "Dequeuing element: " << q.dequeue() << endl;
{
if (isEmpty()) cout << "Dequeuing element: " << q.dequeue() << endl;
{
cout << "This Queue is empty" << endl; cout << "Dequeuing element: " << q.dequeue() << endl;
return -1;
} q.enqueue(45);
else q.enqueue(45);
{ q.enqueue(45);
return arr[front++];
}
} return 0;
}; }
int main()
{
Queue q(4);
q.enqueue(12);
q.enqueue(15);
q.enqueue(1);
OUTPUT:
Enqueued element: 12
Enqueued element: 15
Enqueued element: 1
Dequeuing element: 12
Dequeuing element: 15
Dequeuing element: 1
Enqueued element: 45
This Queue is full
This Queue is full
Circular
Queue
• In Circular Queue, all the nodes are represented
as circle-like structure.
• It is similar to the linear Queue except that the
last element of the queue is connected to the
first element.
• It is also known as Ring Buffer as all the ends
are connected to another end.
LIMITATIONS OF LINEAR QUEUE

• The drawback that occurs in a linear queue

is overcome by using the circular queue.

• If the empty space is available in a circular

queue, the new element can be added in
an empty space by simply incrementing the
value of rear.

• 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.
 CIRCULAR QUEUE IMPLEMENTATION USING ARRAY
#include <iostream> //Function to create Circular queue
using namespace std; void Queue::enQueue(int value)
{
class Queue if ((front == 0 && rear == size - 1) || ((rear + 1) % size == front))
{ {
int rear, front; cout<<"Queue is Full“<<endl;
int size; return;
int *arr; }
public: else if (front == -1) /* Insert First Element */
Queue(int s) {
{ front = rear = 0;
front = rear = -1; arr[rear] = value;
size = s; }
arr = new int[s];
} else if (rear == size - 1 && front != 0)
{
void enQueue(int value); rear = 0;
arr[rear] = value;
int deQueue(); }
void displayQueue(); else{
}; rear++;
arr[rear] = value;
}
}
// Function to delete element from Circular Queue // Function displaying the elements of Circular Queue
int Queue::deQueue() void Queue::displayQueue()
{ {
if (front == -1) if (front == -1)
{ {
cout<<"Queue is Empty"; cout<<"Queue is Empty";
return -1; return;
} }
int data = arr[front]; cout<<"Elements in Circular Queue are: ";
arr[front] = -1;
if (rear >= front)
if (front == rear) {
{ for (int i = front; i <= rear; i++)
front = -1; cout<<arr[i]<<“ “;
rear = -1; }
} else
else if (front == size - 1){ {
front = 0; for (int i = front; i < size; i++)
} cout<<arr[i]<<“ “;
else
front++; for (int i = 0; i <= rear; i++)
cout<<arr[i]<<“ “;
return data; }
} }
int main() cout<<"Deleted value = “<< q.deQueue()<<endl;
{
Queue q(5); q.displayQueue();
// Inserting elements in Circular Queue return 0;
q.enQueue(14); }
q.enQueue(22);
q.enQueue(13); OUTPUT:
q.enQueue(-6);
Elements in Circular Queue are: 14 22 13 -6
// Display elements present in Circular Queue
q.displayQueue(); Deleted value = 14
Deleted value = 22
// Deleting elements from Circular Queue Elements in Circular Queue are: 13 -6
cout<<"Deleted value = "<<q.deQueue()<<endl;
cout<<"Deleted value = "<<q.deQueue()<<endl; Elements in Circular Queue are: 13 -6 9 20 5
Queue is Full
q.displayQueue(); Deleted value = 13
q.enQueue(9); Elements in Circular Queue are: -6 9 20 5
q.enQueue(20);
q.enQueue(5);
q.displayQueue();
q.enQueue(20);
 CIRCULAR QUEUE IMPLEMENTATION USING LINKED LIST
#include <iostream> public:
using namespace std; CircularQueue() {
front = rear = nullptr; // Initialize an empty queue
class Node { }
public: ~CircularQueue() {
int data; while (!isEmpty()) {
Node* next; dequeue();
}
Node(int val) { }
data = val;
next = nullptr;
} bool isEmpty() {
}; return front == nullptr; // Queue is empty if front is null
}
class CircularQueue {
private:
Node* front; // Points to the front of the queue
Node* rear; // Points to the rear of the queue
void enqueue(int val) { void dequeue() {
Node* newNode = new Node(val); if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl;
if (isEmpty()) { return;
front = rear = newNode; }
rear->next = front; // Circular link
} Node* temp = front;
else { int removedValue = front->data;
rear->next = newNode;
rear = newNode; if (front == rear) {
rear->next = front; // Maintain circularity front = rear = nullptr; // Single element
} }
cout << "Enqueued: " << val << endl; else {
} front = front->next;
rear->next = front; // Maintain circularity
}
delete temp;

cout << "Dequeued: " << removedValue << endl;

}
void displayQueue() const { q.enqueue(10);
if (isEmpty()) { q.enqueue(20);
cout << "Queue is empty." << endl; q.enqueue(30);
return;
} q.displayQueue();

cout << "Queue elements: "; q.dequeue();

Node* temp = front;
do { q.enqueue(40);
cout << temp->data << " "; q.enqueue(50);
temp = temp->next; q.displayQueue();
}
while (temp != front); q.dequeue();
cout << endl; q.dequeue();
} q.displayQueue();
};
return 0;
int main() { }
CircularQueue q;
OUTPUT:
Queue elements: 10 20 30
Dequeued: 10
Enqueued: 40
Enqueued: 50
Queue elements: 20 30 40 50
Dequeued: 20
Dequeued: 30
Queue elements: 40 50
Dequeued: 40
Dequeued: 50