lstack.h

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

// file lstack.h
// linked stack
#ifndef LinkedStack_
#define LinkedStack_

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

template<class T>
class LinkedStack 
{
	friend ostream& operator<<(ostream& ,const LinkedStack<T>&);
	friend istream& operator>>(istream& ,LinkedStack<T>&);
public:
	LinkedStack() 
	{
		top = 0; 
		length=0;
	}
	~LinkedStack();
	bool IsEmpty() const 
	{
		return top == 0;
	}
	bool IsFull() const;
	int Length()const 
	{
		return length;
	}
	T Top() const;
	LinkedStack<T>& Add(const T& x);
	LinkedStack<T>& Delete(T& x);
private:
	Lnode<T> *top; // pointer to top Lnode
	int length;            
};

template<class T>
LinkedStack<T>::~LinkedStack()
{// Stack destructor..
	Lnode<T> *next;
	while (top) 
	{
		next = top->link;
		delete top;
		top = next;
	}
}

template<class T>
bool LinkedStack<T>::IsFull() const
{// Is the stack full?
	try 
	{
		Lnode<T> *p = new Lnode<T>;
		delete p;
		return false;
	}
	catch (NoMem) 
	{
		return true;
	}
}

template<class T>
T LinkedStack<T>::Top() const
{// Return top element.
	if (IsEmpty()) 
		throw OutOfBounds();
	return top->data;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x)
{// Add x to stack.
	Lnode<T> *p = new Lnode<T>;
	p->data = x;
	p->link = top;
	top = p;
	++length;
	return *this;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{// Delete top element and put it in x.
	if (IsEmpty()) 
		throw OutOfBounds();
	x = top->data;
	Lnode<T> *p = top;
	top = top->link;
	delete p;
	--length;
	return *this;
}

template <class T>
ostream& operator<<(ostream& out,const LinkedStack<T>& L)
{
	Lnode<T> *current;
	for (current=L.top;current;current=current->link)
	{
		cout<<current->data<<endl;
	}
	return out;
}

template <class T>
istream& operator>>(istream& in,LinkedStack<T>& L)
{
	T x;
	cin>>x;
	while(x)
	{
		L.Add(x);
		cin>>x;
	}
	return in;
}

#endif;