C plus plus program to implement circular queue using doubly linked list?

Answer 1

#include<iostream.h>

class node

{

public:

int data;

node* link;

};

class queue

{

node* front;

node* back;

public:

queue()

{

front=NULL;

back=NULL;

}

void enqueue(int d)

{

node* ptr;

ptr=new node;

ptr->data=d;

ptr->link=NULL;

if(front==NULL)

{

front=ptr;

back=ptr;

}

else

{

back->link=ptr;

back=back->link;

}

}

void dequeue()

{

node* ptr;

ptr=front;

if(front==NULL)

cout<<"\n Nothing can be deleted. \n";

else

{

ptr=front;

front=front->link;

delete ptr;

ptr=NULL;

cout<<"\n The first element has been deleted.\n";

Front();

}

}

void If_Empty()

{

if(front==NULL)

cout<<"\n The queue is empty.\n ";

}

void Front()

{

if(front!=NULL)

cout<<"\n The first element is "<<front->data<<endl;

}

};

void main()

{

queue q;

int data;

char opt;

do

{

cout<<" Enter your data:\t";

cin>>data;

q.enqueue(data);

cout<<"\n Do you want to continue:\t";

cin>>opt;

}while(opt=='y'opt=='Y');

q.Front();

q.dequeue();

q.If_Empty();

q.dequeue();

q.dequeue();

q.If_Empty();

q.dequeue();

}

Answer 2

A circular linked list is the same as a linked list except the tail node's next node is the head node. In a doubly-linked circular list, the head node's previous node is the tail node. Once this is done you need only maintain a pointer to the tail node, since the next node after the tail is the head node, giving constant time access to both via a single pointer.

Answer 3

Circular linked lists are created by using a standard linked list where every node points to the next node. Normally the tail node points to NULL (since nothing comes after the tail), but in a circular linked list, the tail node always points to the head node. In doubly-linked circular lists, the head and tail nodes always point to each other.

The only other difference is that with a linked list you only need to maintain a pointer to the head node. With a circular linked list you need to maintain a pointer to the tail node instead, because the head node can be determined by looking at the tail node's next node. This is useful when implementing queue structures since you need constant-time access to both the head and the tail. In a non-circular linked list, you would need to maintain pointers to both the head and the tail. Circular linked lists therefore reduce the memory overhead by one pointer (4 bytes on a 32-bit system).