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.
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.
Implementation of Circular Queue using LL in C++
#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; }
Output:
10 20 30 40 50 60 20 30 40 50 60
Further Reading: