linkedtypestack.cpp

数据结构中堆栈的具体应用

// LinkedTypeStack.cpp: implementation of the LinkedTypeStack class.
//
//////////////////////////////////////////////////////////////////////

#include "LinkedTypeStack.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

template<class Type>
LinkedTypeStack<Type>::LinkedTypeStack()
{//构造函数
	StackTop=NULL;
}

template<class Type>
LinkedTypeStack<Type>::~LinkedTypeStack()
{
//析构函数
}

template<class Type>
void LinkedTypeStack<Type>::InitStack()
{
//初始化堆栈
	DestroyStack();
}//InitStack

template<class Type>
bool LinkedTypeStack<Type>::IsEmptyStack()
{
//判断堆栈是否为空
	if(StackTop==NULL)
		return TRUE;
	else 
		return FALSE;
}//IsEmptyStack

template<class Type>
bool LinkedTypeStack<Type>::IsFullStack()
{
//判断堆栈是否已满
	return FALSE;
}//IsFullStack

template<class Type>
void LinkedTypeStack<Type>::DestroyStack()
{
//销毁堆栈
	NodeType<Type> *temp;     //指向即将删除的结点
	while(StackTop!=NULL)           //堆栈有内容的时候继续
	{
		temp=StackTop;              //指向栈顶
		StackTop=StackTop->Link;    //指向下一个结点
		delete temp;                //删除结点
	}
}//DestroyStack

template<class Type>
void LinkedTypeStack<Type>::Push(const Type &NewItem)
{
//NewItem入栈
	NodeType<Type> *NewNode;     //新建的结点
	NewNode=new NodeType<Type>;        //生成新的结点
	assert(newNode!=NULL);

	NewNode->info=NewItem;             //存储压栈的内容
	NewNode->Link=StackTop;            //指向下一个结点
	StackTop=NewNode;                  //新的栈顶
}//Push

template<class Type>
Type LinkedTypeStack<Type>::GetTop()
{
//取栈顶元素
	assert(StackTop!=NULL);       //如果栈顶为空，终止程序
	return StackTop->info;        //返回栈顶元素
}//GetTop

template<class Type>
void LinkedTypeStack<Type>::Pop()
{
//出栈
	NodeType<Type> *temp;         //新的结点指针
	//temp=New NodeType<Type>;
	if(StackTop!=NULL)            //如果栈顶不为空
	{
		temp=StackTop;            //指向栈顶
		if(StackTop->Link!=NULL)
		{
			StackTop=StackTop->Link;  //栈顶下移,适合堆栈只有一个元素的情况
		}
		delete temp;              //释放内存空间
	}
	else
		cerr<<"Stack is empty,cannot pop!!!"<<endl;
}//Pop