How to use Queue data Structure in C++ using example or exercise

Online tutorial : How to use Queue data Structure in C++ Programming  using example or exercise code  

QUEUES

               This tutorial discusses queues, the data associated with a queue and the operations performed on a queue. After this lecture, you should be able to implement linear and circular queues using arrays in C++.                                               
           A queue is a special list into which items can be inserted at one end (rear) of the queue and from which items may be removed from the other end (front) of the queue. It is probably the most common data structure in our daily life. A queue may be visualized as a line at a phone booth or a bank. The item that is the first to be inserted into a queue is the first one that may be removed from the queue. For this reason a queue is called a FIFO (First In First Out).

What Data may be Associated with a Queue?

               A queue, just like a stack, is a special form of a list i.e. an ordered collection of items. The items may be of any data-type e.g. integers, characters. The items may even be instances of user defined data types (structures or classes). There are two other variables associated with a queue: rear, which determines the end to which insertions are done and front, which designates the end from which deletion takes place.

Which Operations may be Performed on a Queue?

               The three basic operations that may be performed on a queue are:

• Insertion of a new element: One fundamental operation is to insert an element into the queue. This operation is written as insert (Q, i). The insert operation takes two arguments: Q and i. The notation means "Insert an item i onto the queue Q at the rear end. When we are referring to a single queue, we may use insert(i) to mean "Insert an item i into the queue under consideration at its rear end.
• Removal of an element: Another operation is removing an item from the front end of the queue. This operation may be written as remove (Q). The remove operation takes a single argument: Q. The notation means "Remove an item from the queue Q from the front end. When we are referring to a single queue, it is sufficient to write remove( ).
• Test if the queue is empty: The operation returns TRUE if the queue is empty and FALSE otherwise. This is written as empty(Q) meaning "Test if the queue Q is empty". In case of a single queue, empty( ) may be used.
• We don't consider a full operation because theoretically a queue can never be full and you can always perform an insert operation.

QUEUE AS A LINEAR ARRAY:

               A simple implementation (but not a very good one) of a queue may be done by using an array. Consider an array data that has been declared with MAX number of elements. There are two integer variables rear and front that are used to keep track of the indices of the first and the last elements of the queue.
               Some important things to remember are:

• Rear is initialized to -1 and front to 0
• Since an item is inserted at the rear end, the variable rear is incremented whenever an insertion is done
• Similarly each removal results in an increment of the variable front
• The queue will be considered empty when the value of rear is lesser than that of front

               A graphical representation of the state of the queue and its variables after various operations, is given below:
 

               Now if you try to insert another element into the queue, you have to increment front from 3 to 4 but the array index cannot exceed 3. It means that we cannot insert a new element into the queue although half of the array is empty. This grave flaw in this implementation makes it a poor choice. This problem may be solved by shifting all the elements of the queue towards the zero index of the array but this is highly inefficient. A better choice is to use a circular array.

QUEUE AS A CIRCULAR ARRAY:

               Don't get confused by the term circular array. Physically it is the same linear array. The only change is that we provide a mechanism that links the last element back to the first element of the array. Now in the same figure (when rear is the last element of the array), if we have to make a further insertion, the next item will be inserted in the first element of the array. All we need to do is

• If front is MAX-1 and you have to remove an item (or rear is MAX-1 and you have to insert an item), instead of incrementing make front (or rear) 0
• Otherwise simply increment it

               Now things work fine other than the fact that our previous empty condition is no more valid. Now you have to determine an empty condition. This may be achieved in two ways:

1. Changing the Definition of "front":

               Now front is defined as the index of the array immediately preceding the first element of the queue. (Remember that according to our previous definition, front was the index of the first element of the queue.) Doing so, we observe that a queue will be empty when rear=front. You can use this condition for testing if a queue is empty or not.

• In this case both the front and rear are initialized to MAX-1

               But wait a second. We have to keep a check for overflow as well. Unfortunately we now realize that the full condition is the same as the empty condition that is rear=front. Now how will our program differentiate between a full and an empty queue? This can be solved by keeping an element of your array always empty. So if an array of 10 elements is declared, your queue will have 9 elements at the maximum. If it is attempted to insert 10th element, an error should be generated. You can now use a temporary variable to store the changed value of rear and make the test temporary=front before actually changing the value of rear.

2. Using an Auxiliary Variable:

               By now, you must be disgusted by this never ending series of problems and their solutions that give birth to new problems. Let us finish the topic by introducing an elegant way to determine the full and empty conditions. You even don't need to change the definition of front when using this method. Our queue will have another variable named count. count is incremented whenever an item is inserted into the queue and it is decremented whenever an item is removed from the queue. Now the empty condition will be count=0 and the full condition will be count=MAX. You don't have to leave an element of the array empty and thus this solution takes exactly the same amount of memory. And of course it is much simpler and easier to comprehend.

EXERCISES

• Implement Queue as a C++ class, having two private data members: a character array data and two integers rear and front. Write functions for insert, remove, and empty operations. Then test the queue in a main program using random sequence of operations. Now make appropriate changes to make it into a circular array queue.
• Implement a class strangeQueue in C++, which has two private members that are objects of the stack class you implemented yesterday. Write functions for insert, remove and empty operations for the strangeQueue class. (Hint: Add a function full to your stack class. )
• Write a class complexQueue, which has three private members, which are objects q1, q2, q3 of the class Queue (that you implemented in exercise 1). Now add a function Qinsert that tries to insert the element in q3. If q3 is full, one element is shifted to q2 and the new element is inserted in q3. If both q2 and q3 is full, an element is shifted into q1 and the new element is inserted into q3. Also add a functions Qremove and Qempty. (Hint: Add a function full to your queue class. )