stack.h

常用算法与数据结构原代码

// file stack.h
// formula-based stack

#ifndef Stack_
#define Stack_

#include <iostream.h>
#include "xcept.h"
#include "resize1d.h"

template<class T>
class Stack
{
	// LIFO objects
	friend ostream& operator<<(ostream& ,const Stack<T>&);
	friend istream& operator>>(istream& ,Stack<T>&);
public:
	Stack(int MaxStackSize = 10);
	~Stack() {delete [] stack;}
	bool IsEmpty() const 
	{
		return top == -1;
	}
	bool IsFull() const;
	int Length() const 
	{
		return top+1;
	}
	T Top() const;

	Stack<T>& Add(const T& x);
	Stack<T>& Delete(T& x);
private:
	int top;    // current top of stack
	int MaxTop; // max value for top
	T *stack;   // element array
};

template<class T>
Stack<T>::Stack(int MaxStackSize)
{// Stack constructor.
	MaxTop = MaxStackSize - 1;
	stack = new T[MaxStackSize];
	top = -1;
}

template<class T>
T Stack<T>::Top() const
{// Return top element.
	if (IsEmpty()) 
		throw OutOfBounds(); // Top fails
	return stack[top];
}

template<class T>
bool Stack<T>::IsFull() const
{// Check if stack is full.

   if (top < MaxTop) 
	   return false;
   // see if array expansion possible
   try 
   {
	   T *temp = new T [2 * MaxTop + 1];
	   // expansion is possible
	   delete temp;
	   return false;
   }
   catch (...) 
   {
	   // expansion is not possible
	   return true;
   }
}

template<class T>
Stack<T>& Stack<T>::Add(const T& x)
{// Add x to stack.
	if (top == MaxTop)
	{// double capacity
		MaxTop = 2 * MaxTop + 1;
		ChangeSize1D(stack,  top+1, MaxTop+1);
	}
	stack[++top] = x;
	return *this;
}

template<class T>
Stack<T>& Stack<T>::Delete(T& x)
{// Delete top element and put in x.
	if (IsEmpty()) 
		throw OutOfBounds(); // delete fails

	x = stack[top--];
	if ((top + 1 <= (MaxTop + 1)/4) && MaxTop > 0) 
	{
		// halve the capacity
		MaxTop = (MaxTop - 1)/2;
		ChangeSize1D(stack, top + 1, MaxTop + 1);
	}
	return *this;
}

template<class T>
ostream& operator<<(ostream& out,const Stack<T>& S)
{
	// output stack size
   out << "The stack has " << (S.top + 1)
       << " element(s)" << endl;

	// output stack elements
   out << "The element(s) from top to bottom are"
       << endl;
   for (int i = S.top; i >= 0 ; i--)
      out << S.stack[i] << ' ';
   out << endl;

	return out;
}

template <class T>
istream& operator>>(istream& in,Stack<T>& S)
{
	// input and verify stack size
   int size;
   cout << "Enter size of stack" << endl;
   in >> size;
   if (size > s.MaxTop + 1) 
	   throw NoMem(); // fail

   s.top = size - 1;

   // input the stack elements and store in array
   cout << "Enter the elements from top to bottom"
        << endl;
   for (int i = s.top; i >= 0 ; i--)
      in >> s.stack[i];

   return in;
}
#endif