Previous Section
 < Free Open Study > 
Next Section


4.5 Queues

Logical Level

A stack is an abstract data structure with the special property that elements are always added to and removed from the top. We know from experience that many collections of data elements operate in the reverse manner: Items are added at one end and removed from the other. This structure, called a FIFO (First In, First Out) queue, has many uses in computer programs. We consider the FIFO queue data structure at three levels: logical, implementation, and application. In the rest of this chapter, "queue" refers to a FIFO queue. (Chapter 9 discusses another queue-type abstract data type, the priority queue. The accessing protocol of a priority queue differs from that of a FIFO queue.)

A queue (pronounced like the letter Q) is an ordered, homogeneous group of elements in which new elements are added at one end (the "rear") and elements are removed from the other end (the "front"). As an example of a queue, consider a line of students waiting to pay for their textbooks at a university bookstore (see Figure 4.6). In theory, if not in practice, each new student gets in line at the rear. When the cashier is ready to help a new customer, the student at the front of the line is served.

Click To expand
Figure 4.6: A FIFO queue

Queue A data structure in which elements are added to the rear and removed from the front; a "first in, first out" (FIFO) structure

To add elements to a queue, we access the rear of the queue; to remove elements, we access the front of the queue. The middle elements are logically inaccessible, even if we physically store the queue elements in a random-access structure such as an array. It is convenient to picture the queue as a linear structure with the front at one end and the rear at the other end. However, we must stress that the "ends" of the queue are abstractions; they may or may not correspond to any physical characteristics of the queue's implementation. The essential property of the queue is its FIFO access.

Like a stack, a queue is a holding structure for data that we use later. We put a data item onto the queue; when we need it later, we remove it from the queue. If we want to change the value of an element, we must take that element off the queue, change its value, and then return it to the queue. We do not directly manipulate the values of items that are currently in the queue.

Operations on Queues The bookstore example suggests two operations that we can apply to a queue. First, new elements can be added to the rear of the queue, an operation that we call . We can also remove elements from the front of the queue, an operation that we call . Unlike the stack operations and , the adding and removing operations on a queue do not have standard names. is sometimes called , and is also called , , , and .

Another useful queue operation is checking whether the queue is empty. The function returns true if the queue is empty and false otherwise. We can apply only when the queue is not empty. Theoretically, we can always apply , because in principle a queue has no limit on its size. We know from our experience with stacks, however, that certain implementations (an array representation, for instance) require that we test whether the structure is full before we add another element. This real-world consideration applies to queues as well, so we define an operation. We also need an operation to initialize a queue to an empty state, which we call . Figure 4.7 shows how a series of these operations would affect a queue.

Click To expand
Figure 4.7: The effects of queue operations

We have briefly described a set of accessing operations for a queue. Before we talk about this structure's use and implementation, let's define the specification for the Queue ADT.

We continue to leave the statements in the specifications defining what the user must provide. However, as we are using C++, we assume that this information might be provided when a class object is declared (in the form of a template parameter and a constructor parameter or an included class).

Application Level

We have discussed how operating systems and compilers can use stacks. Queues are often used for system programming purposes. For example, an operating system often maintains a FIFO list of processes that are ready to execute or that are waiting for a particular event to occur. The programmer who creates the operating system can use a Queue ADT to implement these lists.

Computer systems must often provide a "holding area" for messages between two processes, two programs, or even two systems. This holding area, which is usually called a "buffer," is often implemented as a FIFO queue. For example, if a large number of mail messages arrive at a mail server at about the same time, the messages are held in a buffer until the mail server can begin processing them. It processes the messages in the order they arrived-that is, first in, first out order. (Some mail servers may handle the messages based on a priority system; in such a case, the priority queue described in Chapter 9 would be a more appropriate ADT.)

To demonstrate the use of queues, we first look at a simple problem: identifying palindromes. A palindrome is a string that reads the same forward as backward. While we are not sure of their general usefulness, identifying these strings provides us with a good example for the use of both queues and stacks. Besides, palindromes can be entertaining. Some famous palindromes are:

  • A tribute to Teddy Roosevelt, who orchestrated the creation of the Panama Canal: "A man, a plan, a canal-Panama!"

  • Allegedly muttered by Napoleon Bonaparte upon his exile to the island of Elba (although this is difficult to believe given that Napoleon mostly spoke French!): "Able was I ere, I saw Elba."

  • Overheard in a Chinese restaurant: "Won ton? Not now!"

  • Possibly the world's first palindrome: "Madam, I'm Adam."

  • Followed immediately by one of the world's shortest palindromes: "Eve."

As you can see, the rules for what constitutes a palindrome are somewhat lenient. Typically, we do not worry about punctuation, spaces, or matching the case of letters. Two obvious algorithms exist for determining whether a string is a palindrome. The first algorithm starts at both ends, moving inward as you compare the characters. Three cases are possible:

  1. There are two characters that do not match.

  2. The characters all match, including the two middle characters.

  3. The number of characters is odd and the characters on the right and left of the middle character match.

The second algorithm copies the string in reverse order and matches the two copies character by character. As we already have a structure that returns a string in reverse order, let's use the second algorithm.

The characters are read character by character and stored into a queue and a stack. When all of the characters in the line have been processed, the program repeatedly pops a letter from the stack, and dequeues a letter from the queue. As long as these letters match each other, the entire way through this process, we have a palindrome. Can you see why? Because the queue is a first in, first out list, the letters are returned from the queue in the same order they appear in the string. The letters taken from the stack, however, are returned in the opposite order from how they appear in the string. Thus this algorithm compares the letters from the forward view of the string to the letters from the backward view of the string.

Now we are ready to write the main algorithm assuming an instance of a Stack ADT and an instance of the Queue ADT. The basic flow of the algorithm is to continuously read and handle characters until we reach the end of the line.

All of the statements in the algorithm can be coded immediately, using StackType and QueType objects. The program is found in the file palindrome. cpp.

#include "QueType.h"          // Untemplated queue of char
#include "StackTType.h"       // Templated stack
#include <iostream>

int main()
{
  using namespace std;
  bool palindrome = true;
  char character;
  StackType<char> stack(40);
  QueType queue(40);
  char stackChar;
  char queChar;
  cout << "Enter a string; press return." << end1;
  cin.get(character);
  while (character != '\n')
  {
    stack.Push(character);
    queue.Enqueue(character);
    cin.get(character);
  }

  while (palindrome && !queue.IsEmpty())
  {
    stackChar = stack.Top();
    stack.Pop();
    queue.Dequeue(queChar) ;

    if (stackChar != queChar)
      palindrome = false;
  }

  if (palindrome)
    cout << "String is a palindrome" << end1;
  else
    cout << "String is not a palindrome" << end1;
  return 0;
}

The two screen shots illustrate the correctness and the limitations of this algorithm. Uppercase and lowercase letters are not considered to be the same. Does this algorithm have other problems? You are asked to examine this question and improve this algorithm in the exercises.

Click To expand
Click To expand

Implementation Level

Now that we've had the opportunity to be queue users, let's look at how we might implement a queue in C++. Like a stack, a queue can be stored in a static array with its size fixed at compile time or in a dynamically allocated array with its size determined at run time. We look at the dynamic implementation here.

Definition of the Queue Class To concentrate on the ADT Queue itself, we implement it as a queue of char items. You are asked to implement the ADT Queue as a class template in the exercises. As with the stack class, we do not need a comparison function because none of the operations requires comparing items on the queue.

Which data members does our Queue ADT need? We need the items themselves, but at this stage we do not know what else we need. As described in the previous section, we allow the user to determine the maximum size by using a parameterized constructor. Note also that we implement a MakeEmpty function as well as a class constructor.

typedef char ItemType;
class QueType
{
public:
  QueType(int max);  // max is the size of the queue.
  QueType();         // Default size of 500.
  ~QueType();
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const;
  void Enqueue(ItemType item);
  void Dequeue(ItemType& item);
private:
  ItemType* items;
  int maxQue;
  // Whatever else we need.
} :

Implementations of Queue Operations The first question to consider is how we order the items in the array. In implementing the stack, we began by inserting an element into the first array position and then let the top float with subsequent Push and Pop operations. The bottom of the stack, however, remained fixed at the first slot in the array. Can we use a similar solution for a queue, keeping the front of the queue fixed in the first array slot and letting the rear move down as we add new elements?

Let's see what happens after a few Enqueue and Dequeue operations if we insert the first element into the first array position, the second element into the second position, and so on. After four calls to Enqueue with parameters 'A', 'B', 'C, and 'D', the queue would look like this:

Click To expand

Recall that the front of the queue is fixed at the first slot in the array, whereas the rear of the queue moves down with each Enqueue. Now we Dequeue the front element in the queue:

Click To expand

This operation deletes the element in the first array slot and leaves a hole. To keep the front of the queue fixed at the top of the array, we need to move every element in the queue up one slot:

Click To expand

Let's summarize the queue operations corresponding to this queue design. The Enqueue operation would be the same as Push. The Dequeue operation would be more complicated than Pop, because all remaining elements of the queue would have to be shifted up in the array, so as to move the new front of the queue up to the first array slot. The class constructor, MakeEmpty, IsEmpty, and IsFull operations could be the same as the equivalent stack operations.

Before going any further, we want to stress that this design would work. It may not be the best design for a queue, but it could be implemented successfully. Multiple functionally correct ways to implement the same abstract data structure exist. One design may not be as good as another (because it uses more space in memory or takes longer to execute), yet may still be correct. Although we don't advocate the use of poor designs for programs or data structures, the first requirement must always be program correctness.

Now let's evaluate this particular design. Its strengths are its simplicity and ease of coding; it is almost exactly like the stack implementation. Although the queue is accessed from both ends rather than just one end (as in the stack), we have to keep track of only the rear, because the front remains fixed. Only the Dequeue operation is more complicated. What is the weakness of the design? The need to move all of the elements up every time we remove an element from the queue increases the amount of work needed to dequeue items.

How serious is this weakness? To make this judgment, we must know something about how the queue will be used. If this queue is used for storing large numbers of elements at one time, or if the elements in the queue are large (class objects with many data members, for instance), the processing required to move up all elements after the front element has been removed makes this solution a poor one. On the other hand, if the queue generally contains only a few elements and they are small (integers, for instance), the data movement may not require much processing. Furthermore, we need to consider whether performance-how fast the program executes-is important to the application that uses the queue. Thus the complete evaluation of the design depends on the client program's requirements.

In the real programming world, of course, you don't always know the exact uses or complete requirements of programs. For instance, you may be working on a very large project with 100 other programmers. Other programmers may be writing the specific application programs for the project, while you are producing some utility programs that are used by all of the different applications. If you don't know the requirements of the various users of your package of queue operations, you must design general-purpose utilities. In this situation, the design described here is not the best option.

Another Queue Design The need to move the elements in the array arose from our decision to keep the front of the queue fixed in the first array slot. If we keep track of the index of the front as well as the rear, we can let both ends of the queue float in the array.

Figure 4.8 shows how several Enqueue and Dequeue operations would affect the queue. (For simplicity, the figure shows only the elements in the queue. The other slots contain logical garbage, including dequeued values.) The Enqueue operations have the same effect as before; they add elements to subsequent slots in the array and increment the index of the rear indicator. The Dequeue operation is simpler, however. Instead of moving elements up to the beginning of the array, it merely increments the front indicator to the next slot.

Click To expand
Figure 4.8: The effect of Enqueue and Dequeue
Click To expand
Figure 4.9: Wrapping the queue elements around

Letting the queue elements float in the array creates a new problem when the rear indicator reaches the end of the array. In our first design, this situation told us that the queue was full. Now, however, the rear of the queue might potentially reach the end of the (physical) array when the (logical) queue is not yet full (Figure 4.9a).

Because space may still be available at the beginning of the array, the obvious solution is to let the queue elements "wrap around" the end of the array. In other words, we can treat the array as a circular structure, in which the last slot is followed by the first slot (Figure 4.9b). To get the next position for the rear indicator, for instance, we can use an if statement:

if (rear = = maxQue - 1)
  rear = 0;
else
  rear = rear + 1

We can also reset rear by using the remainder (%) operator:

rear = (rear + 1) % maxQue;

This solution leads us to a new problem: How do we know whether a queue is empty or full? In Figure 4.10, we remove the last element, leaving the queue empty. In Figure 4.11, we add an element to the last free slot in the queue, leaving the queue full. The values of front and rear, however, are identical in the two situations. We cannot distinguish between a full queue and an empty queue.

Click To expand
Figure 4.10: An empty queue
Click To expand
Figure 4.11: A full queue

The first solution that comes to mind is to add another data member to our queue class, in addition to front and rear-a count of the elements in the queue. When the count member is 0, the queue is empty; when the count is equal to the maximum number of array slots, the queue is full. Note that keeping this count adds work to the Enqueue and Dequeue routines. If the queue user frequently needed to know the number of elements in the queue, however, this solution would certainly be a good one. We leave the development of this solution as an exercise.

Another common, but less intuitive approach is to let front indicate the index of the array slot preceding the front element in the queue, rather than the index of the front element itself. (The reason for this choice may not be clear immediately, but keep reading.) If rear still indicates the index of the rear element in the queue, the queue is empty when front is equal to rear. To dequeue an element, we increment front to indicate the true location of the front queue element, and assign the value in that array slot to item. (Updating front precedes assigning the value in this design, because front does not point to the actual front element at the beginning of Dequeue.) After this Dequeue operation, IsEmpty finds that front is equal to rear, indicating that the queue is empty (see Figure 4.12).

Click To expand
Figure 4.12: Testing for an empty queue

An additional convention that we must establish to implement this scheme is that the slot indicated by front (the slot preceding the true front element) is reserved. It cannot contain a queue element. Thus, if there are 100 array positions, the maximum size of the queue is 99 elements. To test for a full queue, we check whether the next space available (after rear) is the special reserved slot indicated by front (see Figure 4.13).

Click To expand
Figure 4.13: Testing for a full queue

To enqueue an element, we must first increment rear so that it contains the index of the next free slot in the array. We can then insert the new element into this space.

Using this scheme, how do we initialize a queue to its empty state? We want front to indicate the array index that precedes the front of the queue, so that when we first call Enqueue the front of the queue is in the first slot of the array. Which position precedes the first array slot? Because the array is circular, the first slot is preceded by the last slot. As a consequence, we initialize front to maxQue - 1. Because our test for an empty queue is checking whether front is equal to rear, we initialize rear to front, or maxQue - 1.

Now we see that we must add two data members to the QueType class: front and rear. The header file follows. Through the parameterized constructor, we let the user determine the maximum size of the queue when a class object is declared. Because our implementation takes one more array slot, we must increment max (the parameter to the constructor) before we save it in maxQue. (This implementation is called a circular or ring queue.)

class FullQueue
{}:
class EmptyQueue
{};

typedef char ItemType;
class QueType
{
public:
  QueType(int max);
  QueType();
  ~QueType();
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const:
  void Enqueue(ItemType newItem);
  void Dequeue(ItemType& item);
private:
  int front;
  int rear;
  ItemType* items;
  int maxQue;
};
QueType::QueType(int max)
// Parameterized class constructor.
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = max + 1;
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
}
QueType::QueType()      // Default class constructor.
// Post: maxQue, front, and rear have been initialized.
//       The array to hold the queue elements has been dynamically
//       allocated.
{
  maxQue = 501;
  front = maxQue - 1;
  rear = maxQue - 1;
  items = new ItemType[maxQue];
}
QueType::~QueType()     // Class destructor.
{
  delete [] items;
}
void QueType::MakeEmpty()
// Post: front and rear have been reset to the empty state.
{
  front = maxQue - 1;
  rear = maxQue - 1;
}
bool QueType::IsEmpty() const
// Returns true if the queue is empty; false otherwise.
{
  return (rear == front);
}

bool QueType::IsFull() const
// Returns true if the queue is full; false otherwise.
{
  return ((rear + 1) % maxQue == front);
}

void QueType::Enqueue(ItemType newItem)
// Post: If (queue is not full) newItem is at the rear of the queue;
//       otherwise, a FullQueue exception is thrown.
{
  if (IsFull())
    throw FullQueue();
  else
  {
    rear = (rear +1) % maxQue;
    items[rear] = newItem;
  }
}

void QueType::Dequeue(ItemType& item)
// Post: If (queue is not empty) the front of the queue has been
//       removed and a copy returned in item;
//       otherwise, an EmptyQueue exception is thrown.
{
  if (IsEmpty())
    throw EmptyQueue();
  else
  {
    front = (front + 1) % maxQue;
    item = items[front] ;
  }
}

Note that Dequeue, like the stack Pop operation, does not actually remove the value of the item from the array. The dequeued value still physically exists in the array. It no longer exists in the queue, however, and cannot be accessed because of the change in front. That is, the dequeued data element exists in the implementation but not in the abstraction.

Test Plan To make sure that you have tested all the necessary cases, make a test plan, listing the various queue operations and what tests are needed for each, as we did for stacks. (For example, to test the function IsEmpty, you must call it at least twice-once when the queue is empty and once when it is not.)

We want to Enqueue elements until the queue is full and then call the functions IsEmpty and IsFull to see whether they correctly judge the state of the queue. We can then Dequeue all elements in the queue, printing them out as we go, to confirm that they are correctly removed. At that point, we can call the queue status functions again to see whether the empty condition is detected correctly. We also want to test the "tricky" part of the array-based algorithm: Enqueue until the queue is full, Dequeue an element, then Enqueue again, forcing the operation to circle back to the beginning of the array.

On the Web, the test driver is located in QueDr. cpp, the input file is QueType. in, and the output files are QueType. out and QueType. screen.

Comparing Array Implementations The circular array solution is not nearly as simple or intuitive as our first queue design. What did we gain by adding some amount of complexity to our design? By using a more efficient Dequeue algorithm, we achieved better performance. To find out how much better, let's analyze the first design. Because the amount of work needed to move all of the remaining elements is proportional to the number of elements, this version of Dequeue is an 0(N) operation. The second array-based queue design simply requires Dequeue to change the values of the front indicator and to put the value into item to be returned. The amount of work never exceeds some fixed constant, no matter how many elements are in the queue, so the algorithm has 0(1) complexity.

The other operations all have 0(1) complexity. No matter how many items are in the queue, they do (essentially) a constant amount of work.

Counted Queue

Our Queue ADT did not have an operation that determined the number of items on the queue. Let's define a new class called CountedQueType that is derived from the class QueType and has a data member length that records the number of items on the queue.

typedef char ItemType;
class CountedQueType : public QueType
{
public:
  CountedQueType(int max);
  void Enqueue(ItemType newItem);
  void Dequeue(ItemType& item);
  int LengthIs() const;
  // Returns the number of items on the queue.
private:
  int length;
};
  

The line

class CountedQueType : public QueType

states that CountedQueType is derived from QueType; that is, CountedQueType is the derived class and QueType is the base class. The reserved word public declares QueType to be a public base class of CountedQueType. As a result, all public members of QueType are also public members of CountedQueType. In other words, QueType's member functions Enqueue, Dequeue, IsEmpty, and IsFull can also be invoked for objects of type CountedQueType. The public part of the class CountedQueType further specializes the base class by redefining the inherited functions Enqueue and Dequeue and by adding the data member length, an operation that returns the value of length, and its own class constructor.

Every object of type CountedQueType has an object of type QueType as a subobject. That is, an object of type CountedQueType is an object of type QueType and more. Figure 4.14 shows a class interface diagram for the CountedQueType class. The public interface, shown as ovals at the side of the large circles, consists of the operations available to the client code. The private data items shown in the interior are inaccessible to clients. A dashed line between ovals indicates that the two operations are the same. For example, IsEmpty applied to an object of CountedQueType is the IsEmpty member function defined in type QueType. However, Enqueue applied to an object of type CountedQueType is not the Enqueue defined in QueType, but rather the one defined in CountedQueType.

Click To expand
Figure 4.14: Class interface diagram for CountedQueType class

C++ uses the terms base class and derived class; the corresponding terms superclass and subclass are also used in the literature. The use of "superclass" and "subclass" can prove confusing, however, because the prefix sub usually implies something smaller than the original (for example, a subset of a mathematical set). In reality, a subclass is often "bigger" than its superclass-that is, it includes more data and/or functions.

Implementation of the Derived Class The implementation of the CountedQueType class needs to deal with only the new features that differ from those in QueType. Specifically, we must write the code to override the Enqueue and Dequeue functions, and we must write the LengthIs function and the class constructor. The new Enqueue and Dequeue functions just need to increment or decrement the length data member and call the QueType functions of the same name. LengthIs simply returns the value of length. The class constructor sets length to zero and can use the QueType class constructor to initialize the rest of the class data members. Because Enqueue and Dequeue can throw exceptions, the calls to them must be enclosed within a try/catch statement. We just forward the exceptions to the client's level. Here is the code. A discussion of the syntactic details follows.

#include "CountedQueType.h"

void CountedQueType::Enqueue(ItemType newItem)
{
  try {
  {
    QueType::Enqueue(newItem);
    length++;
  }
  catch(FullQueue)
  {
    throw FullQueue();
  }
}

void CountedQueType::Dequeue(ItemType& item)
{
  try
  {
    QueType::Dequeue(item);
    length--;
  }
  catch(EmptyQueue)
  {
    throw EmptyQueue();
  }
}

int CountedQueType::LengthIs() const
{
  return length;
}

CountedQueType::CountedQueType(int max) : QueType(max)
{
  length = 0;
}

Note two points of syntax here. For Enqueue to invoke the Enqueue defined in QueType, the name of the class must precede the function name, with the scope resolution operator (: :) appearing in between the two names. The same is true for Dequeue. In the class constructor, length is set to zero, but how are front and rear set? The colon followed by QueType (max) after the parameter list of the derived-class constructor causes the invocation of the base-class constructor. This construct (colon followed by a call to the base-class constructor) is known as a constructor initializer.

A class such as QueType can be used as-is in many different contexts or can be adapted to a particular context by using inheritance. Inheritance allows us to create extensible data abstractions-a derived class typically extends the base class by including additional private data or public operations or both.

The items on an instance of a CountedQueType are characters because we extended the QueType that we examined earlier. QueType could be a class template, and CountedQueType could extend that version just as easily. In the next section, we assume that CountedQueType is a class template.

Application of the CountedQueType Class FIFO queues are often used as "waiting lines." Such waiting lines are common on multiuser computer systems and networked systems of workstations. If you use a multiuser or networked computer system, you probably share a printer with other users. When you request a printout of a file, your request is added to a print queue. When your request reaches the front of the print queue, your file is printed. The print queue ensures that only one person at a time has access to the printer and that this access is doled out on a first come, first served basis. Similarly, queues are used to schedule use of other shared resources such as disks and tapes.

Another application area in which queues figure prominently as data structures is the computer simulation of real-world situations. For instance, consider a bank that plans to install drive-up teller windows. The bank should hire enough tellers to service each car within a "reasonable" wait time, but not too many tellers for the number of customers. It may want to run a computer simulation of typical customer transactions, using objects to represent real-world physical objects such as tellers, cars, and a clock. The queue is used to represent the waiting customers.

Queuing simulations usually involve servers (the bank tellers), the items in the queue (people, cars, or whatever is waiting to be served), and the amount of time each item in the queue requires. By varying these parameters and keeping track of the average queue lengths, management can determine how many servers must be employed to keep the customers happy. Therefore, in simulations using queues, the number of items in each queue is important information. Of course, the client program can calculate this information by dequeuing, counting, and enqueuing again, but a derived counted queue is a better choice.

Inheritance and Accessibility Inheritance is a logical issue, not an implementation issue. A class inherits the behavior of another class and enhances it in some way. Inheritance does not mean inheriting access to another class's private variables. Although some languages do allow access to the base class's private members, such access often defeats the purpose of encapsulation and information hiding. C++ does not allow access to the private data members of the base class. Neither external client code nor derived class code can directly access the private members of the base class.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)