Program for Queue using Linked List in C++ and Implementation

Queue is an Abstract data type which follows "First In First Out" Principle . Queue is an ordered collection of homogeneous data elements like stack . It is a linear data Structure in which insertion , deletion operations takes place at two ends called REAR (R) and FRONT (F) of the queue . 
Elements are inserted at the rear end and elements are deleted at the front end of a queue . The first element entered into the queue is the first element that is removed from the queue .

Why To Implement Queues using Linked List ?

In one of my previous tutorial , I discussed about Program for Queues using arrays , where the size of the array need to be fixed to store the elements in the queue . But in Linked list We need not worry about size of the Queue . Size of the queue is under the supervision of the user . So Implementing Queues using Linked list will have more advantage than that of using arrays . 
In this program Linked list data structure is used . If you don't have any idea about Linked List I suggest to have a read of Excellent Linked list Data Structure .

The Following are the operations performed on Queue :
1. The enqueue() Method
2. The dequeue() Method
3. The peak() Method
4. The isempty() 

1. The enqueue() Method :

The enqueue() method adds an item to the rear end of the queue if the queue , is not full . In cases queue is full , the method displays an error message and returns the calling routine . Normally insertion involves incrementing rear and inserting at the cell rear now points to . If rear is at the end of the array , at maxsize-1 , then it must wrap around to the beginning of the array before the insertion takes place . This done by setting rear to -1 , so that array before the insertion takes place .This is achieved by setting rear to -1 , so that when the increment occurs rear will become 0 , the beginning of the array .

2. The dequeue() Method :

The dequeue() method check that the queue is not empty Removal always starts by obtaining the value at front and then incrementing front . However , if this puts front beyond the end of the array , it must be wrapped around to 0 . The return value is stored temporarily .

3. The Peek() Method :

This is another queue operation that finds the value of the item at the front of the queue without deleting the item . The peek() method is straightforward : It returns the value at front . Some implementations allow peeking at the rear of the array as well ; such routines are called something like peekfront() and peekrear() .

Program for Queue using Linked list in C++

Class Definition :

template<class T>
class linkedqueue
{
public :
    linkedqueue()
    {
        front=back=0;
    }
    ~linkedqueue();
    bool isempty() const
    {
        return ((front)?false:true);
    }
    bool isfull() const;
    T first() const;
    T last() const;
    linkedqueue<T>& add(const T&x);
    linkedqueue<T>& deletee(T &x);
private:
    node<T> *front;
    node<T> *back;
};

Destructor, Isfull:

template<class T>
linkedqueue<T>::linkedqueue()
{
    node<T> *next;
    while(front)
    {
        next=front->link;
        delete front;
        front=next;
    }
}
template<class T>
bool linkedqueue<T>::isfull() const
{
    node<T> *p;
    try
    {
        p=new node<T>;
        delete p;
        return false;
    }
    catch(nomem)
    {
        return true;
    }
}

First and Last Elements of Queues:

template<class T>
T linkedqueue<T>::first() const
{
    if(isempty()) throw outofbounds();
    return front->data;
}
template<class T>
T linkedqueue<T>::last() const
{
    if(isempty()) throw outofbounds();
    return back->data;
}

Add and Delete Operation of Queues:

template<class T>
linkedqueue<T>& linkedqueue<T>::add(const T&x)
{
    node<T> *p=new node<T>;
    p->data=x;
    p->link=0;
    if(front)back->link=p;
    else front=p;
    back=p;
    return *this;
}

template<class T>
linkedqueue<T>& linkedqueue<T>::deletee(T &x)
{
    if(isempty()) throw outofbounds();
    x=front->data;
    node<T> *p=front;
    front=front->link;
    delete p;
    return *this;
}

The Time complexity for Queue using Linked list is :
Deletions : O(1)
Insertions : O(1)
for an Empty Queue : front=0 
Also check : Program for Polynomial addition using Linked list

Final Words :

Queue using Linked list is implemented in C++ using Object oriented programming . 
If I missed anything please get it to me through comments . Also share your idea and Logic through comments .