stack.h

//
// Stack implemented using a dynamically allocated using a linked list
//

#ifndef STACK_H
#define STACK_H

#include <stdexcept>
#include <new>
#include <string>
#include "node.h"

using namespace std;

/*=========================================================================*/

class StackEmpty : public runtime_error {
  public:
    StackEmpty() : runtime_error( "stack empty" ) {}
    StackEmpty( const string &what ) : runtime_error( what ) {}
};

/*=========================================================================*/

template <typename T>
class Stack {

  public:
    Stack();
    Stack( const Stack & ) throw ( bad_alloc );
    ~Stack();
    bool empty() const;
    unsigned size() const;
    void clear();
    void push( const T & ) throw ( bad_alloc );
    T pop() throw ( StackEmpty );
    T &top() const throw ( StackEmpty );
    const Stack<T> &operator=( const Stack<T> & ) throw ( bad_alloc );
  
  private:
    unsigned sz;
    Node<T> *contents;

}; // Stack class

template <typename T>
Stack<T>::Stack()
{
  sz = 0;
  contents = 0;
} // Stack<T>::Stack

template <typename T>
Stack<T>::Stack( const Stack<T> &s ) throw ( bad_alloc )
{
  sz = 0;
  contents = 0;
  *this = s;
} // Stack<T>::Stack

template <typename T>
Stack<T>::~Stack()
{
  clear();
} // Stack<T>::~Stack

template <typename T>
bool Stack<T>::empty() const
{
  return (contents == 0);
} // Stack<T>::empty

template <typename T>
unsigned Stack<T>::size() const
{
  return sz;
} // Stack<T>::size

template <typename T>
void Stack<T>::clear()
{
  Node<T> *current = contents;
  while (contents != 0) {
    contents = contents->getNextPtr();
    delete current;
    current = contents;
  } // while
  sz = 0;
  contents = 0;
} // Stack<T>::clear

template <typename T>
void Stack<T>::push( const T &item ) throw ( bad_alloc )
{
  Node<T> *newNode = new Node<T>( item );
  newNode->setNextPtr( contents );
  contents = newNode;
  sz++;
} // Stack<T>::push

template <typename T>
T Stack<T>::pop() throw ( StackEmpty )
{
  if ( empty() )
    throw StackEmpty( "pop: stack empty" );
  Node<T> *ptr = contents;
  contents = contents->getNextPtr();
  T value = ptr->getObject();
  delete ptr;
  sz--;
  return value;
} // Stack<T>::pop

template <typename T>
T &Stack<T>::top() const throw ( StackEmpty )
{
  if ( empty() )
    throw StackEmpty( "top: stack empty" );
  return contents->getObject();
} // Stack<T>::top

/*
 * Overloaded assignment operator for memberwise copy
 * const return avoids ( s1 = s2 ) = s3
 */

template <typename T>
const Stack<T> &Stack<T>::operator=( const Stack<T> &s ) throw ( bad_alloc )
{
  if ( this != &s ) {  // check for self-assignment
    if ( !empty() )
      clear();
    sz = s.sz;
    Node<T> *meptr = 0, *sptr = s.contents;
    while ( sptr != 0 ) {
      if ( meptr == 0 )
        contents = meptr = new Node<T>( *sptr );
      else {
        meptr->setNextPtr( new Node<T>( *sptr ) );
        meptr = meptr->getNextPtr();
      } // else
      sptr = sptr->getNextPtr();
    } // while
  } // if
  return *this; // enables x = y = z
} // Stack<T>::operator=

#endif // STACK_H

---