Thinking In C++. Volume 2: Practical Programming

Just as with a stack, when you use a queue, it’s only a queue and doesn’t have any of the other functionality of the basic sequence containers. This includes the ability to get an iterator in order to step through the stack. However, the underlying sequence container (that the queue is built upon) is held as a protected member inside the queue, and the identifier for this member is specified in the C++ Standard as ‘c’, which means that you can derive from queue to access the underlying implementation. The CustomerQ class does exactly that, for the sole purpose of defining an ostream operator<< that can iterate through the queue and print out its members.

The driver for the simulation is the while loop in main( ), which uses processor ticks (defined in ) to determine if the simulation has run for at least 5 seconds. At the beginning of each pass through the loop, a random number of customers is added, with random service times. Both the number of tellers and the queue contents are displayed so you can see the state of the system. After running each teller, the display is repeated. At this point, the system adapts by comparing the number of customers and the number of tellers; if the line is too long, another teller is added, and if it is short enough, a teller can be removed. In this adaptation section of the program you can experiment with policies regarding the optimal addition and removal of tellers. If this is the only section that you’re modifying, you might want to encapsulate policies inside different objects. We’ll revisit this problem with a multithreaded solution in Chapter 10^.

Priority queues

When you push( ) an object onto a priority_queue, that object is sorted into the queue according to a function or function object. (You can allow the default less template to supply this, or you can provide one of your own.) The priority_queue ensures that when you look at the top( ) element, it will be the one with the highest priority. When you’re done with it, you call pop( ) to remove it and bring the next one into place. Thus, the priority_queue has nearly the same interface as a stack, but it behaves differently.

Like stack and queue, priority_queue is an adapter that is built on top of one of the basic sequences—the default is vector.

It’s trivial to make a priority_queue that works with ints:

//: C07:PriorityQueue1.cpp

#include

#include

#include

#include

using namespace std;

int main() {

  priority_queue pqi;

  srand(time(0)); // Seed random number generator

  for(int i = 0; i < 100; i++)

    pqi.push(rand() % 25);

  while(!pqi.empty()) {

    cout << pqi.top() << ' ';

    pqi.pop();

  }

} ///:~

This pushes into the priority_queue 100 random values from 0 to 24. When you run this program you’ll see that duplicates are allowed, and the highest values appear first. To show how you can change the ordering by providing your own function or function object, the following program gives lower-valued numbers the highest priority:

//: C07:PriorityQueue2.cpp

// Changing the priority

#include

#include

#include

#include

#include

using namespace std;

int main() {

  priority_queue, greater > pqi;

  srand(time(0));

  for(int i = 0; i < 100; i++)

    pqi.push(rand() % 25);

  while(!pqi.empty()) {

    cout << pqi.top() << ' ';

    pqi.pop();

  }

} ///:~

A more interesting problem is a to-do list, in which each object contains a string and a primary and secondary priority value:

//: C07:PriorityQueue3.cpp

// A more complex use of priority_queue

#include

#include

#include

using namespace std;

class ToDoItem {

  char primary;

  int secondary;

  string item;

public:

  ToDoItem(string td, char pri ='A', int sec =1)

    : item(td), primary(pri), secondary(sec) {}

  friend bool operator<(

    const ToDoItem& x, const ToDoItem& y) {

    if(x.primary > y.primary)

      return true;

    if(x.primary == y.primary)

      if(x.secondary > y.secondary)

        return true;

    return false;

  }

  friend ostream&

  operator<<(ostream& os, const ToDoItem& td) {

    return os << td.primary << td.secondary

      << ": " << td.item;

  }

};

int main() {

  priority_queue toDoList;

  toDoList.push(ToDoItem("Empty trash", 'C', 4));

  toDoList.push(ToDoItem("Feed dog", 'A', 2));

  toDoList.push(ToDoItem("Feed bird", 'B', 7));

  toDoList.push(ToDoItem("Mow lawn", 'C', 3));

  toDoList.push(ToDoItem("Water lawn", 'A', 1));

  toDoList.push(ToDoItem("Feed cat", 'B', 1));

  while(!toDoList.empty()) {

    cout << toDoList.top() << endl;

    toDoList.pop();

  }

} ///:~

The ToDoItem’s operator< must be a nonmember function for it to work with less< >. Other than that, everything happens automatically. The output is:

A1: Water lawn

A2: Feed dog

B1: Feed cat

B7: Feed bird

C3: Mow lawn

C4: Empty trash