linkedstack.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//链式栈类
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H
#include <iostream>
using namespace std;
template <class E>
struct StackNode {                    //栈结点类定义
 
	E data;			          //栈结点数据
	StackNode<E> *link;            //结点链指针

	StackNode(E d = 0, StackNode<E> *next = NULL)
		: data(d), link(next) { }
};  
template <class E>
class LinkedStack{ //链式栈类定义   
private:
	StackNode<E> *top;		            //栈顶指针
	void output(ostream& os, StackNode <E> *ptr, int& i);
	//递归输出栈的所有元素
public:
	LinkedStack() : top(NULL) {}	   //构造函数
	~LinkedStack() { makeEmpty(); }   //析构函数
	void Push(E x);		             	   //进栈
	bool Pop(E& x);			   //退栈
	bool getTop(E& x) const;		//取栈顶  	
	bool IsEmpty() const { return top == NULL; }
	void makeEmpty();			//清空栈的内容
	void show(); //输出栈元素
};
template <class E>
void LinkedStack<E>::makeEmpty() {	
	//逐次删去链式栈中的元素直至栈顶指针为空。
	StackNode<E> *p;
	while (top != NULL)		//逐个结点释放
	{ p = top;  top = top->link;  delete p; }
};

template <class E>
void LinkedStack<E>::Push(E x) {
	//将元素值x插入到链式栈的栈顶,即链头。
	top = new StackNode<E> (x, top);	//创建新结点
};

template <class E>
bool LinkedStack<E>::Pop(E& x) {
	//删除栈顶结点, 返回被删栈顶元素的值。
	if (IsEmpty() == true) return false;   //栈空返回
	StackNode<E> *p = top;		//暂存栈顶元素
	top = top->link;			//退栈顶指针
	x = p->data;   delete p;		//释放结点
	return true;	
};
template <class E>
bool LinkedStack<E>::getTop(E& x) const {	
	if (IsEmpty() == true) return false;   //栈空返回
	x = top->data;                       //返回栈顶元素的值
	return true;
};

template <class E>
void LinkedStack<E>::show()
{
	StackNode<E> *ptr = top;
	while (ptr != NULL && ptr->link != NULL)
	{
		cout<<ptr->data<<' ';
		ptr=ptr->link;
	}
	cout<<ptr->data<<endl;
}
#endif;