linkedstack.h

数据结构课程设计-八皇后算法的实现。 使用链表堆栈来实现的

#ifndef LINKED_STACK_H
#define LINKED_STACK_H

#include "StackNode.h"
#include "xcept.h"

template<class T>
class LinkedStack
{
	public:
		LinkedStack() ;
		~LinkedStack() ;
		bool IsEmpty() const ;
		bool IsFull() const ;
		int Size() const ;
		T Top() const ;
		LinkedStack<T>& Add(const T &x) ;
		LinkedStack<T>& Delete(T &x) ;
		LinkedStack<T>& Combine(LinkedStack<T> &x) ;
	private:
		StackNode<T> *top ;
		int iTerm ;
};

template<class T>
LinkedStack<T>::LinkedStack()
{
	top = 0 ;
	iTerm = 0 ;
}

template<class T>
LinkedStack<T>::~LinkedStack()
{
	StackNode<T> *next ;
	while(top)
	{
		next = top->link ;
		delete top ;
		top = next ;
	}
}

template<class T>
bool LinkedStack<T>::IsEmpty() const
{
	return top == 0 ;
}

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

template<class T>
int LinkedStack<T>::Size() const
{
	return iTerm ;
}

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

template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T &x)
{
	StackNode<T> *p = new StackNode<T> ;
	p->data = x ;
	p->link = top ;
	top = p ;
	iTerm++ ;
	return *this ;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T &x)
{
	if(IsEmpty())
	{
		throw OutOfBounds() ;
	}
	x = top->data ;
	StackNode<T> *p = top ;
	top = top->link ;
	delete p ;
	iTerm-- ;
	return *this ;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Combine(LinkedStack<T> &x)
{
	StackNode<T> *p = x.top ;
	iTerm ++ ;
	while(p->link)
	{
		p = p->link ;
		iTerm ++ ;
	}
	p->link = top ;
	top = x.top ;
	x.top = 0 ;
	return *this ;
}



#endif