3.链栈
链栈是运算受限的单链表，只能在链表头部进行操作的单链表。
- 链表的头指针就是栈顶，链头为栈顶，链尾为栈底。
- 栈的链式存储不需要附设头节点。
- 基本不存在栈满的情况，不需要判断栈满，但要判空。
- 空栈相当于头指针指向空。
- 插入（入栈）和删除（出栈）仅在栈顶处执行。
- 因为是动态分配空间，所以需要释放。
#define MaxSize 100 //链栈的最大长度
typedef int SElemType; //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode
{
SElemType data; //结点数据域
struct StackNode* next; //结点指针域
}StackNode, *LinkStack; //struct StackNode的结点形式、链栈形式别名
LinkStack stack; //创建栈顶指针指向链栈的头结点
- *StackNode，LinkStack的区别：
LinkStack temp1 = new StackNode;
这里 LinkStack 是一个指针类型别名，实际上是 StackNode* 的别名。
所以 temp1 是一个指针变量，指向 StackNode 类型的结点。
StackNode* temp2 = new StackNode;
这里直接声明了一个 StackNode* 类型的指针变量 temp2，指向 StackNode 类型的结点。
这两种声明方式是等价的。两者都创建了一个动态分配的 StackNode 类型的结点，并将它的地址赋给相应的指针变量。两者都可以通过 temp1->data 或 temp2->data 来访问结点的数据成员，以及 temp1->next 或 temp2->next 来访问结点的下一个结点的指针成员。
因此，在功能上，temp1 和 temp2 没有区别。不同的只是它们的声明方式，temp1 是通过别名 LinkStack 来声明的指针变量，而 temp2 是直接以 StackNode* 类型来声明的指针变量。
3.1初始化
//链栈的初始化
bool InitStack(LinkStack& stack){
//构造一个空栈、栈顶指针置为空
stack = NULL;
return true;
}
3.2判空
//判断链栈是否为空
bool StackEmpty(LinkStack& stack){
if (stack == NULL){
return true;
}
return false;
}
3.3获取栈长度
/**
* @brief 获取栈顶长度。
* 因为链表的最后一个节点的next指针是nullptr（或者说是NULL），代表链表的终止，
* 所以可以将链表的遍历条件设置为当前节点指针不等于nullptr，这样在遍历过程中，
* 当指针指向最后一个节点时，其next指针就会指向nullptr，循环条件就不再成立，
* 遍历结束，可以避免继续遍历下一个不合法的节点。
* @param stack
* @return int
*/
int StackLength(LinkStack& stack){
int length = 0;
StackNode* temp = stack;//创建临时指针temp与stack指向同一位置
while (temp != nullptr){
length++; //链栈长度即为栈中元素个数，循环一次，长度++
temp = temp->next; //temp指针下移一位
}
return length; //返回链栈长度
}
3.4入栈
链栈的入栈相当于单链表的前插法。
//入栈（前插法）
bool PushStack(LinkStack& stack, SElemType value){ //不用判栈满
StackNode* temp = new StackNode; //生成新结点temp
temp->data = value; //将新节点数据域置为value
temp->next = stack; //将新结点插入栈顶
stack = temp; //更新栈顶指针
return true;
}
3.5出栈
//出栈：首先判空
bool PopStack(LinkStack& stack, SElemType &value){
if (StackEmpty(stack)){
return false;
}
value = stack->data; //将栈顶数据域元素赋值给value
StackNode* temp = stack; //创建一个temp指针，并将其指向 stack 指针所指向的内存地址，以便找到出栈位置并释放。
stack = stack->next; //令栈顶指针指向下一位结点，即更新栈顶指针
delete temp; //释放temp所指向的空间，即出栈元素所占的内存空间，temp本身会在函数结束后自动销毁。
return true;
}
3.6销毁链栈
//销毁链栈，释放内存
void DestroyStack(LinkStack& stack){
StackNode* temp = new StackNode; //创建一个指针
while (stack != nullptr){
temp = stack; //使该临时指针与stack指向同一位置
stack = temp->next; //更新栈顶指针
delete temp; //释放临时指针
}
stack = nullptr;
}
3.7读取栈顶
//读取栈顶：取栈顶元素
bool GetTop(LinkStack& stack, SElemType &value){
if (!StackEmpty(stack)){ //若栈不为空
value = stack->data; //返回栈顶元素
return true;
}
cout<<"栈为空"<<endl;
return false;
}
3.8遍历输出
//遍历输出栈元素
bool StackPrint(LinkStack& stack){
if (stack != nullptr){
StackNode* temp = stack; //创建一个指针与stack指向同一位置
cout<<"出栈顺序：";
while (temp != nullptr){
cout << temp->data <<" ";
temp = temp->next; //temp向下移动一位
}
return true;
}
cout<<"栈为空！"<<endl;
return false;
}
❗3.9链栈c++实例
#include<iostream>
using namespace std;
#define MaxSize 100 //链栈的最大长度
typedef int SElemType; //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode
{
SElemType data; //结点数据域
struct StackNode* next; //结点指针域
}StackNode, *LinkStack; //struct StackNode的结点形式、链栈形式别名
bool InitStack(LinkStack& stack); //初始化链栈
bool StackEmpty(LinkStack& stack); //链栈判空
int StackLength(LinkStack& stack); //计算链栈长度元素个数
bool PushStack(LinkStack& stack, SElemType value); //入栈
bool PopStack(LinkStack& stack, SElemType& value); //出栈
bool GetTop(LinkStack& stack, SElemType& value); //获取栈顶元素
bool StackPrint(LinkStack& stack); //遍历元素
void DestroyStack(LinkStack& stack); //销毁链栈，释放内存
int main()
{
//创建链栈
LinkStack stack;
SElemType value=1;
InitStack(stack);
cout << "检查栈是否为空？" << (StackEmpty(stack) ? "\t是" : "\t否") << endl;
int number = 0; //插入元素个数
cout << "请输入需要插入的元素个数：";
cin >> number;
while ((number--) > 0) {
PushStack(stack, value);//插入所输入元素
value++;
}
cout << "当前栈的元素个数：" << StackLength(stack) << endl;
GetTop(stack, value);
cout << "栈顶元素：" << value << endl;
StackPrint(stack);//遍历打印栈顶元素
cout << endl;
PopStack(stack, value);
cout << "出栈一次,栈顶元素为：" << value << endl;
StackPrint(stack);
DestroyStack(stack);
cout << endl << "栈已被销毁释放" << endl;
cout << "销毁栈后遍历栈结果：" << " ";
StackPrint(stack);
system("pause");
return 0;
}
//链栈的初始化
bool InitStack(LinkStack& stack){
//构造一个空栈、栈顶指针置为空
stack = NULL;
return true;
}
//判断链栈是否为空
bool StackEmpty(LinkStack& stack){
if (stack == NULL){
return true;
}
return false;
}
/**
* @brief 获取栈顶长度。
* 因为链表的最后一个节点的next指针是nullptr（或者说是NULL），代表链表的终止，
* 所以可以将链表的遍历条件设置为当前节点指针不等于nullptr，这样在遍历过程中，
* 当指针指向最后一个节点时，其next指针就会指向nullptr，循环条件就不再成立，
* 遍历结束，可以避免继续遍历下一个不合法的节点。
* @param stack
* @return int
*/
int StackLength(LinkStack& stack){
int length = 0;
StackNode* temp = stack;//创建临时指针temp与stack指向同一位置
while (temp != nullptr){
length++; //链栈长度即为栈中元素个数，循环一次，长度++
temp = temp->next; //temp指针下移一位
}
return length; //返回链栈长度
}
//入栈（前插法）
bool PushStack(LinkStack& stack, SElemType value){ //不用判栈满
StackNode* temp = new StackNode; //生成新结点temp
temp->data = value; //将新节点数据域置为value
temp->next = stack; //将新结点插入栈顶
stack = temp; //更新栈顶指针
return true;
}
//出栈：首先判空
bool PopStack(LinkStack& stack, SElemType &value){
if (StackEmpty(stack)){
return false;
}
value = stack->data; //将栈顶数据域元素赋值给value
StackNode* temp = stack; //创建一个temp指针，并将其指向 stack 指针所指向的内存地址，以便找到出栈位置并释放。
stack = stack->next; //令栈顶指针指向下一位结点，即更新栈顶指针
delete temp; //释放temp所指向的空间，即出栈元素所占的内存空间，temp本身会在函数结束后自动销毁。
return true;
}
//取栈顶元素
bool GetTop(LinkStack& stack, SElemType &value){
if (!StackEmpty(stack)){ //若栈不为空
value = stack->data; //返回栈顶元素
return true;
}
cout<<"栈为空"<<endl;
return false;
}
//遍历输出栈元素
bool StackPrint(LinkStack& stack){
if (stack != nullptr){
StackNode* temp = stack; //创建一个指针与stack指向同一位置
cout<<"出栈顺序：";
while (temp != nullptr){
cout << temp->data <<" ";
temp = temp->next; //temp向下移动一位
}
return true;
}
cout<<"栈为空！"<<endl;
return false;
}
//销毁链栈，释放内存
void DestroyStack(LinkStack& stack){
StackNode* temp = new StackNode; //创建一个指针
while (stack != nullptr){
temp = stack; //使该临时指针与stack指向同一位置
stack = temp->next; //更新栈顶指针
delete temp; //释放临时指针
}
stack = nullptr;
}
检查栈是否为空？ 是
请输入需要插入的元素个数：5
1
2
3
4
5
当前栈的元素个数：5
栈顶元素：5
出栈顺序：5 4 3 2 1
出栈一次,栈顶元素为：5
出栈顺序：4 3 2 1
栈已被销毁释放
销毁栈后打印输出结果： 栈为空！
销毁栈后遍历栈结果： 栈为空！
Press any key to continue . . .