《数据结构-栈与队列讲述》由会员分享，可在线阅读，更多相关《数据结构-栈与队列讲述（53页珍藏版）》请在金锄头文库上搜索。
1、栈与队列栈与队列 栈的定义 栈是限制在表的一端进行 插入和删除操作的线性表。允 许进行插入和删除操作的一端 称为栈顶，另一端称为栈底。 如果多个元素依次进栈， 则后进栈的元素必然先出栈， 所以堆栈又称为后进先出（ LIFO）表。堆栈设有一个栈顶 指针标志栈顶位置。 栈示意图 a1 a3 a2 进栈出栈 top 堆栈的主要操作有： 创建空栈。 进栈(push)操作: 在栈顶插入元素。 出栈(pop)操作: 在栈顶删除元素。 读栈顶元素: 只是读出栈顶元素，并不 改变栈内元素。 顺序栈 同顺序表一样，可利用一维数组来实现。定义如下 ： struct SqStack ElemType *data;/
2、存储元素的数组 int top; /栈顶指针，存储栈顶元素下标 int stacksize; /最大可用空间数量 ; struct SqStack s; /定义一个堆栈s 一般将数组的0下标单元作为栈底，将栈顶元素 的下标存储在栈顶指针top中，它随着元素进栈出栈 而变化。top为-1表示空栈，top等于stacksize-1则表 示栈满。 （1）顺序栈初始化 堆栈的初始化主要是为存储元素的数组申请空间，下面的 初始化函数申请了长度为size的空间。 void InitStack(SqStack *s, int size) if( size 0 ) s-stacksize = size; s-
3、top = -1; s-data = (ElemType *)malloc(size*sizeof (ElemType); / 申请空间 else printf(“堆栈初始化长度错误“); （2）进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶。 void Push(SqStack *s, ElemType x) if(s-top stacksize-1) s-top+; s-datas-top=x; else printf(“栈满”); （3）出栈操作 若栈不空，则删除s的栈顶元素，用e返回其值 void Pop (SqStack *s, ElemType s-top-; else pri
4、ntf(“栈空”); （4）取栈顶元素 若栈不空，则用e返回s的栈顶元素。 void GetTop(SqStack *s, ElemType else printf(”栈空”); 链式栈 栈的链式存储结构实质上就是一个无头结点、 只能在头部插入、删除元素的单链表。 typedef struct node ElemType data; /数据域 struct node *next; /指针域 SNode, *LinkStack; LinkStack top； /定义栈顶指针 这里SNode可用来定义结点，LinkStack用来定 义栈顶指针。 （1）进栈操作 若栈不满，则在栈顶插入元素x作为新的
5、栈顶。 void Push(LinkStack top, ElemType x) SNode *p=( SNode *)malloc(sizeof(SNode); if(p!=NULL) p-data=x; p-next=top; top=p; （2）出栈操作 若栈不空，则删除栈顶元素，用e返回其值。 void Pop (LinkStack top, ElemType e); SNode *p; if(top!=NULL) e= top-data; p=top; top=top-next; free( p); 举例 : 后缀表达式求值 假定表达式是由加减乘除和数字构成。最简 单的表达式为下列形
6、式： (操作数S1)(运算符OP)(操作数S2) 三种不同的表示方法： 前缀表示法 OPS1S2 例如6+3写成+63 中缀表示法 S1OPS2 例如6+3写成6+3 后缀表示法 S1S2OP 例如6+3写成63+ 同时，任何表达式都可分解为下列形式： (子表达式E1)(运算符OP)(子表达式E2) 它的后缀表示法应写成： (E1的后缀表示)(E2的后缀表示)OP 只要不断对子表达式进一步分解，总能将子表达 式分解为最简单形式，因此任何四则运算表达式 都可写成前缀式或后缀式。 例如： 2*(6+3) 2(6+3)* 263+*。 (注意：转化为后缀式后括号去掉) 中缀式虽然容易理解，但在求值的
7、时候利 用前缀式或后缀式更为简单。用后缀式求 值的算法为： 首先设立一个堆栈，依此读取后缀式首先设立一个堆栈，依此读取后缀式 中的字符，若字符是数字，则进栈并继续中的字符，若字符是数字，则进栈并继续 读取，若字符是运算符（记为读取，若字符是运算符（记为OPOP），则连），则连 续出栈两次得到数字续出栈两次得到数字S S 1 1 和和S S 2 2 ，计算表达式，计算表达式 S S1 1 OPOPS S 2 2 并将结果入栈，继续读取后缀式。并将结果入栈，继续读取后缀式。 当读到结束符时停止读操作，这时堆栈中当读到结束符时停止读操作，这时堆栈中 只应该有一个数据，即结果数据。只应该有一个数据，即
8、结果数据。 例如后缀式263+*的计算过程为2、6、3依 次入栈，读+号则令3和6依次出栈，计算 6+3后将结果9入栈，读*号则令9和2依次 出栈，计算2*9后将结果18入栈。这时18 就是最终结果。 【例2-3】假定表达式是由不超过过四个实 数进行四则运算构成的算式，要编写一个 程序来求解该该算式的结结果。 采用顺序栈 计算后缀表达式 #include struct SqStack double *data;/存储元素的数组 int top; /栈顶指针，存储栈顶元素的下标 int stacksize; /堆栈最大可分配空间数量，以元素为单位 ; / 初始化 void InitStack(s
9、truct SqStack s, int size ) if( size 0 ) s.stacksize = size; s.top = -1; s.data = (double *)malloc(size*sizeof(double); / 申请空间 else printf(“堆栈初始化长度错误“); / 入栈 void Push(struct SqStack s, double x) if(s.top -1) e= s.datas.top; s.top-; else printf(“栈空“); int main() struct SqStack T;/定义一个堆栈 double a,b,c
10、,d; char exp20;/存储表达式的数组，最长20个字符 double num1,num2; printf(“依次输入a、b、c、d的值：“); scanf(“%f,%f,%f,%f”,/输入a,b,c,d的数值 printf(“输入表达式：“); scanf(“%s”,exp);/输入a,b,c,d组成的表达式 InitStack(T, 20);/堆栈初始化 / 处理字符数组，计算后缀表达式 for(int i=0; expi!=0; i+) switch(expi) case + : case - : case * : case / : Pop(T,num2);Pop(T,num1
11、); if(expi=+)Push(T,num1+num2); if(expi=-)Push(T,num1-num2); if(expi=*)Push(T,num1*num2); if(expi=/)Push(T,num1/num2); break; default : if(expi=a)Push(T,a); if(expi=b)Push(T,b); if(expi=c)Push(T,c); if(expi=d)Push(T,d); Pop(T,num1); printf(“结果为：%f”,num1); return 0; 中缀表达式变成等价的后缀表达式 将中缀表达式变成等价的后缀表达式，表
12、达式中 操作数次序不变，运算符次序发生变化，同时去 掉了圆括号。转换规则是：设立一个栈，存放运设立一个栈，存放运 算符，首先栈为空，编译程序从左到右扫描中缀算符，首先栈为空，编译程序从左到右扫描中缀 表达式，若遇到操作数，直接输出，并输出一个表达式，若遇到操作数，直接输出，并输出一个 空格作为两个操作数的分隔符；若遇到运算符，空格作为两个操作数的分隔符；若遇到运算符， 则必须与栈顶比较，运算符级别比栈顶级别高则则必须与栈顶比较，运算符级别比栈顶级别高则 进栈，否则退出栈顶元素并输出，然后输出一个进栈，否则退出栈顶元素并输出，然后输出一个 空格作分隔符；若遇到左括号，进栈；若遇到右空格作分隔符；
13、若遇到左括号，进栈；若遇到右 括号，则一直退栈输出，直到退到左括号止。当括号，则一直退栈输出，直到退到左括号止。当 栈变成空时，输出的结果即为后缀表达式。栈变成空时，输出的结果即为后缀表达式。 步骤 栈中元素 输出结果 说明 1 ( （进栈 2(1输出1 3( +1+进栈 4( +1 2输出2 5 1 2 +退栈输出，退栈 到（止 6*1 2 +*进栈 7* (1 2 +（进栈 8* ( (1 2 +（进栈 9* ( (1 2 + 8输出8 10* ( ( -1 2 + 8 - 进栈 将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达 式。 现在用栈来实现该运算，栈的变化及输出结
14、果如下 ： 11* ( ( -1 2 + 8 2输出2 12* (1 2 + 8 2 -退栈输出，退 栈到（止 13* ( /1 2 + 8 2 -/ 进栈 14* ( / (1 2 + 8 2 -（ 进栈 15* ( / (1 2 + 8 2 - 7输出7 16* ( / ( -1 2 + 8 2 - 7- 进栈 17* ( / ( -1 2 + 8 2 - 7 4输出4 18* ( /1 2 + 8 2 - 7 4 -退栈输出，退 栈到（止 19*1 2 + 8 2 - 7 4 - /退栈输出，退 栈到（止 20 1 2 + 8 2 - 7 4 - / * *退栈并输出 栈的应用举例 由于
15、栈结构具有的后进先出的固有特性， 致使栈成为程序设计中常用的工具。以下 是几个栈应用的例子。 数制转换 十进制N和其它进制数的转换是计算机 实现计算的基本问题,其解决方法很多,其中 一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下 ： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) initstack(s); scanf (“%”,n); while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e); printf(“%d”,e); 括号匹配的检验 假设表达式中充许括号嵌套,则检验括号 是否匹配的方法可用“期待的急迫程度”这个 概念来描述。例： （）（） （） 队列定义 队列是只能在表的一端进行插入、在另一 端进行删除操作的线性表。允许删除元素的一 端称为队头，允许插入元素的一端称为队尾。 显然不论元素按何种顺序进入队列，也必 然按这种顺序出队列，所以队列又称为先进先 出（FIFO）表。队列有两
