Hot Topics
Data Structure
Circular Queue using Linked List
Algorithm
Create a class called Node which will have the data members of linked list
Create a class called CircularQueue which will make an array of node type
push() – To push element in circular queue there might be two cases
When the queue is empty add create a new Node and point the front pointer on the newly created node
When the queue has atleast one node present and the rear pointer is pointing on that node,create a new node and add the node right next to the node pointed by rear and reassign rear pointer to the newly created node.
pop() – To pop or remove an element from the front of queue we have three cases
If the queue is empty we cannot remove node from queue
If there is only a single node then remove that node and reassign front and rear to NULL
If there is more than one node get the value of the node denoted by the front pointer and transfer the front pointer to its next node before removing.
display() – To display attach another pointer to the front and print while traversing until that pointer reach the front pointer again.
getFront() – Get the node pointed by the front pointer
getRear() – Get the node pointed by the rear pointer
#include
// intializing the node of linked list
class Node
{
public:
int data;
Node *next;
Node(int d)
{
data = d;
next = NULL;
}
};
// intializing the queue
class Queue
{
public:
Node *front, *rear;
int size;
Queue()
{
front = rear = NULL;
size = 0;
}
// function to push nodes
void push(int val)
{
size++;
Node *newNode = new Node(val);
// if circular queue is empty
if (front == NULL)
{
front = newNode;
}
// if circular queue is not empty
else
{
rear->next = newNode;
}
rear = newNode;
rear->next = front;
std::cout << val << " is pushed to circular queue" << std::endl;
}
// function to remove nodes
void pop()
{
// if circular queue is empty
if (front == NULL)
{
std::cout << "The queue is empty" <data;
delete front;
front = rear = NULL;
std::cout << val << " is popped out from circular queue" <data;
front = front->next;
rear->next = front;
delete temp;
std::cout << val << " is popped out from circular queue" << std::endl;
}
// function to display nodes in queue
void display()
{
if (size == 0)
{
std::cout << "The queue is empty" << std::endl;
}
// attaching a temp pointer
Node *temp = front;
std::cout << "Displaying the elements in circular queue: " <next != front)
{
std::cout << " " <data;
temp = temp->next;
}
std::cout << " " <data;
std::cout << std::endl;
}
// function to get the front node
void getFront()
{
if (front == NULL)
{
std::cout << "The circular queue is empty" << std::endl;
}
std::cout << "The element at the front of circular queue is " <data << std::endl;
}
// function to get the rear node
void getRear()
{
if (front == NULL)
{
std::cout << "The circular queue is empty" << std::endl;
}
std::cout << "The element at the rear of circular queue is " <data << std::endl;
}
};
int main()
{
Queue q;
q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.display();
q.pop();
q.display();
q.getFront();
q.getRear();
return 0;
}
Output
10 is pushed to circular queue
20 is pushed to circular queue
30 is pushed to circular queue
40 is pushed to circular queue
Displaying the elements in circular queue:
10 20 30 40
10 is popped out from circular queue
Displaying the elements in circular queue:
20 30 40
The element at the front of circular queue is 20
The element at the rear of circular queue is 40
Automata Fixing