linstack.h.txt

数据结构（c++语言描述）链式堆栈类的定义和实现

template <class T> class LinStack;			//前视定义,否则友元无法定义

template <class T>							//模板类型为T
class StackNode
{
	friend class LinStack<T>;				//定义类LinStack<T>为友元
private:
	T data;									//数据元素
	StackNode<T> *next;	    				//指针
public:
	//构造函数1,用于构造头结点
	StackNode(StackNode<T> *ptrNext = NULL)
		{next = ptrNext;}
	
	//构造函数2,用于构造其他结点
	StackNode(const T& item, StackNode<T> *ptrNext = NULL)
		{data = item;	next = ptrNext;}

	~StackNode(){};
};

template <class T>
class LinStack
{
private:
	StackNode<T> *head;				//头指针
	int size;						//数据元素个数
public:
	LinStack(void);					//构造函数
	~LinStack(void);				//析构函数

	void Push(const T& item);		//入栈
	T Pop(void);					//出栈
	T GetTop(void)const;			//取栈顶元素
	int NotEmpty(void) const;		//堆栈非空否
};
 
//堆栈类的实现  
template <class T> 
LinStack<T>::LinStack()				//构造函数
{
	head = new StackNode<T>;		//头指针指向头结点
	size = 0;						//size的初值为0
}

template <class T>
LinStack<T>::~LinStack(void)		//析构函数
//释放所有动态申请的结点空间
{ 
	StackNode<T> *p, *q;

	p = head;						//p指向头结点
	while(p != NULL)				//循环释放结点空间
	{
       	q = p;
		p = p->next;
		delete q;
	}
}

template <class T>
int LinStack<T>::NotEmpty(void) const	//堆栈非空否
{
	if(size != 0) return 1;
	else return 0;
}
	
template <class T>
void LinStack<T>::Push(const T& item)			//入栈
{
	//新结点newNode的data域值为item，next域值为 head->next
	StackNode<T> *newNode = new StackNode<T>(item, head->next);

	head->next = newNode;						//新结点插入栈顶
	size++;										//元素个数加1
}

template <class T>
T LinStack<T>::Pop(void)						//出栈
{
	if(size == 0) 
	{
		cout << "堆栈已空无元素可删！" << endl;
		exit(0);
	}
		
	StackNode<T> *p = head->next;	//p指向栈顶元素结点
	T data = p->data;				
	head->next = head->next->next;	//原栈顶元素结点脱链
	delete p;						//释放原栈顶结点空间
	size--;							//结点个数减1
	return data;					//返回原栈顶结点的data域值
}

template <class T>
T LinStack<T>::GetTop(void)const			//取栈顶元素
{
	return head->next->data;
}