Implementing Queue Using Linked List

In a general Queue (at any office or bank or any other place), people join the queue at the end and are removed from the front of queue.

Similarly Queue data structure is a linear list of elements where element is always inserted at the end and deleted from the front. 

Since it is a linear list (not hierarchical like Tree or Graph) it make sense to implement it using either Array or Linked List. In this post we will see the Linked list implementation of a Queue data structure.

Major operations that are performed on a Queue are:

•  Insert (also called Enqueue) - Inserting element at the End of queue.
• Delete (also called Dequeue) - Deleting element from the start of queue.

But lets implement few more operations like checking whether the queue is empty or not, printing all the elements of queue, deleting the entire queue (used in the destructor) etc. as shown in the below declaration:

class Queue
{
public:
    // Constructor
    Queue():front(NULL), rear(NULL){}
    // DEstructor - delete the Queue
    ~Queue();
    void enqueue(int data);
    int dequeue();
    bool isEmpty();
    void printQueue();
private:
    Node *front;  // pointer pointing to head of list
    Node *rear;   // pointer pointing to end of list
};

The Implementation of Node structure is also familiar as shown in earlier posts:

struct Node
{
    int data;
    Node* link;
    Node(int _data):data(_data),link(NULL){}
};

Important condition:

The Queue is Empty if front pointer is NULL

if(front == null)
    Queue is EMPTY
else
    Queue is NOT Empty

We can also check on the rear pointer, because when a queue is empty then ideally both front and rear can be set to NULL. Now lets look at other important functions:

isEmpty: Check if the Queue is Empty or not

The function isEmpty is hence very Simple

/** return true if the Queue is empty, else return false.
 */
bool Queue::isEmpty()
{
    return (front == NULL);
}

push / insert / enqueue: Inserting in the Queue

Insert after the rear Node and then move the rear pointer point to the new last Node.

The Important condition to check is that if the queue is empty then we have to modify the front pointer also (along with rear pointer).

/** Insert an element at the end of Queue.
 */
void Queue::enqueue(int data)
{
    if(front == NULL)
    {
        // If there are no elements in the queue then both front
        // & rear will point to the new element inserted
        rear = front = new Node(data);
    }
    else
    {
        // Element will be inserted at the end.
        rear->link = new Node(data);
        rear = rear->link;
    }
}

pop / delete / dequeue: Deleting from the Queue

Delete the Node (preserve its data to be returned later) pointed to by front and set the front pointer point to the new front node.

There are two condition to be checked

1. If the Queue is empty (if front pointer is NULL). Then either throw an exception or return a special value (we are returning -1 here to indicate that the queue is empty).
2. If the Queue has only one node (i.e it becomes empty after deleting the node). In this case, after deleting the node, we may want to set the rear pointer also to NULL. Actually, it is not required, because the check is on front pointer everywhere, but its a good practice.

/** Delete and return the first element of the queue.
 * If there are no element in the queue then the function will return -1.
 */
int Queue::dequeue()
{
    // If no element then return -1
    if(front == NULL){
        return -1;
    }
    int returnValue = front->data;
    Node* temp = front->link;
    delete front;
    front = temp;
    // If there was only one element in the Queue, then deleting it will make the queue empty
    // hence also set rear pointer to null (to be consistent)
    if(front == NULL){
        rear = NULL;
    }
    return returnValue;
}

printQueue: Print all the element of the queue

This is simply printing the elements of a linked list

/** Print the entire Queue
 */
void Queue::printQueue()
{
    Node *temp = front;
    while(temp != NULL)
    {
        cout<<" "<<temp->data;
        temp = temp->link;
    }
}

~Queue: The destructor

Simply deleting all the elements in the list.

/**

 * Delete all the nodes in the Queue.
 */
Queue::~Queue()
{
    while(front != NULL)
    {
        Node* temp = front;
        front = front->link;
        delete temp;
    }
}

You may also want to read Linked list implementation of Stack Data Structure.