Chapter 8
Queues and Priority Queues
Queues

• example of inserting at rear (back) and deleting from front of list
• properties of queue:
•      list of elements with access only at both ends (front, back).
•      insert at the end, delete from front.
•      first in first out (FIFO), first come first served (FCFS)
• Implementation:
• Use any container that supports the operations:
• size()
• empty()
• push_back()
• front()
• pop_front()
• Containers:
• vector - no pop_front()
• list
• deque - direct access.   It is a "double-ended queue."
• Constructor & Operations:
• queue();
create an empty queue.
• bool empty() const;
• T& front();        const T& front();
Return reference to the value of the front of queue.
• void pop();
Remove the item from the front of queue.
• void push(const T& item);
Insert the argument item at the back of the queue.
• int size() const;
• Example 8-1 on page 387
queue<int> q;
q.push(2);
q.push(3);
q.push(99);

while (!q.empty())
{
   cout<<q.front()<<" ";
   q.pop():
}

• Example of queue & stack
• miniQueue: use a list object, qlist to implement
// insert item into the queue by inserting it at
// the back of the list
template <typename T>
void miniQueue<T>::push(const T& item)
{
 qlist.push_back(item);
}

// remove the item at the front of the queue
// by erasing the front of the list
template <typename T>
void miniQueue<T>::pop()
{
 // if queue is empty, throw underflowError
 if (qlist.size() == 0)
  throw underflowError("miniQueue pop(): empty queue");

 // erase the front
 qlist.pop_front();
}

Click here to see the whole class definition.
• Example 8-3 (pages 398-399)
queue<int, list<int> > qList;
queue<int, deque<int> > qDeque;
int value;

cout << "Enter an integer > 0 or 0 to quit: ";
cin >> value;

while (value != 0)
{
  if (value % 2 == 0)
     qList.push(value);
  else
     qDeque.push(value);

  cout << "Enter an integer > 0 or 0 to quit: ";
  cin >> value;
}
cout <<endl << "Even number: ";
while (!qList.empty())
{
   cout << qList.front() << " ";
   qList.pop();
}
cout <<endl <<endl;

cout<< "Odd numbers: ";
while (!qDeque.empty())
{
   cout << qDeque.front() << " ";
   qDeque.pop();
}
cout <<endl;
 

• Bounded-Queue:  Array-Based Queue

See Circular - Queue, figures 8-4 & 8-5 on pages 410

• Similar to queue, the operation 'insert' is same as queue.

However, delete the most important (highest priority)element from the list.

T& top();

Return a reference to the element having the highest priority.

• Program 1 (pages 388-389)  Job Interview Scheduling
• Program 2 (pages 393-395)  Radix Sort
• Program 3 (pages 403-406)  Time-Driven Simulation
• Program 4 (pages 418-421)  Managing a Secretarial Pool