学一样东西首先要要明白学它有什么用。那么问题来了:栈使用来干么的?
先说点无聊但是很必要的东西:
简单来说:栈是一种数据结构,在计算机术语中是十分重要的。因为栈在 计算机中的应用很多。其中最重要的是应用于函数的调用,也经常用作临时性数据的存储等等。栈又名堆栈,实质上是一种线性表。只不过栈作为一种线性表是很特殊的存在。因为它的运算受到了限制:只能在表头进行插入或者删除的操作。
如果你是初学者只需要记住:
实质:运算受限的线性表(线性表,你懂的),只能在表头执行插入或者删除等操作。
特点:后进先出(因为每次进入的数据都在栈顶,所以出去的时候肯定是先出去)。
就够了。
既然说栈是一种线性表,那么它的简单实现就有两种:顺序存储(即数组);链式存储(即链表)
由于链表相对于数组来说难那么一丢丢,所以以下讲解使用链表来完成,当然我也会贴出顺序存储的实现。
故事:
从前有个人小领。
没错就是小领,他本来是一位未来的IT大神,但是由于他经常学C++,所以眼睛瞎掉了。为了能娶到如花,他到 一家饭店去洗盘子挣钱。现在在他的面前有一对摞在一起的盘子,老板告诉他这堆盘子有100个。洗完之后可以得到1毛钱。
把盘子看做一个数据 节点:
(要注意的是链栈是采用头插法建的)
typedef struct LinkNode
{
int data;
struct LinkNode *next;
}LiStack;
初始化栈:建立一个空栈:
void InitStack(LiStack *&s)
{
s = (LiStack *)malloc(sizeof(LiStack)); //为数据节点申请空间
s->next = NULL;
}
即出栈:
bool Pop(LiStack *&s)
{
LiStack *p;
if (s->next == NULL) //如果洗完了,就没得洗了。
return false;
p = s->next; // 如果没洗完 ,我们让下一个盘子位于栈顶(相当于把这个盘子隔过去)
s->next = p->next;
free(p); //释放被取的盘子所占的空间
return true;
}
进栈:
void Push(LiStack *s, int e)
{
LiStack *p;
p = (LiStack*)malloc(sizeof(LiStack)); //申请一个空间
p->data = e;
p->next = s->next; //让新加入的盘子位于顶部
s->next = p;
}
判断栈是否为空:
bool IsEmpty(LiStack *s)
{
return (s->next== NULL);
}
销毁栈:
void Destory(LiStack *&s)
{
LiStack *p = s, *q = s->next;
while (q != NULL)
{
free(p);
p = q;
q = p->next;
}
free(p); //最后一个数据节点为p,所以我们需要销毁p
}
最终,小领通过卖Upan成功 娶到了如花。
(是不是觉得栈的操作好少,是 的,栈的操作很少,以至于好好学的人很少)
以下贴出来顺序储存的代码实现:
#define MAX 1001
typedef struct Stack
{
int data[MAX]; //栈存储的数据
int top;
}SqStack;
void InitStack(SqStack *&s) //初始化栈
{
s = (SqStack *)malloc(sizeof(SqStack));// 申请空间,并让top为-1,(意思是空栈,栈存储是从0 开始)
s->top = -1;
}
bool Push(SqStack *&s, int e) //进栈
{
if (s->top == MAX - 1) //如果栈已经满了,则不进栈
return false;
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(SqStack *&s)
{
if (s->top == -1) //如果当前栈里面没有数据,就不出栈
return false;
s->top--; //有数据就出栈,top--
return true;
}
bool StackEmpty(SqStack *s) //是否为空(通过top的值判断)
{
return (s->top == -1);
}
bool GetTop(SqStack *s, int &e) //取栈顶元素
{
if (s->top == -1) //如果栈为空,则不取
return false;
e = s->data[s->top];
return true;
}
void Destory(SqStack *&s) //销毁栈。
{
free(s); //释放空间
}
1.括号的匹配(链栈实现)
括号 的匹配很容易理解,意思就是给定一个字符串里面包含了许多的括号,我们要做的就是判断括号的使用是否合法。例如:[][[]]]]、())()[][]是不合法的,而[][][]等是合法的。理解题意就ok了,那么你可能会问,对于不是括号的字符怎么处理,答案:不做处理,只看括号。
(一定要注意判断括号的匹配采用的是头插法建表)
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct Stack //数据节点
{
char data; //数据信息
struct Stack *next;
}LiStack;
bool Push(LiStack *&s, char e) //入栈
{
LiStack *p;
p = (LiStack *)malloc(sizeof(LiStack)); //注意数据是放在顶端(即头插的头部)
p->data = e;
p->next = s->next;
s->next = p;
return true;
}
bool Pop(LiStack *&s) //出栈
{
LiStack *p;
if (s->next != NULL) //如果栈不为空,就出栈
{
p = s->next;
s->next = p->next;
free(p);
return true;
}
return false;
}
bool IsEmpty(LiStack* &s) //栈是否为空
{
return s->next == NULL;
}
bool GetTop(LiStack *s, char e, int num) //判断括号是否匹配,要注意的是"(" 与 “)” 在ASCII表中相差1,而“[” 与“]”相差的是2.
{
if (s->next == NULL)
{
return false;
}
else
{
if (e == s->next->data + num) //如果匹配返回真。
return true;
else
return false;
}
}
int main()
{
LiStack *L;
L = (LiStack *)malloc(sizeof(LiStack));
L->next = NULL;
char str[100];
scanf("%s", str);
int i;
int len = strlen(str);
for (i = 0; i < len; i++)
{
if ((str[i] == '(') || (str[i] == '[')) //如果是括号的左部分,则将其入栈。
{
Push(L, str[i]);
continue;
}
else if (str[i] == ']') //如果是“]”
{
if (IsEmpty(L) == true) //则判断当前栈是否为空,如果为空,则这个字符串中的括号使用是不合法的。
{
printf("NO");
return 0;
}
else
{
if (GetTop(L, str[i], 2) == true) //如果栈不为空,则判断“]”与栈顶元素是否匹配,如果匹配,则出栈。
{
Pop(L);
}
}
}
else if (str[i] == ')') //如果是“)”
{
if (IsEmpty(L) == true) //则判断当前栈是否为空,如果为空,则这个字符串中的括号使用是不合法的。
{
printf("NO");
return 0;
}
else
{
if (GetTop(L, str[i], 1) == true) //如果栈不为空,则判断“)”与栈顶元素是否匹配,如果匹配,则出栈。
{
Pop(L);
}
}
}
}
if (IsEmpty(L) == true) //最后只需要判断 栈是否为空就可以了,对于那些不是括号的字符,我们根本就没入栈,所以嘿嘿嘿。
{
printf("YES");
}
else
{
printf("NO");
}
return 0;
}
括号的匹配不难,按照思路一点一点写出来就ok了。但是 要注意括号在ASCII码表中的位置关系。
2.中缀表达式转换成后缀表达式
数据结构书上讲的太过繁琐,又是什么左运算符,又运算符什么的,无聊。
我们在此用两个栈,s1,s2。s1为运算符的临时存储栈,s2为最终结果 的存储栈。
简单来说分以下情况:
从左 到右依次取数据 。
1.如果是数据,直接入s1栈顶。
2.如果是(,直接入s1栈顶。
3.如果是 ),则将距离s1栈顶 最近的“ )”之间的元素,逐个出栈,并入栈s2.
4.如果是 运算符,则将该运算符与s1栈顶的元素比较,如果该元素 的优先级大,则直接入s1栈顶,否则将s1栈顶元素出栈,并把 出栈的元素入栈s2,直到s1栈顶元素的优先级高于该元素。
重复操作,直到数据取完,是不是很简单,
那么模拟一下:
中缀表达式“9+(3-1)*3+10/2”转化为后缀表达式“9 3 1-3*+ 10 2/+”
1. 初始化一空栈,用来对符号进出栈使用。
2. 第一个字符是数字9,输出9,后面是符号“+”,进栈。
3. 第三个字符是“(”,依然是符号,因其只是左括号,还未配对,故进栈。
4. 第四个字符是数字3,输出,总表达式为9 3,接着是“-”进栈。
5. 接下来是数字1,输出,总表达式为9 3 1,后面是符号“)”,此时,我们需要去匹配此前的“(”,所以栈顶依次出栈,并输出,直到“(”出栈为止。此时左括号上方只有“-”,因此输出“-”,总的输出表达式为9 3 1 -
6. 接着是数字3,输出,总的表达式为9 3 1 - 3 。紧接着是符号“*”,因为此时的栈顶符号为“+”号,优先级低于“*”,因此不输出,进栈。
7. 之后是符号“+”,此时当前栈顶元素比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”号更低的优先级,所以全部出栈),总输出表达式为 9 3 1 - 3 * +.然后将当前这个符号“+”进栈。也就是说,前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”,而下图中的栈底(也是栈顶)的“+”是指“9+(3-1)*3+”中的最后一个“+”。
8. 紧接着数字10,输出,总表达式变为9 3 1-3 * + 10。
9. 最后一个数字2,输出,总的表达式为 9 3 1-3*+ 10 2
10. 因已经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1-3*+ 10 2/+
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define MAX 1001
typedef struct Stack
{
char data[MAX];
int top;
}SqStack;
int cmp(char ch) //判断优先级( * / 的优先级最高,次之 是+ -,最后是 ( ))
{
switch (ch)
{
case'+':
case'-':
return 1;
case'*':
case'/':
return 2;
default:
return 0;
}
}
void InitStack(SqStack *&s) //初始化栈
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1;
}
bool Push(SqStack *&s, char e) //数据入栈
{
if (s->top == MAX)
return false;
else
s->data[++s->top] = e;
return true;
}
bool Pop(SqStack *&s) //数据出栈
{
if (s->top == -1)
return false;
else
s->top--;
return true;
}
bool IsEmpty(SqStack *s) //判断栈是否为空
{
return s->top == -1;
}
int main()
{
SqStack *s1, *s2;
InitStack(s1), InitStack(s2);
char str[1001], int i;
scanf("%s", str);
int len = strlen(str);
for (i = 0; i < len; i++)
{
if (str[i] == '(') //如果当前数据是“(”,直接入栈
Push(s1, str[i]);
else if (str[i] == ')') //如果是“)”,则在s1中找到最近的“(”元素,将两者之间的数据出栈,并入栈到s2.
{
while (s1->data[s1->top] != '(')
{
Push(s2, s1->data[s1->top]);
Pop(s1);
}
Pop(s1);
}
else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') //如果是运算符
{
while (cmp(s1->data[s1->top]) >= cmp(str[i])) //判断优先级,该运算符优先级较s1栈顶元素的优先级低的话
{
Push(s2, s1->data[s1->top]); //将s1栈顶元素出栈并入栈到s2,直到该元素的运算符优先级较高。
Pop(s1);
}
Push(s1, str[i]); //然后将这个 元素入栈s1.
}
else
Push(s2, str[i]); //如果是操作数据直接入站s2.
}
while (IsEmpty(s1) == false)// 将s1最终还存储其中 的数据转移到s2
{
Push(s2, s1->data[s1->top]);
Pop(s1);
}
for (i = 0; i <= s2->top; i++) //完成。
printf("%c", s2->data[i]);
return 0;
}
是不是很简单,有效代码很少,精髓在于运算符优先级判断的cmp函数。
可以通过Swust Oj 1042;(题数据弱。。。)
3.后缀表达式求值
后缀表达式的求值:
将中缀表达式转换成等价的后缀表达式后,求值时,只需从左到右扫描一遍后缀表达式即可,而不需要考虑到运算符优先级问题。具体求值步骤为:从左到右扫描后缀表 达式,遇到运算符就把表达式中该运算符前面两个操作数取出并运算,然后把结果带回后缀表达式;继续扫描直到后缀表达式最后一个表达式。 后缀表达式的求值的算法:
设置一个栈,开始时,栈为空,然后从左到右扫描后缀表达式,若遇操作数,则进栈;若遇运算符,则从栈中退出两个元素,先退出的放到运算符的右边,后退出的 放到运算符左边,运算后的结果再进栈,直到后缀表达式扫描完毕。此时,栈中仅有一个元素,即为运算的结果。
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct Stack
{
struct Stack *next;
int data;
}LiStack;
bool Push(LiStack *&s, int e) //元素进栈
{
LiStack *p;
p = (LiStack *)malloc(sizeof(LiStack));
p->data = e;
p->next = s->next;
s->next = p;
return true;
}
bool Pop(LiStack *&s) ///元素出栈
{
if (s->next == NULL)
{
return false;
}
s->next = s->next->next;
return true;
}
int main()
{
int i = 0;
char str[1001];
while (1) //要注意输入的时候数据之间是有空格的
{
scanf("%c", &str[i]);
if (str[i] == '\n')
break;
else
{
i++;
}
}
LiStack *L;
L = (LiStack *)malloc(sizeof(LiStack));
L->next = NULL;
int len = strlen(str);
for (i = 0; i < len; i++)
{
if (str[i] >= '0' && str[i] <= '9') //如果是操作数,直接进栈
{
int data = str[i] - 48;
Push(L, data);
}
else if (str[i] == '+') //如果是加号,然后栈顶和栈顶的下个元素求和,对这两个数据出栈,将结果入栈
{
int data = L->next->next->data + L->next->data;
Pop(L);
Pop(L);
Push(L, data);
}
else if (str[i] == '-')
{
int data = L->next->next->data - L->next->data;//如果是减号,栈顶下个元素 - 栈顶元素,这两个数据出栈,计算结果入栈
Pop(L);
Pop(L);
Push(L, data);
}
else if (str[i] == '*') //如果是乘号,栈顶下个元素 * 栈顶元素,这两个数据出栈,结果入栈
{
int data = L->next->next->data * L->next->data;
Pop(L);
Pop(L);
Push(L, data);
}
else if (str[i] == '/') //如果是除号,栈顶下个元素 / 栈顶元素,这两个数据出栈,结果入栈
{
int data = L->next->next->data / L->next->data;
Pop(L);
Pop(L);
Push(L, data);
}
}
printf("%d", L->next->data); //最终栈中只剩余一个值就是最后的计算结果
return 0;
}
代码可通过Swust oj 1043
如果是刚接触数据结构,能将括号的匹配,中缀变后缀,后缀表达式的求值理解并能使用就已经差不多了。
如果对栈有兴趣的同学可以去学习一下关于栈是在函数调用中的运用等等。
ok,如有错,请留言。
文章浏览阅读1.1k次。docker启动redis命令_linux docker 重启 redis
文章浏览阅读325次。插头DP小结_dp插头模型
文章浏览阅读3.5k次。关于测试工作效率低的一些思考和改进方法引子 汇总统计了一下项目组近期测试项目实际工作量与基线工作量的对比,发现一个严重问题。就是工作效率特别低下。下面简单列举一下几个项目预期工作量和实际工作量以及时间耗费严重的地方、项目简要背景。 1、B版本测试。版本预期工作量15人天,实际耗费工作量在30人天。更为严重的是测试人员并没有因为测试周期延长和工作量投入加大而测试的更轻松,反而是测试期..._测试人员不足与改进
文章浏览阅读173次。级联样式表 CSS-难以成熟 (CSS — Difficult to maturation)Unlike software, the CSS specifications are developed by successive versions, which would allow a browser to refer to a particular version. CSS was devel..._级联样式表是哪年产生的
文章浏览阅读1.7k次。目录批处理语句1、批处理语句简介示例一:示例二:存储过程一、什么是存储过程1、存储过程的简介2、存储过程包含的内容3、存储过程的优点4、存储过程的分类系统存储过程:用户定义存储过程5、常用的系统储存过程(1)一般常用的存储过程(2)xp_cmdshell二、创建存储过程1、定义存储过程的语法2、不带参数的存储过程3、带参数..._sql的批处理
上次,我们解除了css的内外边距、鼠标悬停及其练习。现在我们学习css元素练习和定位。
文章浏览阅读7.6k次。在Android中我们可以用visibility来控制控件的显示和隐藏,那在Flutter中我们怎么控制呢?其实,在Flutter中控制Widget显示和隐藏有3中方法:不过3种方法的核心思想都是根据变量的值去判断的,所以先定义一个变量:bool visible = true;变量的值可以在事件中去控制,比如: onPressed: () { setS..._flutter判断控制是否被遮住
文章浏览阅读673次。有没有师兄师姐有meganv2.04以上的版本小弟只有低版本的 需要高版本运行一下有偿!_megan v2.04
文章浏览阅读32次。springboot基于springboot的小型超市库存管理系统。springboot基于SpringBoot的校园失物招领系统。springboot基于springboot的残障人士社交平台。springboot基于springboot的酒店管理系统。springboot基于springboot的电商购物系统。springboot基于微信小程序的Sunmoon口红商城。springboot基于云平台的便民物流速递信息管理系统。springboot基于微服务的固定资产管理系统。
文章浏览阅读3.1k次。还在用PPT、Word和Excel画企业组织结构图吗?对于人力资源的同事来说,画组织结构图是一键非常头疼的事情,尤其是对于一些大公司和人员变动较大的公司来说,需要经常更换组织结构图,每次变动都要耗费大量的时间和精力去重新绘图。其实绘制织结构图很简单,之所以难是因为没有找对工具和方法!今天小编就教你如何用亿图图示轻松绘制一个既美观又专业的组织结构图!下图是一个简单的组织结构图例子,小编就以此为例,详细讲解一下好看清晰、实用的公司组织结构图是怎么画出来的。1、新建组织结构图2、创建组织结构_书本里印刷的结构图是用什么软件做的
文章浏览阅读1.8k次,点赞4次,收藏5次。BLE5.0 扩展蓝牙名称长度_蓝牙广播名称过长
文章浏览阅读3.5k次。centos8安装NVIDIA显卡驱动,docker模式运行机器学习_centos8安装显卡驱动