linstack.h

数据结构c++-书的一些源代码

#include <iostream.h>
#include <stdlib.h>

template <class T> class LinStack;			//前视定义,否则友元无法定义
template <class T>							//模板类型为T
class StackNode
{
		friend class LinStack<T>;					//定义类LinStack<T>为友元
		private:
			StackNode<T> *next;	    				//指向下一结点的指针
		public:
			T data;								//定义为公有成员方便使用
			//构造函数	
			StackNode(const T& item, StackNode<T> *ptrNext = NULL);
			~StackNode(){};
};

template<class T>
StackNode<T>::StackNode(const T &item, StackNode<T> *ptrNext)
{
	data = item;
	next = ptrNext;
}

template <class T>
class LinStack
{
		private:
			StackNode<T> *top;				//指向表头的指针
			int size;						//单堆栈的结点个数
   		public:
    		LinStack(void);					//构造函数
			~LinStack(void);				//析构函数
			int StackSize(void) const;		//返回堆栈的结点个数
			int StackEmpty(void) const;		//堆栈空否,空返回1;否则返回0
			void Push(const T& item);	//把数据域值为item的结点插入栈顶
			T Pop(void);				//把栈顶结点出栈并返回栈顶元素
			T Peek(void);					//返回栈顶结点的data值
			void ClearStack(void);			//清空堆栈为初始化状态
};
 
//堆栈类的实现  
template <class T> 
LinStack<T>::LinStack()				//构造函数
{
		top = NULL;					//头指针指向头结点
		size = 0;					//定义size的初值为0
}

template <class T>
LinStack<T>::~LinStack(void)		//析构函数
{ 
		ClearStack();				//释放所有结点
		top = NULL;
}

template <class T>
int LinStack<T>::StackSize(void) const	//返回堆栈的结点个数
{
		return size;
}

template <class T>
int LinStack<T>::StackEmpty(void) const	//堆栈空否,空返回1;否则返回0
{
		if(size <= 0) return 1;
		else return 0;
}
	
template <class T>
void LinStack<T>::Push(const T& item)
//把数据域值为item的结点插入栈顶
{
		//构造新结点newNode，newNode的data域值为item，next域值为 top
		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;				//保存原栈顶结点的data域值
		delete top;						//释放原栈顶结点空间
		size--;							//结点个数减1
		top = p;						//top指向新的栈顶结点
		return data;					//返回原栈顶结点的data域值
}

template <class T>
T LinStack<T>::Peek(void)				//返回栈顶结点的data值
{
		return top->data;
}

template <class	T>	
void LinStack<T>::ClearStack(void)		//清空堆栈为初始化状态
{
		StackNode<T> *p, *p1;

		p = top;						//p指向第一个结点
		while(p != NULL)				//循环释放结点空间直至初始化状态
		{
        	p1 = p;
			p = p->next;
			delete p1;
		}
		size = 0;						//结点个数置为初始化值0
}