Linked Queue

An array implementation of queue has limitation of fixed size. The fixed sizes do not give flexibility to the user to dynamically exceed the maximum size. The declaration of arbitrarily maximum size leads to poor utilization of memory. In addition, the major drawback is the updating of front and rear.

This limitation can be overcome using linked implementation of queue. Linked list implementation of queue is called linked queue.

Using linked queue data can be added at rear end easily without adjusting of entire queue. Data can be deleted from the front end.

Node structure for linked queue:

class QNode

{

public:

int data;

QNode *link;

};

Each node contains data and the link pointer to the next element in the queue.

class Queue

{

QNode *Front, *Rear;

int IsEmpty();

public:

Queue()

{

Front = Rear = Null;

}

void Add( int Element);

int Delete();

int FrontElement();

~Queue();

};

 

The above class declaration creates an empty queue and initializes the pointer front and rear to Null. Here, front always points to the first node of queue and rear points to the last node of queue.

Queue empty condition is simply checked by comparing the front with Null.

if(Front == Null)  // list is empty

If NewNode is a node getting added in an empty queue, both front and rear get updated.

 

 If deletion of data has to be performed, first a check has to be made if queue is empty or not. If it is not empty then front end has to be modified and front is set to point to front->next node.

           

            int Queue :: Delete()

            {

            int temp;

            QNode *current = Null;

            if(!IsEmpty())

            {

            temp = Front->data;

            current = Front;

            Front = Front->link;

            delete current;                                                                        

            if(Front == Null)

            Rear = Null;

            return(temp);

            }

            }