Please navigate to the bottom of the page for Table of Contents

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 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.

4 comments:

  1. what if there is only one item in the queue, after we removed it from the queue, the tail becomes null. In the Dequeue function, however, the scenario is not taken cared of. Or did I miss something??

    ReplyDelete
    Replies
    1. Jian,
      The dequeue happens from the head pointer. Tail is not needed here. Tail is more relevant to the enqueue process.

      Delete
  2. Hi Nikhil i hav a doubt .... in dequeue it should remove the tail data right ? as it was inserted first ? please clarify me

    ReplyDelete