Lecture 19 Objectives

KNOW:

• How to use the template stack class defined in Chapter 7
• The two implementations for the stack (array and linked list) presented in Chapter 7
• How a stack is used to implement recursive calls

BE ABLE TO:

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

Sample Exam Question:

A client program executes the following code:

   stack< int > s; 
   s.push(1);
   s.push(2);
   s.push(3);
   cout << s.top( );
   s.pop();

1. Suppose that s is represented by a partially filled array. Draw the state of the private member variables of s after the code executes:

              _______            __________________________________
         used|       |      data|      |      |      |      |      |
             |_______|          |______|______|______|______|______|
                                  [0]    [1]    [2]    [3]    [4]
   
   

2. Suppose that s is represented by a linked list. Draw the state of the private member variables of s after the code executes:

                  _______      
         head_ptr|       |  
                 |_______|