【数据结构】三、栈和队列：3.链栈（链栈栈的初始化，判空，进栈，出栈，读取栈顶，链栈实例）

🕗 发布于 2024-04-27 16:55 数据结构 c++ c语言 链表算法

文章目录

- 3.链栈

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

原文地址：https://blog.csdn.net/weixin_51350847/article/details/138126713

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：JAVA 中间件之 Mycat2
下一篇：debian 12 配置VNC

Linux环境下配置git
Linux配置git教程
阅读更多2024-10-13
递推，CF 1957C - How Does the Rook Move?
如果选其他的(1, x) / (x, 1) x > 1，那么会扣掉一行一列，问题等价于 (n - 2) * (n - 2)的网格的方案数。f(i) = f(i - 1) + (2i - 2) *
阅读更多2024-10-13
复杂网络分析基本概念
复杂网络分析
阅读更多2024-10-13
人工智能长期记忆的新突破：HippoRAG的创新框架
人工智能咨询培训老师叶梓转载标明出处大模型（LLMs）在预训练后，如何有效地整合大量新经验，同时避免灾难性遗忘，一直是人工智能领域的难题。尽管已有的检索增强生成（RAG）方法为LLMs提供了长期记忆
阅读更多2024-10-13
SAP SD学习笔记09 - 受注传票中的不完全Log 和 Business Partner(取引先机能）
本章讲了出荷传票中的内容，不完全Log 和 Business Partner（取引先机能）。不完全Log是用来Check出荷传票的内容是否完全，作为能否出力后续机能的依据；Business Partn
阅读更多2024-10-13
PTC发布PTC Modeler 10.1，进一步支持SysML v2
*进一步支持SysML v2。基于之前的版本做了改进，增加了动作建模，允许建模者使用动作、流和控制模式等元素建模系统的功能行为，还在结构建模中增加了更多功能，包括流、绑定连接和共轭端口。
阅读更多2024-10-13
github下载文件的两种方式（非git形式）
2.如果下载的是单独的某一个文件，则可以按照下图的格式点击下图所示的那个下载的图标即可。1.以下面的图为例，可以直接点击右上方的绿色。按键，在弹出的列表中选择。
阅读更多2024-10-13
朴素贝叶斯分类（鸢尾花数据集）
fit 函数获取 y 中所有不同的类别，并将这些类别存储在 self.classes 中，这里的classes就是通过 X[y == c] 选择属于类别 c 的所有样本，存储在 X_c 中均值和方差是
阅读更多2024-10-13
MySQL中的数据类型
在Mysql中有许多衍生的int类型，比如Tinyint就是其中一个，他的最小值是-128 最大值是127那么为什么Mysql中要对这些数据做如此详细的处理？是为了让程序员对数据的合法插入，数据类型本
阅读更多2024-10-13
【黑苹果】记录MacOS升级Sonoma的过程
【黑苹果】记录MacOS升级Sonoma的过程一、硬件二、提前说明三、准备OC四、选择驱动五、选择ACPI六、下载内核扩展七、其他问题
阅读更多2024-10-13