Queue using Circular Linked List in C++
Hi GuyZ,
Queue is another important data structure which follows FIFO (First In First Out) method. Implementing queue using Circular Linked List is best practicing method. Unlike implementing SLL, CLL is better choice because CLL allows store address of first node at last nodes link.
By implementing Queue using CLL, we need to keep track of any of nodes, that is first or last to track full Queue. The better choice is to track last node because last node holds the link to first node. So by tracking last node we can access last and first nodes fast, ie, first_node = last_node->link. While tracking first node, we need to traverse until last node get the last node. ie,
If you are tracking first node you have to follow above steps to get last node. But while tracking last node, get the first node is very easy.
Queue is another important data structure which follows FIFO (First In First Out) method. Implementing queue using Circular Linked List is best practicing method. Unlike implementing SLL, CLL is better choice because CLL allows store address of first node at last nodes link.
By implementing Queue using CLL, we need to keep track of any of nodes, that is first or last to track full Queue. The better choice is to track last node because last node holds the link to first node. So by tracking last node we can access last and first nodes fast, ie, first_node = last_node->link. While tracking first node, we need to traverse until last node get the last node. ie,
tmp = first_node;
while(tmp->link!=first_node){
tmp = tmp->link;
}
last_node = tmp;
If you are tracking first node you have to follow above steps to get last node. But while tracking last node, get the first node is very easy.
Source Code
#include <iostream>
using namespace std;
/*
Queue Implementation using Circular Linked List (CLL)
Coded By Ajith Kp (C) http://www.terminalcoders.blogspot.com
*/
struct node
{
int data;
node *link = NULL;
};
class Queue{
node *end;
public:
Queue(){
end = NULL;
}
void menu(){
int op = 0;
cout<<"\t\t\tMENU\n1. Enqueue\n2. Dequeue\n3. Show\n4. Exit";
while(op!=4){
cout<<"\nOption: ";
cin>>op;
switch(op){
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
show();
break;
case 4:
break;
default:
cout<<"Error: Try again..";
break;
}
}
}
void enqueue(){
node *nn = new node;
cout<<"Enter data: ";
cin>>nn->data;
if(end==NULL){
end = nn;
end->link=nn;
}
else{
nn->link = end->link;
end->link = nn;
end = nn;
}
cout<<"Data "<<nn->data<<" is added to queue...";
}
void dequeue(){
node *nn;
if(end==NULL){
cout<<"Error: Queue is empty...";
}
else{
nn=end->link;
if(end->link==end){
end=NULL;
}
else{
end->link = nn->link;
}
cout<<"Data: "<<nn->data<<" is deleted from Queue...";
delete(nn);
}
}
void show(){
node *tmp;
cout<<"Queue: ";
if(end){
tmp = end->link;
cout<<tmp->data<<" ";
tmp = tmp->link;
while(tmp!=end->link){
cout<<tmp->data<<" ";
tmp=tmp->link;
}
}
else{
cout<<"Empty...";
}
}
};
int main(){
Queue q;
q.menu();
return 0;
}
