Lecture Objectives

Lecture 18 Objectives

At the end of today's class you should

KNOW:

How to use the template queue class defined in Chapter 8
The two implementations for the queue (array and linked list) presented in Chapter 8

BE ABLE TO:

Analyze each of the queue member functions using big-O analysis
Recognize applications for which a queue is a useful data structure

Sample Exam Question:

In Chapter 8 the authors define a linked list implementation of a class queue with the following private data members:

    private:
        node *front_ptr;
        node *rear_ptr; 
        size_type count;       // Total number of items in the queue

Using the implementation given, write a new public modification member function called makeEmpty. The pre- and post-conditions are given below. Your function should not call any of the linked list toolkit functions. The comments will help you write the function.

// PRE:  none.
// POST: The queue is empty; all nodes have been deallocated.
// Write the complete heading for the function on the next line:


{
   // if the queue is empty, there are no nodes to deallocate, so return



   // otherwise, do the following:
   // declare a local variable that is a pointer to a node (call it p)



   // write a loop that moves front_ptr down the list until
   // it reaches the end of the list
   // for every iteration of the loop, do the following:
   //          make p point to the node that front_ptr points to
   //          move front_ptr down to the next node in the list
   //          delete the node pointed to by p









   // set rear_ptr to NULL


}