栈——链式存储结构及其基本运算

该文章主要介绍栈的链式存储结构以及相关运算。ios

头文件：LinkStack.h算法

#ifndef LINKSTACK_H_
#define LINKSTACK_H_
const int MaxSize = 100;
template <typename T>
struct LinkStack			//链栈结点类
{
	T data;					//数据域
	LinkStack *next;		//指针域
};
template <typename T>
class LinkStackClass		//链栈类
{
	LinkStack<T> *head;		//链栈头结点
public:
	//==================链栈的基本运算算法===========================
	LinkStackClass();		//构造函数
	~LinkStackClass();		//析构函数
	bool StackEmpty();		//判栈空算法
	void Push(T e);			//进栈算法
	bool Pop(T &e);			//出栈算法
	bool GetTop(T &e);		//取栈顶元素
};
//==================链栈的其余运算算法===========================
template <typename C>
void Reverse(LinkStackClass<C> &L);//将链栈中的元素逆置

#endif

源文件：LinkStack.cpp函数

#include <iostream>
#include "LinkStack.h"
//==================链栈的基本运算算法===========================
template <typename T>
LinkStackClass<T>::LinkStackClass()		//构造函数
{
	head = new LinkStack<T>();
	head->next = NULL;
}
template <typename T>
LinkStackClass<T>::~LinkStackClass()	//析构函数
{
	LinkStack<T> *pre = head, *p = pre->next;
	while (p != NULL)
	{
		delete pre;
		pre = p;							
		p = p->next;
	}
	delete pre;
}
template <typename T>
bool LinkStackClass<T>::StackEmpty()	//判栈空算法
{
	return (head->next == NULL);
}
template <typename T>
void LinkStackClass<T>::Push(T e)		//进栈算法
{
	LinkStack<T> *p = new LinkStack<T>();
	p->data = e;							
	p->next = head->next;					
	head->next = p;
}
template <typename T>
bool LinkStackClass<T>::Pop(T &e)		//出栈算法
{
	LinkStack<T> *p;
	if (head->next == NULL)				//栈空的状况
		return false;
	p = head->next;						
	e = p->data;
	head->next = p->next;					
	delete p;							
	return true;
}
template <typename T>
bool LinkStackClass<T>::GetTop(T &e)	//取栈顶元素
{
	LinkStack<T> *p;
	if (head->next == NULL)				
		return false;
	p = head->next;						
	e = p->data;
	return true;
}
//==================链栈的其余运算算法===========================
template <typename C>
void Reverse(LinkStackClass<C> &L)
{
	C *temp = new C[MaxSize];
	int i = 0;
	while (!L.StackEmpty())
	{
		C stacktop;
		L.Pop(stacktop);
		temp[i] = stacktop;
		i++;
	}
	int j = 0;
	while (j < i)
	{
		L.Push(temp[j]);
		j++;
	}
	delete[]temp;
}

主函数：main.cppspa

#include "LinkStack.cpp"

using namespace std;
//====================链栈的基本运算算法====================
void main()
{	
	//===
	LinkStackClass<char> st;			//定义一个字符链栈st
	char e;
	cout << "创建空栈st\n";
	cout << "栈st" << (st.StackEmpty()?"空":"不空") << endl;
	cout << "字符a进栈\n"; st.Push('a');
	cout << "字符b进栈\n"; st.Push('b');
	cout << "字符c进栈\n"; st.Push('c');
	cout << "字符d进栈\n"; st.Push('d');
	cout << "字符e进栈\n"; st.Push('e');
	cout << "栈st" << (st.StackEmpty()?"空":"不空") << endl;
	st.GetTop(e);
	cout << "栈顶元素:" << e << endl;
	cout << endl<<endl;

	//===
	cout << "逆置链栈中全部元素" << endl;
	Reverse<char>(st);
	cout << "出栈序列:";
	while (!st.StackEmpty())
	{
		st.Pop(e);
		cout << e << " ";
	}
	cout << endl;
	cout << "销毁链栈st" << endl;
}