数据结构--链栈C++(模板类实现)
作者:
AmbitionX
,
2022-05-03 14:20:57
,
所有人可见
,
阅读 175
#include <iostream>
using namespace std;
template <typename DataType>
struct Node
{
DataType data;
Node<DataType> * next;
};
template <typename DataType>
class LinkStack
{
public:
LinkStack(); // 构造函数 初始化 链栈
~LinkStack(); // 析构函数 销毁链栈
void Push(DataType x); // 入栈操作,将元素x入栈
DataType Pop(); // 出栈操作,将栈顶元素出栈
DataType GetTop(); // 取出栈顶元素,不删除
void Empty(); // 判空
private:
Node<DataType> * top; // 栈顶指针
};
// 初始化
template <typename DataType>
LinkStack<DataType>:: LinkStack()
{
top = new Node<DataType>; // 生成栈顶指针结点
top->next = nullptr;
}
// 析构函数 链栈的销毁
template <typename DataType>
LinkStack<DataType> :: ~LinkStack( )
{
Node<DataType> *q;
while (top != NULL) //释放链栈的每一个结点的存储空间
{
q = top; //暂存被释放结点
top = top->next; // top指向被释放结点的下一个结点
delete q;
}
}
// 入栈操作,将元素x入栈
template <typename DataType>
void LinkStack<DataType>:: Push(DataType x)
{
Node<DataType> * s = nullptr;
s = new Node<DataType>;
s->data = x;
s->next = top;
top = s;
}
// 出栈操作,将栈顶元素出栈
template <typename DataType>
DataType LinkStack<DataType>:: Pop()
{
Node<DataType> * p = nullptr;
DataType x;
if (top == nullptr) throw "下溢";
x = top->data;
p = top;
top = top->next;
delete p;
return x;
}
// 取出栈顶元素,不删除
template <typename DataType>
DataType LinkStack<DataType>:: GetTop()
{
if (top == nullptr) throw "栈顶为空";
else return top->data;
}
// 判空
template <typename DataType>
void LinkStack<DataType>:: Empty()
{
if (top == nullptr) cout << "栈为空" << endl;
else cout << "栈不为空" << endl;
}
int main()
{
LinkStack<int> S{ }; // 定义栈
cout << "1 和 2 入栈";
S.Push(1);
S.Push(2);
cout << "当前栈顶元素位: " << S.GetTop() << endl;
int x;
try
{
x = S.Pop(); // 出栈
cout << "出栈操作,出来的元素是: " << x << endl;
}
catch (char *str)
{
cout << str << endl;
}
int y;
try
{
cout << "请输入待入栈元素: ";
cin >> y;
cout << "待入栈元素为: " << y << endl;
S.Push(y); // 进栈
}
catch (char *str)
{
cout << str << endl;
}
S.Empty();
return 0;
}