#### Stacks & Queues

Problem
Implement a circular queue using linked list.
Circular queue is the one in which rear node has a link to the front node.

Solution
We implement the queue in such a manner that next of rear always points to the front node.
The pointers are updated during the enqueue and dequeue operations.
See the implementation below.

```#include<iostream>
using namespace std;

// structure of a circular queue node
typedef struct cqueue_node {
int data;
struct cqueue_node *next;
}node;

// declare the circular queue data structure
class cqueue {
private :
// pointers to front and rear element
node *front, *rear;
public :
cqueue() {
front = rear = NULL;
}
void enqueue(int element); // insert an element
int dequeue(); // removes the front element
void displayCQueue(); // display the circular queue
};

// enqueue an element to the circular queue
void cqueue :: enqueue(int element) {
node *new_element = new node;
new_element->data = element;
new_element->next = NULL;
if (front == NULL) {
front = rear = new_element;
}
else {
// next of rear is front in circular queue
rear->next = new_element;
rear = new_element;
}
rear->next = front;
}

// dequeue front element from circular queue
int cqueue :: dequeue() {
int element;
if (front == NULL) {
return -99999; //for empty queue
}
else if (front == rear) {
// only 1 node in circular queue
element = front->data;
delete front;
front = rear = NULL;
}
else {
node *ptr = front;
element = ptr->data;
front = front->next;
// next of rear is front in circular queue
rear->next = front;
delete ptr;
}
return element;
}

// display all the elements of the circular queue
void cqueue :: displayCQueue() {
node *ptr = front;
cout<<"\nCircular Queue \n";
do {
cout<<ptr->data<<" ";
ptr = ptr->next;
} while (ptr != front);
}

// main
int main() {
cqueue cq;
cq.enqueue(5);
cq.enqueue(18);
cq.enqueue(11);
cq.enqueue(7);
cq.enqueue(13);
cq.enqueue(9);
cq.displayCQueue();
int dq_element = cq.dequeue();
cout<<"\nDequeued element :: "<<dq_element;
cout<<"\nAfter dequeueing :-";
cq.displayCQueue();
cout<<endl;
return 0;
}```