该文章主要介绍栈的链式存储结构以及相关运算。
头文件：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.cpp
#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;
}