Implement a Queue data structure using a linked list

Following closely on the heels of Stacks is the Queue data structure. Queue is a FIFO (First In First Out) structure. We have queue's all over in our lives. Queue at the grocery checkout line, at the movie theater ticket counter, at the mall, everywhere. We all are intimately familiar with the structure. The person who enters the queue first, gets out first. A conveyor belt is another example of a queue. The 2 main operations on a queue are Enqueue() and Dequeue().

As always, let's first define the linked list data structure that we will use for the queue data structure. Not surprisingly, this is the exact same structure we have been using for our examples:

typedef struct linked_list
{
    int data;
    struct linked_list *next;
} Node;

In addition, we have been using a global HEAD pointer that points to the start of this list. For queues, we also need a TAIL pointer that points to the end of the queue (list).

// global head pointer pointing to the root of the list
Node *head;
    
// global tail pointer for managing the last point
// in the queue; this is an optimization so that
// insertion in the queue is an O(1) operation
// and does not require a full queue traversal
// each time you want to insert an element in 
// the queue
Node *tail;

Now let's review the function to display the queue. This is a simple linked list traversal function.

// display the elements in the queue
// this basically is in order traversal
// of the linked list
void DisplayQueue()
{
    Node *currNode = head;
    printf("START --> ");
    // we will use a while loop
    // to display the queue
    // we could also have used recursion
    while (currNode != NULL)
    {
        // print the node data
        printf("%d --> ", currNode->data);
        // move to next element
        currNode = currNode->next;
    }
    printf(" --> END\n");
}

Adding a new element to the queue involves 2 pieces of logic. If the list is empty, then both head and tail pointers to the new node. Otherwise, the element is added at the tail end of the list. Remember, queue is a FIFO structure that dictates that the elements get added at the end of the list.

// add an element to the queue
// elements are added to the end of the queue
void Enqueue(int data)
{
    // assumption: head is already defined elsewhere in the program
    // 1. create the new node
    Node *temp = new Node;
    temp->data = data;
    temp->next = NULL;

    // special case - empty queue
    if (head == NULL)
    {
        // set both global pointers
        // to this new node
        head = temp;
        tail = temp;
    }
    else
    {
        // insert at the very end
        // set the tail pointer to 
        // point to this new node
        tail->next = temp;
        tail = temp;
    }
}

The last piece of the puzzle is the Dequeue method. This is same as the Stack Pop method. We need to remove the first element from the list.

// remove an element from the queue
// elements are removed from the 
// front of the queue
Node* Dequeue()
{
    // elements in a queue are removed
    // from the front
    // check for empty list
    if (head == NULL)
    {
        printf("Queue is empty\n");
        return NULL;
    }
        
    // get the top node
    Node *firstNode = head;

    // move the head 
    head = head->next;
        
    // disconnect the node 
    // from the list
    firstNode->next = NULL;

    // return the top node
    return firstNode;
}

 

Be warned. When you manipulate linked lists, you have the potential to create memory leaks if the nodes are not freed correctly. So test, double test your logic; especially when you create/delete nodes from the list.