linstack.h

数据结构的一些教程....比较适于初学者

// 链式堆栈类的定义与实现
#include "iostream.h"
#include "stdlib.h"

template<class T> class LinStack;   //向前引用说明

template<class T> class StackNode    //定义堆栈结点类模板
{
	friend class LinStack<T>;
	private:
		T data;
		StackNode<T> *next;
	public:
		//构造函数
		StackNode(const T& item, StackNode<T> *ptrNext=NULL)
		{  data=item;  next=ptrNext;   }
		~StackNode()    //析构函数
		{  }
};

template<class T> class LinStack    //定义链式堆栈类模板
{
	StackNode<T> *top;   //T为栈中元素类型,top指向栈顶
	int size;       //栈当前大小
 public:
	LinStack(void)          //构造一个空栈
	{  top=NULL;  size=0;  }
	~LinStack(void);        //析构函数：清空且销毁栈

	int StackSize(void) const   //返回栈大小
	{ return size; }
	bool StackEmpty(void) const   //判别栈是否为空
	{  return size<=0;  }
	void Push(const T& item);   //入栈。item为引用T型便于快速传输
	T Pop(void);                //出栈
	T Peek(void);               //取栈顶元素
	void ClearStack(void);      //清空栈
};

template<class T>
LinStack<T>::~LinStack(void)   //析构函数
{
	ClearStack();    //清空栈
	top=NULL;           //栈顶指针置0
}

template<class T>
void LinStack<T>::Push(const T& item)  //新元素入栈
{
	//利用栈结点构造函数申请一个栈结点，使它指针域指向原栈顶
	StackNode<T> *newNode=new StackNode<T>(item,top);
	top=newNode;  //把新结点作栈顶
	size++;     //栈大小增加1
}

template<class T>
T LinStack<T>::Pop(void)   //栈顶元素出栈
{
	if(size==0) //如果是空栈则报错退出
	{
		cerr<<"栈已空，无元素可删除！"<<endl;
		exit(1);
	}

	StackNode<T> *p=top->next;  //p指向栈顶元素的下一个元素
	T data=top->data;   //保存栈顶元素中的数据
	delete top;    //删除栈顶指针所指结点
	size--;    //栈的大小减1
	top=p;      //重置栈顶指针
	return data;   //返回原栈顶的数据
}

template<class T>
T LinStack<T>::Peek(void)    //读栈顶元素的数据
{
	if(!StackEmpty()) return top->data;
	else
	{ 
		cerr<<"堆栈已空！"<<endl;
		exit(1);
	}
}

template<class T>
void LinStack<T>::ClearStack(void)   //清空栈
{
	StackNode<T> *p,*p1;   //指向栈结点的工作指针

	p=top;
	while(p!=NULL) //从栈顶到栈底逐个删除栈结点
	{
		p1=p;
		p=p->next;
		delete p1;
	}
	size=0;
	top=0;
}