《孙丽云数据结构第3章栈和队列(第8-10讲)》由会员分享，可在线阅读，更多相关《孙丽云数据结构第3章栈和队列(第8-10讲)（40页珍藏版）》请在金锄头文库上搜索。
1、1,绪 言,从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。,2,3.1 栈,栈，也叫堆栈，是最常用也是最重要的数据结构之一。 栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 举例： 栈操作的特点：后进先出。 因此，栈称为后进先出表（LIFO, Last In First Out）。,3,栈顶,入栈,出栈,进栈出栈示意图,栈底,
2、4,初始化栈InitStack(S) 设置一个空栈S。 压栈Push(S,x) 将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 取栈顶元素GetTop(S,x) 若栈S不空，则由x返回栈顶元素。 判栈空Empty(S) 若栈S为空栈，结果为1，否则结果为0。,2栈的基本运算,在栈顶插入元素,在栈顶删除元素,5,3.1.2 栈的顺序存储结构及其基本运算的实现,栈有两种存储表示方法:顺序存储和链式存储 1、栈的顺序存储结构 栈的顺序存储结构简称为顺序栈。是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针
3、top指示栈顶元素在顺序栈中的位置。,（a）当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值top=-1。 （b）表示在（a）基础上执行Push(S, A)后得到这种状态。 （c）又有三个元素B、C、D先后入栈，此时栈顶元素的下标值top=3。栈已满。 （d）表示在（c）状态下，执行一次Pop(S，x)运算得到。 （e）表示在（d）状态下，执行三次Pop(S，x)运算得到。此时栈顶下标值top=-l，又变成栈空状态,顺序栈的几种状态（最大长度MaxSize为4）,7,顺序栈的C语言描述如下：,#define MaxSize typedef struct ElemType dataMax
4、Size; int top; STACK;,ElemType 为栈中元素的数据类型，可以根据需要而指定为某种具体的类型。 成员data:为一个一维数组，用于存储栈中元素。 成员top:栈顶指针。取值范围为0MaxSize-1。 top=-1表示栈空，top=MaxSize-1表示栈满。,8,2基本运算在顺序存储结构的实现,（1）初始化栈InitStack(S) void InitStack(STACK *S) S-top=-1; （2）压栈Push(S,x) int Push(STACK *S,ElemType x) if(S-top=MaxSize-1) printf(“n Stack is
5、 full!“); return 0; S-top+; S-dataS-top=x; return 1; ,注意压栈顺序： （1）top指针加1； （2）元素压入,9,2基本运算在顺序存储结构的实现,（3）出栈Pop(S,x) int Pop(STACK *S, ElemType *x) if(Empty(S) printf(“n Stack is free!“); return 0; *x=S-dataS-top; 记住要删除的元素值 S-top-; return 1; ,传址,自定义函数一次只能有一个返回值,10,2基本运算在顺序存储结构的实现,（4）取栈顶元素GetTop(S,x) in
6、t GetTop(STACK *S, ElemType *x) if(Empty(S) printf(“n Stack is free!“); return 0; *x=S-dataS-top; return 1； （5）判栈空Empty(S) int Empty(STACK *S) return (S-top=-1?1:0);,11,1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当出栈时，top变化为 。 A. top不变 . top-n C. toptop-1 D. top=top+1,C,课堂练习,12,C,课堂练习,2.若进栈序列为1,2,3,4,
7、进栈过程中可以出栈，则 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4,3、假设以S和X分别表示进栈和退栈操作，则对输入序列1,2,3,4,5进行一系列栈操作SXSSXSSXXX之后，得到的输出序列为 。,13542,试找出所有可能的出栈序列,13,栈的应用举例 应用栈解决数制的转换问题,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,14,栈的应用举例 应用栈解决数制的转换问题,char B=
8、“0123456789ABCDEF”; void DecToOthers(int n,int b) int x; STACK st; InitStack( ,16进制数时！,15,3栈的共享存储单元,两个栈共享大小为m的内存空间时，分配方法的示意图如下：,两个栈的共享存储单元可用C语言描述如下： #define MaxSize typedef struct ElemType dataMaxSize; int top2; STACK;,最大限度的利用栈空间,16,（1）两个栈共享存储单元的压栈算法,int Push(STACK *S,ElemType x,int k) if(S-top0+1=S
9、-top1) printf(“n stack is full!“); return 0; if(k=0) S-top0+; S-dataS-top0=x; else S-top1-; S-dataS-top1=x; return 1; ,判断栈是否溢出,17,（2）两个栈共享存储单元的出栈算法,int Pop(STACK *S,int k,ElemType *x) if(k=0) ,18,3.1.3 栈的链式存储结构及其基本运算的实现,1.栈的链式存储结构 栈的链式实现是以链表作为栈的存储结构，栈的链式实现称为链栈。插入和删除运算只能在链栈的栈顶进行。,链栈结构示意图：,top栈顶指针，惟一的
10、确定一个链栈。,19,3.1.3 栈的链式存储结构及其基本运算的实现,链栈的C语言描述如下： typedef struct snode /定义链栈结点类型 ElemType data; struct snode *next; LinkSTACK; LinkSTACK *top;,top的后继指针指向栈顶元素。,20,链栈的几种状态:,21,表达式的三种表示方法：,设 Exp = S1 OP S2,则称 OP S1 S2 为前缀表示法,S1 OP S2 为中缀表示法,S1 S2 OP 为后缀表示法,3.2 栈的应用 表达式求值,例如: Exp = a b + (c d / e) f,前缀式: +
11、 a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +,22,3.2 栈的应用 中缀表达式求值,“算符优先法” 的基本思想： （1）操作数栈置为空栈，表达式起始符“#”为运算符栈的栈底元素。 （2）从左到右扫描表达式，依次读入表达式中每个字符。若所读字符为“#”，且操作符的栈顶元素也为“#”时，则输出操作数栈中的栈顶数据，即为运算的结果，结束处理。否则，进行下面处理。 （3）若为操作数，入操作数栈；若为操作符，则要将当前操作符和操作符栈中的栈顶操作符进行优先级比较。,23,如果当前操作符的优先级大于栈顶操作符的优先级，则将当前操作符压人
12、操作符栈中；转第(2)步。 如果当前操作符的优先级等于栈顶操作符的优先级，则将当前操作符栈顶的操作符出栈。转第(2)步。 如果当前操作符的优先级小于栈顶操作符的优先级，将当前操作符栈顶的操作符出栈。并从操作数栈中顺次出栈两个操作数（先退出作为运算符的右操作数，后退出作为运算符的左操作数）。用刚出栈的操作符对两个操作数进行计算求值，将所得值压入操作数栈中。转第(3)步。,3.2 栈的应用 中缀表达式求值,24,算术表达式3（7-2）求值的动态过程,中缀表达式转换为等价的后缀表达式,中缀表达式 等价后缀表达式 0.3(52+1) 0.3 5 21+/ 16-9(4+3) 16 9 4 3+- 2(
13、x+y)/(1-x) (25+x) (a(a+b)+b),25 x+a a b+b+,2 x y +1 x-/,26,先找运算符，再找操作数。,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,如何从后缀式求值？,27,3.3 栈与递归,递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多问题的算法设计。在计算机内部，通过栈来实现递归算法。所以递归是栈的一个实际应用。,例：汉诺塔的递归过程,28,void Hano
14、i (int n, char x, char y, char z) if (n = = 1) move(x,1,z); else Hanoi ( n-1, x, z, y); move(x,n,z); Hanoi ( n-1, y, x, z); ,算 法,29,3.4.1 队列的定义和运算,1队列的定义 队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。 队列特点： 先进先出(FIFOFirst In First Out),30,2.队列的基本运算,队列初始化InitQueue(SQ) 设置一个空
15、队列SQ。 入队列EnQueue(SQ，x) 将x插入到队列SQ的队尾。 出队OutQueue(SQ，x) 将队头元素赋给x，并删除队头元素。 取队头元素GetHead(SQ，x) 由x返回队头结点的值。 判队列空Empty(SQ) 队列SQ是否为空。若为空返回1，否则返回0。,31,3.4.2 队列的顺序存储结构及其基本运算的实现,队列有两种存储表示方法:顺序存储和链式存储 1队列的顺序存储结构 队列的顺序存储结构简称顺序队。 顺序队是用一维数组依次存放队列中的元素和分别指示队列的首端和队列的尾端的两个变量组成。这两个变量分别称为“队头指针”和“队尾指针”。,顺序队列的数据类型定义如下,#define MaxSize typedef struct ElemType dataMaxSize; int front,rear; SQUEUE;,与顺序表、顺序栈比较,32,顺序队列的设置,队列中元素用一维数组存储，数组的低下标一端为队头，高下标一端为队尾。 头
