Sunday, May 22, 2011

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 listNode *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 queueNode *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 listvoid 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 queuevoid 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 queueNode* 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.