Intermediate Business Programming with C++

Introduction to Queues

A queue is an ordered collection of data items such that:

A queue's basic operations are:

Because of its general construct, a queue is said to be a First-In-First-Out (FIFO) structure. In addition to being called FIFO, a queue is also called First-Come-First-Served (FCFS).

 Note:  In some implementations the method: addQ() is called: enqueue(). Further in these implementations front() and removeQ() are combined into a method: dequeue() which returns the value at the front of the queue and then removes that value. However in these notes these methods will remain separate because some implementations of queues require the program to call front() to get its value, send this value to another site and then if the other site receives the value correctly, the queue is notified to remove the front element using the removeQ() method.

Queues as Compared to Stacks

When compared as containers:

When compared as to how they handle applications:

When these containers are used:

From an ordering perspective, then, queues are the "opposite" of stacks.

The Queue ADT Implemented Using an Array

Any implementation of a queue requires:

Therefore an array-based implementation would need data constructs like:

Problem:

Consider the following graphic as an example of an array implemented queue (notice that the capacity of the myArray is 11).

To begin with, both myFront = 0 and myBack = 0. Any additions to the queue would be at the back and therefore the additions would result in incrementing myBack.

 Note:  In the following discussion, each ai is a data item in myArray.

Add an element a1 to the queue so myBack = myBack + 1

Add another element a2 so myBack = myBack + 1

Add another element a3 so myBack = myBack + 1 and then add another element a4 which yields myBack = myBack + 1

Deletions from the front of the queue would result in incrementing myFront, so we have: myFront = myFront + 1 and the first element appears to be a2. However, if you looked in the memory, you would find a1 still in position 0. It is that the queue does not know that a1 is there. As far as the queue is concerned, the data in this position is garbage.

If the additional elements: a5, a6, a7, a8, a9 and a10 are added to the queue then the code would need to increment myBack, once for each of these elements. In addition, if another element is removed from the queue myFront would be incremented as well and what would appear in the queue would be the following:

Using a traditional approach to an array, as more data is added to the array, the array could run out of space soon! That is, if the program added a11, the counter: myBack would be incremented to exceed the size of the array. However this would not need to be the case in a queue if the following example was used:

In this example, you will notice that when a11 was added to the queue, the counter myBack took on the value 0 again and when a12 was added to the queue, myBack was incremented to 1. In a similar fashion when myFront reaches the end of the array, it too is set to 0 again.

Solution:

Initially, a queue object is empty and the queue counters will have the following values:

After many insertions and deletions, the queue is full:

PROBLEM: How to distinguish between empty & full?

Possible Solutions:

Wrap around keeps the addition/deletion cycle from walking off the edge of the storage array.

Say, myArray has capacity elements. When myBack hits the end of myArray, an addition should wrap myBack around to the first element of myArray, e.g.:

myBack++; if (myBack = = capacity) myBack = 0; myBack = (myBack + 1) % capacity;

An analogous handling of myFront is needed when there is a deletion: e.g.

myFront = (myFront + 1) % capacity;

An Example: A Queue as a Long Array

Create a C++ program that simulates the circle queue example above into a program. Set the array elements to be long integers. In doing this, the top and the bottom of the queue begin at position 0 because an array in C++ starts with index 0. Notice the following graphic which shows a circular queue with eight elements:

 Note:  An array is not the only way to solve this specification as will be discussed later in the lectures when Lists are discussed and when the STL (Standard Temple Library) is discussed.

The 5 Phases of Software Development

  1. The Specification Phase

  2. The Design Phase

  3. The Coding Phase

    • long_queue.h

    • long_queue.cpp

    • useQueue.cpp

    (Are there cases where the program could fail? Has the program adequately provided for error handling? What should be added to ensure NO failure?)

  4. The Testing Phase (What should be done here?)

  5. The Maintenance Phase (What should be done here?)

 Warning:  The Maintenance Phase should consider what the potential future changes can be. What the programmer needs to be very careful not to implement into the program what he/she believes will solve maintenance work of the future because it may never happen and these additions may make a program that the user does not want.

The Specifications Phase

Create a long queue. The queue should operate like the following example:

The queue class needs to have methods that provide for each of the following:

First consider some actions with the circle queue. For example:

In the example above as elements are added: myFront is the index of the first element in the queue array while myBack is one position beyond the last element of the queue (i.e. where the next element can be added). However both myFront and myBack must rap around the array when they have reached the end of the array.

The Design Phase

To implement the specification, the program will create a C++ class: Queue. To do this we must determine the data members, the operations (member functions) and any other conditions that will be required to achieve the specifications. In addition we must always consider those cases that will make the operations fail. We should try to prevent any errors within the class if possible. If this is not possible, we need to consider what needs to be done in the implementation program to prevent ALL possible errors.

Independent of the class there will need to be a long:

The class will have three data members:

  • myFront:

A long that is the index of location of the first element of the queue.

  • myBack

A long that is the location of one position beyond the last element added to the queue.

  • theArray[ ]

A long array that holds the elements of the queue.

The class methods that are required and the error considerations are the following:

To help with debugging, we will add the operation:

The following would be an example of a UML diagram for the class

As with the stack design phase above, the structure chart will not be discussed.

The Testing Phase

When designing the Testing Phase we need to keep in mind: The Program Must Never Fail No Matter What the User Does!!!! If this is our goal, then what should we do to test the program if we were a member of the Quality Assurance group? What types of errors could occur?

Some considerations to test:

Can you think of any other possible tests? There is an error in the coding that is not well handled. Find it.

Designing a General Queue Class

As with Stack, we will need to generalize the data type so that Queue can handle a long or a char or even a Date. To demonstrate the generality of this header we will use as the data type the class: Date which is in the header: date.h

What we will do now is to redesign the previous example so that the data type of the elements in Queue will not matter. This change will require that the data type of theArray[ ] in the previous example be specified outside of the definition of Queue in the implementation program. As with Stack, we again need to use a typedef in the implementation program as in the following statement:

typedef Date QueueType;

This will be done after the include of the Date header file. Of course we would change this if we wanted the data type of Queue to be something other than Date objects.

Next we need to change the definition of theArray[ ] as in the following statement:

QueueType theArray[capacity];

In addition to this change of the array, it will be necessary to rewrite the prototypes and the definitions of two methods to reflect this change in data type of the queue. That is the following two functions must change:

void addQ(const QueueType& value); QueueType frontQ () const;

The redefinition of the class: Queue can be viewed in the header: new_queue.h.

Because of these changes, the implementation program must be changed in two ways:

The implementation is now changed to the program: date_queue.cpp. This particular implementation is designed specifically for the class Date but with only minor changes it should work for any class.

Related

Категории