Queues

A queue is another special type of list structure. Elements can only be inserted to the back of a queue, and only the front element can be accessed and modified. The structure of a queue is the same as that of a line of people. A person who wishes to stand in line must go to the back, and the person in front of the line is served. Thus, a queue is a FIFO structure, "First In, First Out". A generic queue is very simple to, a class definition for a linked queue is shown below.

template <class ItemType>
struct QueNode
{
   ItemType data;
   QueNode<ItemType> *next;
};

template <class ItemType>
class Queue
{
public:
   Queue(); //class constructor - initialize variables
   ~Queue(); //class destructor - return memory used by queue elements
   void enqueue(const ItemType); //add an item to the back of the queue
   ItemType dequeue(); //remove the first item from the queue and return its value
   ItemType first() const; //return the value of the first item in the queue without modification to the structure
   bool IsEmpty() const; //returns true if there are no elements in the queue
   bool IsFull() const; //returns true if there is no system memory for a new queue node
   int length() const; //returns the amount of elements in the queue
private:
   QueNode<ItemType> *front;
   QueNode<ItemType> *back;
   int len;
};

The front pointer will reference the first node in the queue, and the back pointer will reference the last node in the queue. It is possible to maintain only a front pointer. The last node in the list points to a NULL value, and can easily be found. However, such a design would be inefficient since finding the last node every time its location is needed is very time consuming. Therefore, we maintain a reference to it in our class implementation.

The class constructor initializes the private data members.

template <class ItemType>
Queue<ItemType>::Queue()
{
   front = NULL;
   back = NULL;
   len = 0;
}

The destructor deletes all nodes, freeing up the memory they used. The clear() function is called to do this operation.

template <class ItemType>
Queue<ItemType>::~Queue()
{
   clear();
}

The enqueue() function adds a new item to the back of the queue. The algorithm differs slightly, depending on whether the queue is empty or not. If the queue is not empty, the last node is set to point to the newly created node, and the back pointer is set to reference the new node. The value of the new node is item, and its next pointer has a value of NULL.

If the queue is empty, a similar procedure is used. However, the front pointer is also set to reference the newly created node. Since there is only one node in the queue, the front and back are one in the same.

template <class ItemType>
void Queue<ItemType>::enqueue(const ItemType item)
{
   assert(!IsFull()); //abort if there is no more memory for a new node
   if(len != 0) //if the queue is not empty
   {
      back->next = new QueNode<ItemType>; //create a new node
      back = back->next; //set the new node as the back node
      back->data = item;       back->next = NULL;    }
   else
   {
      back = new QueNode<ItemType>; //create a new node
      back->data = item;       back->next = NULL;       front = back; //set front to reference the new node. Since there it is the only node in the queue, it is considered to be both the back and front.
   }
   len++; //increment the amount of elements in the queue
}

The dequeue() function removes the node at the front of the queue and returns its value. The value of the front node is stored in item. A temporary local pointer is then created to reference the front node, and the front pointer is set to the next element in the queue. The front node is deleted using tmp as a reference. The function then checks if the queue is empty by evaluating front. If it has a value of NULL, the queue is empty, and the back pointer must also be set to NULL since it maintains the address of the now deleted node.

template <class ItemType>
ItemType Queue<ItemType>::Dequeue()
{
   assert(!IsEmpty()); //abort if the queue is empty, no node to dequeue
   ItemType item = front->data; //store the value of the first node, to be returned at the end
   QueNode<ItemType> *tmp = front; //temporary pointer to the first node.
   front = front->next; //set the second node in the queue as the new front
   delete tmp; //delete the original first node
   if(front == NULL) //if the queue is empty, update the back pointer
      back = NULL;
   len--; //decrement the amount of nodes in the queue
   return item; //return the value of the original first element
}

The first() function returns the value of the front node without modifying the queue.

template <class ItemType>
ItemType Queue<ItemType>::first() const
{
   assert(!IsEmpty()); //abort if the queue is empty
   return front->data;
}

The IsEmpty() function checks to see if there are any nodes in the queue by evaluating the front pointer. If the queue is empty, front has a value of NULL.

template <class ItemType>
bool Queue<ItemType>::IsEmpty() const
{
   return (front == NULL);
}

The IsFull() function works exactly the same way as it did with other data structures. A node is "created" using the new command, which is then checked. If the new command had failed to set aside the necessary memory, its value is NULL, in which case the function returns true. If the new node is created successfully, it is deleted and the function returns false.

template <class ItemType>
bool Queue<ItemType>::IsFull() const
{
   QueNode<ItemType> *tmp = new QueNode<ItemType>;
   if(tmp == NULL)
      return true;
   else
   {
      delete tmp;
      return false;
   }
}

The length() function returns the value of len, which maintains the amount of nodes in the queue. Again, a function is used to retrieve this value instead of making it a public data member to avoid error and make our class abstract.

template <class ItemType>
int Queue<ItemType>::length() const
{
   return len;
}