Exercise 5.1

Implement a two-level stack hierarchy. The base class is a pure abstract Stack class that minimally supports the following interface: pop(), push(), size(), empty(), full(), peek(), and print(). The derived classes are LIFO_Stack and Peekback_Stack. The Peekback_Stack allows the user to retrieve the value of any element in the stack without modifying the stack itself.

The two derived classes implement the actual element container using a vector. To display the vector, I use a const_reverse_iterator. This supports traversing the vector from the back to the front.

#include <string> 


#include <iostream> 


#include <vector> 


using namespace std; 





typedef string elemType; 


class Stack { 


public: 


    virtual ~Stack(){} 


    virtual bool pop( elemType& ) = 0; 


    virtual bool push( const elemType& ) = 0; 


    virtual bool peek( int index, elemType& ) = 0; 





    virtual int  top() const = 0; 


    virtual int  size() const = 0; 





    virtual bool empty() const = 0; 


    virtual bool full() const = 0; 


    virtual void print( ostream& =cout ) const = 0; 


}; 





ostream& operator<<( ostream &os, const Stack &rhs ) 


      { rhs.print(); return os; } 





class LIFO_Stack : public Stack { 


public: 


   LIFO_Stack( int capacity = 0 ) : _top( 0 ) 


        { if ( capacity ) _stack.reserve( capacity ); } 


   int  size()  const { return _stack.size(); } 


   bool empty() const { return ! _top; } 


   bool full()  const { return size() >= _stack.max_size(); } 


   int  top()   const { return _top; } 


   void print( ostream &os=cout ) const; 





   bool pop(  elemType &elem ); 


   bool push( const elemType &elem ); 


   bool peek( int, elemType& ){ return false; } 


private: 


   vector< elemType > _stack; 


   int _top; 


}; 





bool LIFO_Stack::pop( elemType &elem ){ 


     if ( empty() ) return false; 


     elem = _stack[ --_top ]; 


     _stack.pop_back(); 


     return true; 


} 





bool LIFO_Stack::push( const elemType &elem ){ 


     if ( full() ) return false; 


     _stack.push_back( elem ); 


     ++_top; 


     return true; 


} 





void LIFO_Stack::print( ostream &os=cout ) const { 


    vector<elemType>::const_reverse_iterator 


           rit = _stack.rbegin(), 


           rend = _stack.rend(); 





    os << "\n\t"; 


    while ( rit != rend ) 


            os << *rit++ << "\n\t"; 





    os << endl; 


} 

The implementation of the Peekback_Stack duplicates that of LIFO_Stack except for the implementation of peek():

bool Peekback_Stack:: 


peek( int index, elemType &elem ) 


{ 


    if ( empty() ) 


         return false; 





    if ( index < 0 || index >= size() ) 


         return false; 





    elem = _stack[ index ]; 


    return true; 


} 

Here is a small program that exercises the inheritance hierarchy. The nonmember peek() instance accepts an abstract Stack reference and invokes the virtual peek() member function, which is unique to each derived class.

void peek( Stack &st, int index ) 


{ 


   cout  << endl; 


   string t; 


   if ( st.peek( index, t )) 


        cout << "peek: " << t; 


   else cout << "peek failed!"; 


   cout << endl; 


} 





int main() 


{ 


   LIFO_Stack st; 


   string str; 


   while ( cin >> str && ! st.full() ) 


           st.push( str ); 





   cout << '\n' << "About to call peek() with LIFO_Stack" << endl; 


   peek( st, st.top()-1 ); 


   cout << st; 





   Peekback_Stack pst; 





   while ( ! st.empty() ){ 


      string t; 


      if ( st.pop( t )) 


           pst.push( t ); 


   } 





   cout << "About to call peek() with Peekback_Stack" << endl; 


   peek( pst, pst.top()-1 ); 


   cout << pst; 


} 

When compiled and executed, this program generates the following output:

once upon a time 


About to call peek() with LIFO_Stack 


peek failed! 





     time 


     a 


     upon 


     once 





 About to call peek() with Peekback_Stack 


 peek: once 





     once 


     upon 


     a 


     time