Top of document
©Copyright 1999 Rogue Wave Software

The Queue Data Abstraction

As a data abstraction, a queue is traditionally defined as any object that implements the following operations:

empty()
 return true if the collection is empty
size()
 return number of elements in collection
front()
 return (but do not remove) the element at the front of the queue
back()
 return the element at the end of the queue
push(newElement)
 push a new element on to the end of the queue
pop()
 remove (but do not return) the element at the front of the queue

Include Files

Note that the operations of accessing and of removing the front elements are performed separately. Programs that use the queue data abstraction should include the file queue, as well as the include file for the container type (e.g., list).

   # include <queue>
    # include <list>

Declaration and Initialization of queue

A declaration for a queue must specify both the element type as well as the container that will hold the values. For a queue the most common containers are a list or a deque. The list version is generally smaller, while the deque version may be slightly faster. The following are sample declarations for a queue.

   queue< int, list<int> > queueOne;
    queue< double, deque<double> > queueTwo;
    queue< Part *, list<Part * > > queueThree;
    queue< Customer, list<Customer> > queueFour;

The last example creates a queue of a programmer-defined type named Customer. As with the stack container, all objects stored in a queue must understand the operators < and ==.

Because the queue does not implement an iterator, none of the generic algorithms described in Sections 13 or 14 apply to queues.

Example Program - Bank Teller Simulation

 Obtaining the Sample Program

Queues are often found in businesses, such as supermarkets or banks. Suppose you are the manager of a bank, and you need to determine how many tellers to have working during certain hours. You decide to create a computer simulation, basing your simulation on certain observed behavior. For example, you note that during peak hours there is a ninety percent chance that a customer will arrive every minute.

We create a simulation by first defining objects to represent both customers and tellers. For customers, the information we wish to know is the average amount of time they spend waiting in line. Thus, customer objects simply maintain two integer data fields: the time they arrive in line, and the time they will spend at the counter. The latter is a value randomly selected between 2 and 8. (See Chapter 2 (Varieties of Iterators) for a discussion of the randomInteger() function.)

class Customer {
 public:
    Customer (int at = 0) : arrival_Time(at), 
          processTime(2 + randomInteger(6)) {}
    int arrival_Time;
    int processTime;
    
    bool done()      // are we done with our transaction? 
       { return --processTime < 0; }
       
    operator < (const Customer & c)   // order by arrival time
       { return arrival_Time < c.arrival_Time; }
       
    operator == (const Customer & c)   // no two customers are alike
       { return false; }
 };

Because objects can only be stored in standard library containers if they can be compared for equality and ordering, it is necessary to define the < and == operators for customers. Customers can also tell us when they are done with their transactions.

Tellers are either busy servicing customers, or they are free. Thus, each teller value holds two data fields; a customer, and a boolean flag. Tellers define a member function to answer whether they are free or not, as well as a member function that is invoked when they start servicing a customer.

class Teller {
 public:
    Teller() { free = true; }
    
    bool isFree()   // are we free to service new customer?
       { if (free) return true;
         if (customer.done())
            free = true;
         return free;
        }
 
    void addCustomer(Customer c)   // start serving new customer
       {   customer = c;
          free = false;
       }
 
 private:
    bool free;
    Customer customer;
 };

The main program is then a large loop, cycling once each simulated minute. Each minute a new customer is, with probability 0.9, entered into the queue of waiting customers. Each teller is polled, and if any are free they take the next customer from the queue. Counts are maintained of the number of customers serviced and the total time they spent in queue. From these two values we can determine, following the simulation, the average time a customer spent waiting in the line.

void main() {
    int numberOfTellers = 5;
    int numberOfMinutes = 60;
    double totalWait = 0;
    int numberOfCustomers = 0;
    vector<Teller> teller(numberOfTellers);
    queue< Customer, deque<Customer> > line;
    
    for (int time = 0; time < numberOfMinutes; time++) {
       if (randomInteger(10) < 9)
          line.push(Customer(time));
       for (int i = 0; i < numberOfTellers; i++) {
          if (teller[i].isFree() & ! line.empty()) {
             Customer & frontCustomer = line.front();
             numberOfCustomers++;
             totalWait += (time - frontCustomer.arrival_Time);
             teller[i].addCustomer(frontCustomer);
             line.pop();
             }
          }
       }
    cout << "average wait:" <<
           (totalWait / numberOfCustomers) << endl;
 }

By executing the program several times, using various values for the number of tellers, the manager can determine the smallest number of tellers that can service the customers while maintaining the average waiting time at an acceptable amount.

Top of document