数据结构之堆栈
堆栈的基本概念
堆栈是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是：线性表允许在任意位置插入和删除数据元素操作，而堆栈只允许在固定一端进行插入和删除数据元素操作
根据堆栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，这样，最后进入堆栈的数据元素总是最先退出堆栈，因此，堆栈也称作后进先出的线性表，或简称后进先出表。
例子
设有数据元素序列A,B,C，是否可以利用一个堆栈，得到数据元素序列B, A, C。
分析：按照如下方法操作：A入栈，B入栈，B出栈，A出栈，C入栈，C出栈，则输出数据元素序列为B, A, C。因此，利用一个堆栈，可以把数据元素序列A, B, C变换为数据元素序列B, A,C。其操作过程的堆栈内容示意图下图所示。
输出序列为B, A, C的操作过程
在软件设计中，需要利用堆栈进行数据元素序列转换的例子很多。例如，在编译软件系统中，就需要频繁地把中缀表达式形式的算术表达式，转换成后缀表达式形式的算术表达式。又如，任何支持递归算法的程序设计语言，都是借助堆栈来实现递归算法需要的后调用的过程先执行的要求的。
堆栈操作集合
- 初始化StackInitiate(S)：初始化堆栈S。
- 非空否StackNotEmpty(S)：堆栈S非空否。若堆栈非空，则函数返回1；否则函数返回0。
- 入栈StackPush(S, x)：在堆栈S的当前栈顶插入数据元素x。
- 出栈StackPop(S, d)：把堆栈S的当前栈顶数据元素删除并由参数d带回。若出栈成功，则返回1；失败，则返回0。
- 取栈顶数据元素StackTop(S, d)：取堆栈S的当前栈顶数据元素并由参数d带回。若取到数据元素，则返回1；否则返回0。
顺序堆栈的存储结构
顺序存储结构的堆栈称作顺序堆栈。
顺序堆栈和顺序表的数据成员是相同的，不同之处是，顺序堆栈的入栈和出栈操作只能对当前栈顶元素进行。
顺序堆栈的存储结构示意图如图3-3所示。其中，a0, a1, a2, a3, a4表示顺序堆栈要存储的数据元素序列，stack表示顺序堆栈存放数据元素的数组，MaxStackSize表示顺序堆栈数组stack的最大存储单元个数，top表示顺序堆栈数组stack的当前栈顶位置。
顺序堆栈的存储结构示意图
定义结构体SeqStack如下：
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize]; //连续内存空间存放栈中元素
int top; //存放栈顶元素在data数组中的下标
}SqStack;
顺序堆栈的操作实现
- 初始化StaticInitiate(*S)
void StaticInitiate(*S)
{
S->top=0; //初始化栈顶下标值
}
- 非空否StackNotEmpty(S)
int StackNotEmpty(S) //判断顺序堆栈S是否为空，非空返回1，否则返回0
{
if(S.top<=0)
return 0;
else
return 1;
}
- 入栈StackPush(SeqStack *S,DataType x)
int StackPush(SeqStack *S,DataType x)//把数据元素x存入顺序堆栈S中，入栈成功返回1，否则返回0
{
if(S->top>=MaxStackSize)
{
printf("堆栈已满，无法插入！\n")
return 0;
}
else
{
S->Stack[S->top]=x;
S->top++;
return 1;
}
}
- 出栈StackPop(SeqStack *S,DataType)
int StackPop(SeqStack *S,DataType) //取出顺序堆栈S的栈顶元素值由参数d带回，出栈成功则返回1，否则返回0
{
if(S->top<=0)
{
printf("堆栈已空无数据元素出栈！\n");
return 0;
}
else
{
S->top--; //得注意top--，--top的差别
*d=S->stack[S->top];
return 1;
}
}
- 取栈顶数据元素StackTop(SeqStack S,DataType *d)
int StackTop(SeqStack S,DataType *d) //取栈顶数据元素值由参数d带回，成功返回1，不成功返回0
{
if(S.top<=0)
{
printf("堆栈已空！\n");
return 0;
}
else
{
*d=S.stack[S.top-1];
return 1;
}
}
- 撤销动态申请空间Destory(SLNode *head)
void Destory(SLNode *head)
{
LSNode *p,*p1;
p=head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p);
}
}
堆栈应用
括号匹配问题: 假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个函数，用来判别表达式中括号是否正确配对，并设计一个测试主函数。
算法思想: 检验括号是否配对可以设置一个栈，每读入一个括号，如果是左括号，则直接进栈，如果读入的是右括号，并且与当前栈顶的左括号是同类型的，则说明括号是配对的，将栈顶的左括号出栈，否则不配对。如果输入序列已经读完，而栈中仍然有等待配对的左括号，则该括号不配对。
代码实现
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include "string.h"
/*宏定义和链栈类型定义*/
typedef char DataType;
#include "LinkStack.h" //包括链栈实现文件
int Match(DataType e,DataType ch); //检验括号是否配对函数
int main()
{
LinkStack S;
char *p;
DataType e;
DataType ch[60];
InitStack(&S); //初始化链栈
printf("请输入带括号的表达式");
gets(ch);
p=ch;
while(*p)
{
switch(*p)
{
case '(':
case '[':
case '{':
PushStack(S,*p++);
break;
case ')':
case ']':
case '}':
if (StackEmpty(S))
{
printf("缺少左括号。\n");
return 0;
}
else
{
GetTop(S,&e);
if (Match(e,*p))
{
PopStack(S,&e);
}
else
{
printf("左括号不配对\n");
return 0;
}
}
default: //如果是其他字符，则不处理，直接指向下一个字符
p++;
}
}
if (StackEmpty(S))
{
printf("括号匹配\n");
return 1;
}
else
{
printf("缺少右括号\n");
return 0;
}
}
int Match(DataType e,DataType ch)
{
if (e=='('&&ch==')')
{
return 1;
}
else if (e=='['&&ch==']')
{
return 1;
}
else if (e=='{'&&ch=='}')
{
return 1;
}
else
{
return 0;
}
}
算术表达式计算问题
- 中缀表达式和后缀表达式的描述
在编译系统中，算术表达式可以分为三类：算术表达式，关系表达式，逻辑表达式。任何一个算术表达式都是由：操作数，运算符和分界符组成。我们把操作数，运算符和分界符（分界符标志了一个算术表达式的结束）称为一个算术表达式的单词。
中缀表达式：算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外）
A+（B-C/D）*E
后缀表达式：表达式中的运算符出现在操作数之后。编译系统对于中缀表达式处理方法是将其变成后缀表达式
ABCD/-E*+
- 后缀表达式的特点
- 后缀表达式的操作数和中缀表达式的操作数先后次序完全相同（上面ABCDE），只是运算符的先后次序改变了（+-/*）；
- 后缀表达式中没有括号，后缀表达式的运算次序就是其执行次序
- 后缀表达式的实现过程
编译系统设置一个存放运算符的堆栈，初始时栈顶置一个分界符“#”。编译系统从左到右依次扫描中缀表达式，每读到一个操作数就把它作为后缀表达式的一部分输出，每读到一个运算符（分界符也看作运算符）就将其优先级与栈顶运算符优先级运算符进行比较，以决定是就所读到的运算符进栈，还是将栈顶运算符作为最为后缀算术表达式的一部分输出。
- 运算符优先级别注意：若把O1看成栈顶运算符，O2看成当前扫描读到的运算符。
- 当O1为“+”或“-”，O2为“*”或“/”时，O1的优先级 < O2的优先级(满足先乘除，后加减)
- 当O1为“+”“-”“*”或“/”，O2为“（”时，O1的优先级 < O2的优先级（满足先括号内，后括号外的规则）
- 当O1的运算符和O2的运算符同级别时，O1的优先级 > O2的优先级别（同级别先左后右规则）
- 由于后缀表达式无括号，当O1为“（”，O2为“）”时，用标记“=”使算法在此时去掉该对算法；
- 当O1为“#”时，O2为“#”时，用标记“=”使算法在此时结束处理
- 若表中的值为空，则不允许出现这种情况，一旦出现即为中缀算术表达式语法出错，如O1为“）”，而O2为“（”情况，即为中缀表达式语法错误！
- 算法步骤：
（1）设置一个堆栈，初始时将栈顶元素置为#
（2）顺序读入中缀算术表达式，当读到的单词为操作数是就将其输出，并接着读下一个单词
（3）单读到的单词为运算符时，令a为当前栈顶运算符的变量，b为当前扫描读到运算符的变量，把当前读到的运算符赋给b,然后比较变量a的优先级和b的优先级。若a的优先级高于ｂ的优先级，则将ａ退栈并作为后缀表达式的一个单词输出，，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
- 若优先级 ａ＜ｂ，则将ｂ的值进栈，然后接着读下一个单词
- 若优先级 ａ＞ｂ，则将ａ退栈并作为后缀表达式的一个单词输出，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
- 若优先级 ａ＝ｂ且ａ为“（”，ｂ为“）”。则将ａ退栈，接着读下一个单词
- 若优先级 ａ＝ｂ且ａ为“＃”，ｂ为“＃”。算法结束。
函数实现
int PostExp(char str[]) //借助堆栈计算后缀表达式str的值
{
DataType x,x1,x2;
int i;
LsNode *head; //定义头指针变量head
StackInitiate(&head); //初始化链式堆栈head
for(i-0;str[i]!=#;i++) //循环直到输入为#
{
if(isdigit(str[i])) //当str[i]为操作数时
{
x=(int)(str[i]-48); //转换成int类型数据存于变量x中
StackPush(head,x); //x入栈
}
else //当str[i]为运算符时
{
StackPop(head,&x2); //退栈的操作数，存于变量x2中
StackPop(head,&x1); //退栈的被操作数，存于变量x1中
switch(str[i]) //执行str[i]所表示的运算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除数为0错误！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
StackPush(head,x1); //运算结果入栈
}
}
StackPop(head,&x); //得到计算结果存于x
return x; //返回计算结果
}
应用
设有后缀算术表达式ABCD/-E*+，其中，变量A等于3，变量B等于6，变量C等于4，变量D等于2，变量E等于5，设计一个程序，求出该后缀算术表达式的值。
代码实现
#include<stdio.h>
#include<malloc.h> //包含有exit()函数
#include<stdlib.h> //包含isdigit()函数
#include<ctype.h> //定义DataType（）函数
typedef int DataType;
#include"LinStack.h"
int PostExp(char str[]) //借助堆栈计算后缀表达式str的值
{
DataType x,x1,x2;
int i;
LsNode *head; //定义头指针变量head
StackInitiate(&head); //初始化链式堆栈head
for(i-0;str[i]!=#;i++) //循环直到输入为#
{
if(isdigit(str[i])) //当str[i]为操作数时
{
x=(int)(str[i]-48); //转换成int类型数据存于变量x中
StackPush(head,x); //x入栈
}
else //当str[i]为运算符时
{
StackPop(head,&x2); //退栈的操作数，存于变量x2中
StackPop(head,&x1); //退栈的被操作数，存于变量x1中
switch(str[i]) //执行str[i]所表示的运算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除数为0错误！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
StackPush(head,x1); //运算结果入栈
}
}
StackPop(head,&x); //得到计算结果存于x
return x; //返回计算结果
}
void main()
{
char str[]="3642/-5*+#";
int result;
result=PostExp(str);
printf("后缀算术表达式计算结果为：%d",result);
}
程序运行结果：23
腾讯云开发者
