APStack 

Declaration

#include "apvector.h"                  // used for stack implementation - class for 1-D arrays with bounds checking

template <class itemType>
class apstack
{
  public:
   
  // constructors/destructor

    apstack( );                            // construct empty stack
    apstack( const apstack & s );            // copy constructor
    ~apstack( );                           // destructor

  // assignment

    const apstack & operator = ( const apstack & rhs );

  // accessors

    const itemType & top( )      const;   // return top element (NO pop)
    bool             isEmpty( )  const;   // return true if empty, else false
    int              length( )   const;   // return number of elements in stack

  // modifiers

    void push( const itemType & item );   // push item onto top of stack
    void pop( );                          // pop top element
    void pop( itemType & item );          // combines pop and top
    void makeEmpty( );                    // make stack empty (no elements)

  private:

    int myTop;                            // index of top element
    apvector<itemType> myElements;        // storage for stack
};

  // **********************************************************************
  //
  // Specifications for stack functions
  //
  // Any violation of a function's precondition will result in an error message
  // followed by a call to abort.
  //
  //
  // constructors/destructor
  //
  //  apstack( )
  //    postcondition: the stack is empty
  //
  //  apstack( const apstack & s )
  //    postcondition: stack is a copy of s
  //
  //  ~apstack( )
  //    postcondition: stack is destroyed
  //
  // assignment
  //
  //  const apstack & operator = ( const apstack & rhs )
  //    postcondition: normal assignment via copying has been performed
  //
  // accessors
  //
  //  const itemType & top( ) const
  //    precondition: stack is [e1, e2, ... en] with n >= 1
  //    postcondition: returns en
  //
  //  bool isEmpty( ) const
  //     postcondition: returns true if stack is empty, false otherwise
  //
  //  int length( ) const
  //     postcondition: returns # of elements currently in stack
  //
  // modifiers
  //
  //  void push( const itemType & item )
  //     precondition: stack is [e1, e2...en] with  n >= 0
  //     postcondition: stack is [e1, e2, ... en, item]
  //
  //  void pop( )
  //     precondition: stack is [e1, e2, ... en] with n >= 1
  //     postcondition: stack is [e1, e2, ... e(n-1)]
  //
  //
  //  void pop(itemType & item )
  //     precondition: stack is [e1,e2,...en] with n >= 1
  //     postcondition: stack is [e1,e2,...e(n-1)] and item == en
  //
  //  void makeEmpty( )
  //     postcondition:  stack is empty
  //
  //  Examples of variable definition
  //
  //    apstack<int> istack;                    // creates empty stack of integers
  //    apstack<double> dstack;                 // creates empty stack of doubles
  //

#include "apstack.cpp"        // kludge, added on 4/7/97

#endif
 

Implementation

#include <stdlib.h>

const int SDEFAULT_SIZE = 10;        // default initial stack size

template <class itemType>
apstack<itemType>::apstack( )
    : myTop(-1),
      myElements(SDEFAULT_SIZE)
    
// postcondition: the stack is empty    
{
   
}

template <class itemType>
apstack<itemType>::apstack(const apstack<itemType> & s)
   : myTop(s.myTop),    
     myElements(s.myElements)

// postcondition: stack is a copy of s    
{
   
}
    
template <class itemType>
apstack<itemType>::~apstack()
// postcondition: stack is destroyed
{
    // vector destructor frees memory
}

template <class itemType>
const apstack<itemType> &
apstack<itemType>::operator = (const apstack<itemType> & rhs)
// postcondition: normal assignment via copying has been performed
{
    if (this != &rhs)
    {
        myTop = rhs.myTop;
        myElements = rhs.myElements;
    }
    return *this;
}

template <class itemType>
bool
apstack<itemType>::isEmpty() const
// postcondition: returns true if stack is empty, false otherwise
{
    return myTop == -1;
}

template <class itemType>
int
apstack<itemType>::length() const
// postcondition: returns # of elements currently in stack
{
    return myTop+1;
}

template <class itemType>
void
apstack<itemType>::push(const itemType & item)
// precondition: stack is [e1, e2...en] with  n >= 0
// postcondition: stack is [e1, e2, ... en, item]    
{
    if( myTop + 1 >= myElements.length() )   // grow vector if necessary
    {
        myElements.resize(myElements.length() * 2);
    }
    myTop++;                           // new top most element
    myElements[myTop ] = item;
}

template <class itemType>
void
apstack<itemType>::pop()
// precondition: stack is [e1,e2,...en] with n >= 1
// postcondition: stack is [e1,e2,...e(n-1)]
{
    if (isEmpty())
    {
        cerr << "error, popping an empty stack" << endl;
        abort();
    }
    myTop--;
}

template <class itemType>
void
apstack<itemType>::pop(itemType & item)
// precondition: stack is [e1,e2,...en] with n >= 1
// postcondition: stack is [e1,e2,...e(n-1)] and item == en    
{
    if (isEmpty())
    {
        cerr << "error, popping an empty stack" << endl;
        abort();
    }
    item = myElements[myTop];
    myTop--;
}

template <class itemType>
const itemType &
apstack<itemType>::top() const
// precondition: stack is [e1, e2, ... en] with n >= 1
// postcondition: returns en
{
    if (isEmpty())
    {
        cerr << "error, popping an empty stack" << endl;
        abort();
    }   
    return myElements[myTop];
}

template <class itemType>
void
apstack<itemType>::makeEmpty()
// postcondition:  stack is empty    
{
    myTop = -1;   
}