详解数据结构：栈

embedded/2024/9/22 20:00:43/

一、顺序栈

顺序栈的存储方式如下：

从图中可以看出，顺序栈需要两个指针，base指向栈底，top指向栈顶。

typedef struct SqStack {ElemType *base; //栈底指针ElemType *top; //栈顶指针}SqStack;

说明：

ElemType是元素类型，需要什么类型就写什么类型。

typedef将结构体等价于类型名Sqstack。

栈定义好了之后，还要先定义一个最大的分配空间，这和数组一样，需要预先分配空间，因此可以采用宏定义：

#define Maxsize 100;  //预先分配空间，这个数值根据实际需要预估确定

上面的结构体定义采用了动态分配的形式，也可以采用静态分配的形式，使用一个长数组存储数据元素，一个整型下标记录栈顶元素的位置。静态分配的顺序栈结构定义如下：

typedef struct SqStack {ElemType data[Maxsize]; //定长数组int top; //栈顶下标}SqStack;

注意：栈只能在一端操作，后进先出，是人为规定的，也就是说不允许在中间查找，取值，插入，删除等操作。顺序栈本身是顺序存储的，有人就想：我偏要从中间取一个元素，这也是可以的，但这样做，这就不是栈了。

1、顺序栈的初始化

初始化一个空栈，动态分配Maxsize大小的空间，用S.top和S.base指向该空间的基地址。

代码实现：

bool InitStack(SqStack &S) //构造一个空栈S{S.base=new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间if(!S.base)    //空间分配失败return false;S.top=S.base;  //top初始为base，空栈return true;}

2、入栈

入栈前要判断是否栈满，如果栈已满，则入栈失败；否则将元素放入栈顶，栈顶指针向上移动一个位置（top++）。

图解：

输入1，入栈（左图）

接着输入2，入栈（右图）

代码实现：

bool Push(SqStack &S,int e) // 插入元素e为新的栈顶元素{if(S.top-S.base==Maxsize) //栈满return false;*(S.top++)=e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;return true;}

3、出栈

出栈前要先判断是否为空栈，如果栈是空的，则出栈失败；否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个位置（top--）。

完美图解：

栈顶元素所在的位置是S.top-1，因此把该元素取出来，暂存在变量e中，然后S.top指针向下移动一个位置。因此可以先移动一个位置，即--S.top，然后再取出元素。

例：栈顶元素4出栈前后的状态

注意：因为顺序栈删除一个元素时，并没有销毁该空间，所以4其实还在那个位置，只不过下一次再有元素进栈时，就把他覆盖了。相当于该元素已出栈，因为栈的内容时S.base到S.top-1。

代码实现：

bool Pop(SqStack &S,int &e) //删除S的栈顶元素，暂存在变量e中{if(S.base==S.top) //栈空return false;e=*(--S.top); //栈顶指针减1，将栈顶元素赋给ereturn true;}

4、取栈顶元素

取栈顶元素和出栈不同。取栈顶元素只是把栈顶元素复制一份，栈顶指针未移动，栈内元素个数未变。而出栈时栈顶指针向下移动一个位置，栈内不在包含这个元素。

完美图解：

取栈顶元素*(S.top-1)即元素4，取值后S.top指针没有改变，栈内元素的个数也没有改变。

代码实现：

int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变{if(S.top!=S.base)  //栈非空return *(S.top-1); //返回栈顶元素的值，栈顶指针不变elsereturn -1;}

二、链栈

栈可以顺序存储，也可以用链式存储。

顺序栈是分配一段连续的空间，需要两个指针：base指向栈底，top指向栈顶，而链栈每个节点的地址都不连续，只需要一个栈顶指针即可。

链栈的每个节点都包含两个域：数据域和指针域。可以把链栈看作一个不带头结点的单链表，但只能在头部进行插入、删除、取值等操作，不可以在中间和尾部操作。

链栈的结构体定义如下：

typedef struct Snode{ElemType data; //数据域struct Snode *next; //指针域，指向下一个节点的指针}Snode,*LinkStack;

链栈的节点定义和单链表一样，只不过它只能在栈顶那一端操作而已。

1、链栈的初始化

初始化一个空的链栈是不需要头结点的，因此只需要让栈顶指针为空即可。

代码实现：

typedef struct Snode{ElemType data; //数据域struct Snode *next; //指针域，指向下一个节点的指针}Snode,*LinkStack;

2.入栈

入栈是将新元素节点压入栈顶。因为链栈中第一个节点为栈顶，因此将新元素节点插入到第一个节点的前面，然后修改栈顶指针指向新结点即可。有点像堆柴，将新的节点堆在栈顶之上，新的节点成为新的栈顶。

完美图解：

（1）生成新结点。入栈前要创建一个新结点，将元素e存入该结点的数据域。

代码实现：

p=new Snode; //生成新结点，用p指针指向该结点p->data=e; //将e放在新结点数据域

（2）将新元素节点插入到第一个节点的前面，然后修改栈顶指针指向新结点。

赋值解释：

  • p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域。
  • S=p;    //修改栈顶指针为p

整体代码实现：

bool Push(LinkStack &S,int e) //在栈顶插入元素e{LinkStack p;p=new Snode; //生成新结点p->data=e; //将e放在新结点数据域p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域S=p;    //修改栈顶指针为preturn true;}

3.出栈

出栈就是把栈顶元素删除，绕过指针指向下一个节点，然后释放该结点空间。

赋值解释：

  • p=S;  //用p保存栈顶元素地址，以备释放
  • S=S->next;  //修改栈顶指针，指向下一个结点
  • delete p;  //释放原栈顶元素的空间

代码实现：

bool Pop(LinkStack &S,int &e) //删除S的栈顶元素，用e保存其值{LinkStack p;if(S==NULL) //栈空return false;e=S->data;  //将栈顶元素赋给ep=S;  //用p保存栈顶元素地址，以备释放S=S->next;  //修改栈顶指针，指向下一个结点delete p;  //释放原栈顶元素的空间return true;}

4.取栈顶元素

取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素赋值一份，栈顶指针并没有改变。而出栈是指删除栈顶元素，栈顶指针指向了下一个元素。

代码实现：

int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针{if(S!=NULL) //栈非空return S->data; //返回栈顶元素的值，栈顶指针不变elsereturn -1;}

顺序栈和链栈的所以基本操作都只需要常数事件，所以在事件效率上难分伯仲。在空间效率方面，顺序栈需要预先分配固定长度的空间，有可能造成空间浪费或溢出；链栈每次只分配一个节点，除非没有内存，否则不会出现溢出，但是每个节点需要一个指针域，结构性开销增加。因此，如果元素个数变化较大，可以采用栈链；反之，可以采用顺序栈。在实际中，顺序栈比链栈应用更广泛。

配套完整代码（顺序栈）：

#include<iostream>
using namespace std;#define Maxsize 100  //预先分配空间，这个数值根据实际需要预估确定；typedef struct SqStack {int *base; //栈底指针int *top; //栈顶指针
}SqStack;bool InitStack(SqStack &S) //构造一个空栈S
{S.base=new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间if(!S.base)    //空间分配失败return false;S.top=S.base;  //top初始为base，空栈return true;
}bool Push(SqStack &S,int e) // 插入元素e为新的栈顶元素
{if(S.top-S.base==Maxsize) //栈满return false;*(S.top++)=e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;return true;
}bool Pop(SqStack &S,int &e) //删除S的栈顶元素，暂存在变量e中
{if(S.base==S.top) //栈空return false;e=*(--S.top); //栈顶指针减1，将栈顶元素赋给ereturn true;
}int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
{if(S.top!=S.base)  //栈非空return *(S.top-1); //返回栈顶元素的值，栈顶指针不变elsereturn -1;
}int main()
{int n,x;SqStack S;InitStack(S);//初始化一个顺序栈Scout<<"请输入元素个数n："<<endl;cin>>n;cout<<"请依次输入n个元素，依次入栈："<<endl;while(n--){cin>>x; //输入元素Push(S,x);}cout<<"元素依次出栈："<<endl;while(S.top!=S.base)//如果栈不空，则依次出栈{cout<<GetTop(S)<<"\t";//输出栈顶元素Pop(S,x);   //栈顶元素出栈}return 0;
}

配套完整源代码（链栈）：

#include<iostream>
using namespace std;typedef struct Snode{int data; //数据域struct Snode *next; //指针域
}Snode,*LinkStack;bool InitStack(LinkStack &S)//构造一个空栈S
{S=NULL;return true;
}bool Push(LinkStack &S,int e) //在栈顶插入元素e
{LinkStack p;p=new Snode; //生成新结点p->data=e; //将e放在新结点数据域p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域S=p;    //修改栈顶指针为preturn true;
}bool Pop(LinkStack &S,int &e) //删除S的栈顶元素，用e保存其值
{LinkStack p;if(S==NULL) //栈空return false;e=S->data;  //将栈顶元素赋给ep=S;  //用p保存栈顶元素地址，以备释放S=S->next;  //修改栈顶指针，指向下一个结点delete p;  //释放原栈顶元素的空间return true;
}int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针
{if(S!=NULL) //栈非空return S->data; //返回栈顶元素的值，栈顶指针不变elsereturn -1;
}int main()
{int n,x;LinkStack S;InitStack(S);//初始化一个顺序栈Scout<<"请输入元素个数n："<<endl;cin>>n;cout<<"请依次输入n个元素，依次入栈："<<endl;while(n--){cin>>x; //输入元素Push(S,x);}cout<<"元素依次出栈："<<endl;while(S!=NULL)//如果栈不空，则依次出栈{cout<<GetTop(S)<<"\t";//输出栈顶元素Pop(S,x);   //栈顶元素出栈}return 0;
}


http://www.ppmy.cn/embedded/13206.html

相关文章

数仓建模—物理数据模型

数仓建模—物理数据模型

数仓建模—物理数据模型 前面我们讲了数据模型和逻辑数据模型，你可以参考前面的文章，这一节我们介绍一下物理数据模型 数仓建模—数据模型 数仓建模—逻辑数据模型 什么是物理数据模型 物理数据模型指定如何在数据库中构建数据模型。它概述了所有表结构，包括列名、数据类…
阅读更多...
Qt 运行 Android 程序时找不到 Toou2D 库闪退

Qt 运行 Android 程序时找不到 Toou2D 库闪退

问题描述 程序闪退&#xff0c;错误信息如下&#xff0c;找不到库。 W libAndroid10_armeabi-v7a.so: QQmlApplicationEngine failed to load component W libAndroid10_armeabi-v7a.so: qrc:/main.qml:3:1: plugin cannot be loaded for module "Toou2D": Cannot …
阅读更多...
【一些神金】怎么缓解工作压力？使用VS-code彩虹屁插件

【一些神金】怎么缓解工作压力？使用VS-code彩虹屁插件

怎么缓解工作压力&#xff1f; 其实吃点好的&#xff0c;多睡一会儿&#xff0c;再锻炼锻炼身体就好。 但我只是想炫耀一下这个彩虹屁插件。 原版插件&#xff1a;VS-code-Rainbowfart 我的版本&#xff1a;RainbowFart-Oberon 基于 MIT 开源&#xff0c;包括所有设计资源及音…
阅读更多...
Day10 React———— 第十天

Day10 React———— 第十天

useReducer useReducer 是 React Hooks 中的一个函数&#xff0c;用于管理组件的状态。它类似于 useState&#xff0c;但提供了更复杂的状态逻辑处理能力。 接受一个 reducer 函数和初始状态作为参数&#xff0c;并返回当前状态和 dispatch 函数。 使用 useReducer 的基本流程…
阅读更多...
【AI写作】未来科技趋势：揭秘DreamFusion的革新力量

【AI写作】未来科技趋势：揭秘DreamFusion的革新力量

首先&#xff0c;这篇文章是基于笔尖AI写作进行文章创作的&#xff0c;喜欢的宝子&#xff0c;也可以去体验下&#xff0c;解放双手&#xff0c;上班直接摸鱼~ 按照惯例&#xff0c;先介绍下这款笔尖AI写作&#xff0c;宝子也可以直接下滑跳过看正文~ 笔尖Ai写作&#xff1a;…
阅读更多...
Redis 数据类型

Redis 数据类型

文章目录 Reidis 命名规范String类型Hash 类型List 类型Set 类型Zset 类型补充 概览&#xff1a; 数据结构 &#xff1a; key value 中value的类型 内部编码&#xff1a; 实际在底层用来存储value的结构 设计优点&#xff1a; ① 解耦&#xff0c;用户可根据需求再开发内部编…
阅读更多...
Pinia 深度剖析：Vue.js 应用状态管理的全面指南

Pinia 深度剖析：Vue.js 应用状态管理的全面指南

一、pinia简介 Pinia 是一个专门为 Vue.js 应用程序设计的状态管理库。它的设计理念是简化状态管理过程&#xff0c;提供一种清晰、可维护的方式来管理应用程序中的数据。 二、安装与创建 1.你可以通过 npm 或者 yarn 来安装 Pinia&#xff1a; npm install pinia # 或者 y…
阅读更多...
MySQL—一条查询SQL语句的完整执行流程

MySQL—一条查询SQL语句的完整执行流程

MySQL—一条查询SQL语句的完整执行流程 表结构和数据如下&#xff1a; 我们分析的sql语句如下&#xff1a; select tb_id,tb_name,tb_address from tb_user where tb_id 66;大体来说&#xff0c;MySQL可以分为Server层和存储引擎层两部分: Server层 包括:连接器、查询缓存、…
阅读更多...
最新文章

Copyright @ 2022~2023