Code Listings Chapter 7

Listing 7-1  The header file for an array-based stack

/** ADT stack: Array-based implementation.
@file ArrayStack.h */
#ifndef _ARRAY_STACK
#define _ARRAY_STACK
#include "StackInterface.h"
const int MAX_STACK = maximum - size - of - stack;

template < class ItemType > class ArrayStack:public StackInterface < ItemType >
{
private:
  ItemType items[MAX_STACK];	// Array of stack items
  int top;	// Index to top of stack

public:
  ArrayStack ();	// Default constructor
  bool isEmpty () const;

  bool push (const ItemType & newEntry);

  bool pop ();

  ItemType peek () const;
};  // end ArrayStack

#include "ArrayStack.cpp"
#endif

Listing 7-2  The implementation file for an array-based stack

/** @file ArrayStack.cpp */
#include <cassert> 	// For assert
#include "ArrayStack.h"	// Header file
template < class ItemType > ArrayStack < ItemType >::ArrayStack ():top (-1)
{
}   // end default constructor

// Copy constructor and destructor are supplied by the compiler
template < class ItemType > bool ArrayStack < ItemType >::isEmpty () constconst
{
  return top < 0;
}   // end isEmpty

template < class ItemType > bool ArrayStack < ItemType >::push (const ItemType & newEntry)
{
  bool result = false;

  if (top < MAX_STACK - 1)	// Does stack have room for newEntry?
    {
      top++;
      items[top] = newEntry;
      result = true;
    }	// end if
  return result;
}   // end push

template < class ItemType > bool ArrayStack < ItemType >::pop ()
{
  bool result = false;

  if (!isEmpty ())
    {
      top--;
      result = true;
    }	// end if
  return result;
}   // end pop

template < class ItemType > ItemType ArrayStack < ItemType >::peek () constconst
{
  assert (!isEmpty ());	// Enforce precondition
// Stack is not empty; return top
  return items[top];
}   // end peek

// end of implementation file

Listing 7-3  The header file for the class LinkedStack

/** ADT stack: Link-based implementation.
@file LinkedStack.h */
#ifndef _LINKED_STACK
#define _LINKED_STACK
#include "StackInterface.h"
#include "Node.h"
template < class ItemType > class LinkedStack:public StackInterface < ItemType >
{
private:
  Node < ItemType > *topPtr;	// Pointer to first node in the chain;
// this node contains the stacks top
public:
// Constructors and destructor:
  LinkedStack ();	// Default constructor
  LinkedStack (const LinkedStack < ItemType > &aStack);	// Copy constructor

  virtual ~ LinkedStack ();	// Destructor
// Stack operations:
  bool isEmpty () const;

  bool push (const ItemType & newItem);

  bool pop ();

  ItemType peek () const;
};  // end LinkedStack

#include "LinkedStack.cpp"
#endif

Listing 7-4   The implementation file for the class LinkedStack

/** @file LinkedStack.cpp */
#include <cassert> 	// For assert
#include "LinkedStack.h"	// Header file
template < class ItemType > LinkedStack < ItemType >::LinkedStack ():topPtr (nullptr)
{
}   // end default constructor

template < class ItemType > LinkedStack < ItemType >::LinkedStack (const LinkedStack < ItemType > &aStack)
{
// Point to nodes in original chain
  Node < ItemType > *origChainPtr = aStack->topPtr;
  if (origChainPtr == nullptr)
    topPtr = nullptr;	// Original bag is empty
  else
    {
// Copy first node
      topPtr = new Node < ItemType > ();
      topPtr->setItem (origChainPtr->getItem ());
// Point to first node in new chain
      Node < ItemType > *newChainPtr = topPtr;
// Copy remaining nodes
      while (origChainPtr != nullptr)
	{
// Advance original-chain pointer
	  origChainPtr = origChainPtr->getNext ();
// Get next item from original chain
	  ItemType nextItem = origChainPtr->getItem ();

// Create a new node containing the next item
	  Node < ItemType > *newNodePtr = new Node < ItemType > (nextItem);
// Link new node to end of new chain
	  newChainPtr->setNext (newNodePtr);
// Advance pointer to new last node
	  newChainPtr = newChainPtr->getNext ();
	}	// end while
      newChainPtr->setNext (nullptr);	// Flag end of chain
    }	// end if
}   // end copy constructor

template < class ItemType > LinkedStack < ItemType >::~LinkedStack ()
{
// Pop until stack is empty
  while (!isEmpty ())
    pop ();
}   // end destructor

template < class ItemType > bool LinkedStack < ItemType >::isEmpty () constconst
{
  return topPtr == nullptr;
}   // end isEmpty

template < class ItemType > bool LinkedStack < ItemType >::push (const ItemType & newItem)
{
  Node < ItemType > *newNodePtr = new Node < ItemType > (newItem, topPtr);
  topPtr = newNodePtr;
  newNodePtr = nullptr;
// end push
  template < class ItemType > bool LinkedStack < ItemType >::pop ()
  {
    bool result = false;

    if (!isEmpty ())
      {
// Stack is not empty; delete top
	Node < ItemType > *nodeToDeletePtr = topPtr;
	topPtr = topPtr->getNext ();
// Return deleted node to system
	nodeToDeletePtr->setNext (nullptr);
	delete nodeToDeletePtr;

	nodeToDeletePtr = nullptr;
	result = true;
      }	// end if
    return result;
  } // end pop
  template < class ItemType > ItemType LinkedStack < ItemType >::peek ()const
  {
    assert (!isEmpty ());	// Enforce precondition
// Stack is not empty; return top
    return topPtr->getItem ();
  } // end getTop
// end of implementation file

Listing 7-5 The header file for the class PrecondViolatedExcep

/** @file PrecondViolatedExcep.h */
#ifndef _PRECOND_VIOLATED_EXCEP
#define _PRECOND_VIOLATED_EXCEP
#include 
#include 
using namespace std;

class PrecondViolatedExcep:public logic_error
{
  public:PrecondViolatedExcep (const string & message = "");
};  // end PrecondViolatedExcep
#endif

Listing 7-6 The implementation file for the class PrecondViolatedExcep

/** @file PrecondViolatedExcep .cpp */
#include " PrecondViolatedExcep .h"
PrecondViolatedExcep::PrecondViolatedExcep (const string & message):
     logic_error ("Precondition Violated Exception: " + message)
{
}   // end constructor