In this chapter we shall learn about below topics:
10.1 Introduction to Circular Queue Data Structure
10.2 Implementation of Circular Queue
10.3 Implementation of Circular Queue using Linked List
10.4 Output
10.1 Introduction to Circular Queue Data Structure
In the previous chapter we have seen the implementation of Circular Queue using arrays. In this chapter we shall see how to implement Circular Queue using Circular Singly Linked List.
10.2. Implementation of Circular Queue
As we are using circular singly linked list, there is no need to compute the index where the element should be inserted.
But here we need to take 2 pointers, “front” and “rear”.
“front” pointer will always point at the beginning of LL. This pointer will be used to delete the element.
“rear” pointer will always point at the end of LL. This pointer will be used to insert an element.
Insertion [enqueue] operation can be visualized as below:
As you can see from the image above, we increase the rear pointer and keep the front pointer still, while we are inserting the elements.
Deletion [dequeue] operation can be visualized as below:
As you can see from the above image, we increase the front pointer and keep the rear pointer still, while we are deleting the elements.
As we are using 2 pointers, we don’t need to compute the index to be inserted, like we did in the array implementation.
10.3. Implementation of Circular Queue using Linked List
#include<iostream>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *front = NULL;
Node *rear = NULL;
void enqueue(int val)
{
if(front==NULL || rear==NULL)
{
//create a new node
Node *newNode;
newNode = new Node;
newNode->data = val;
newNode->next = NULL;
//as it is single node, both pointers
//point to the same node
front = newNode;
rear = newNode;
}
else
{
Node *newNode;
newNode = new Node;
newNode->data = val;
rear->next = newNode;
newNode->next = front;
rear = newNode;
}
}
void dequeue()
{
Node *n;
n = front;
front = front->next;
delete(n);
}
void display()
{
Node *ptr;
ptr = front;
do
{
cout<< ptr->data <<" ";
ptr = ptr->next;
}while(ptr != rear->next);
cout<<endl;
cout<<endl;
}
int main(void)
{
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
enqueue(60);
display();
dequeue();
display();
return 0;
}10.4 Output
10 20 30 40 50 60
20 30 40 50 60