linkedtypestack.h

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

// LinkedTypeStack.h: interface for the LinkedTypeStack class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_LINKEDTYPESTACK_H__4A0C589D_B10A_4E3B_9ACB_B8EBC027B783__INCLUDED_)
#define AFX_LINKEDTYPESTACK_H__4A0C589D_B10A_4E3B_9ACB_B8EBC027B783__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define TRUE	1
#define FALSE	0

#include <iostream>
#include <cassert>

//定义结点
template<class Type>
struct NodeType
{
	Type info;
	NodeType<Type> *Link;
};

template<class Type>
class LinkedTypeStack  
{
public:
	inline void Pop();
	inline Type GetTop();
	inline void Push(const Type &NewItem);
	inline void DestroyStack();
	inline bool IsEmptyStack();
	inline void InitStack();
	LinkedTypeStack();
	virtual ~LinkedTypeStack();

private:
	NodeType<Type> *StackTop;
};

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

//////////////////////////////////////////////////////////////////////
// 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>
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

#endif // !defined(AFX_LINKEDTYPESTACK_H__4A0C589D_B10A_4E3B_9ACB_B8EBC027B783__INCLUDED_)