第3章 栈和队列

第三章栈和队列

[内容提要]1.栈和队列的概念

2.栈和队列的存储结构及它们的应用

3.栈和队列与线性表的联系

2定义：栈(Stack)是限制仅在表的一端进行插入和删除操作的线性表。允许进行插入和删除的一端称为栈顶(top)不允许插入和删除的一端称为栈底(bottom)不含元素的栈称为空栈。往栈中存入元素称为入栈从栈中输出元素成为出栈特点：后进先出(LIFO)或先进后出（FILO）栈的基本概念栈的示例图a3a2a13出栈入栈top

栈的顺序存储结构(顺序栈)

顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，通常用一维数组存放栈的元素。设“指针”top指示栈顶元素的当前位置或后一空位置(下标)。4

5顺序栈的类型说明：

#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];inttop;}SeqStack;6MaxTop...210stop=0（初始状态，栈为空）记录当前堆栈顶端的索引值SeqStacks;s.top=0;MAXSIZE-1

顺序栈的几种情况

7base123450栈空栈顶指针top,指向实际栈顶后的空位置.top123450进栈Atop出栈栈满BCDEF设数组大小为maxsizes.top=0,栈空，此时出栈，则下溢s.top=maxsize,栈满，此时入栈，则上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空topbasebase假设maxsize＝６8初始化（栈置空）操作判栈空函数

进栈操作出栈函数

读栈顶元函数顺序栈上实现的操作9栈的链式存储结构定义：栈的链式存储结构，简称链栈，它的组织形式与单链表类似，链表的尾部结点是栈底，链表的头部结点是栈顶。

10栈的链式存储结构a1topdatanexta2a3a4NULL栈顶栈底

链栈的类型定义：

typedefstructnode{intdata;structnode*next;}StackNode;StackNode*top;

11初始化操作进栈操作出栈操作链栈上实现的操作12用除法把十进制数转换成二进制数，把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）,十进制数35转换成二进制数35178421011001余数结果：10011栈的应用举例———进制转换13栈的应用实例——表达式求值

对下面的算术表达式求值1+2*4-9/3

必须遵循先乘除后加减、先左后右及先括号内后括号外的四则运算法则，其计算顺序应为：

1+2*4-9/3└─┘└┘

①③└──┘②└────┘④

采用“运算符优先数法”

对每种运算符赋于一个优先数，如：

运算符：*/+-#

优先数：22110

其中#是表达式结束符。

对表达式求值时，一般设立两个栈，一个称为运算符栈(OPTR)。另一个称为操作数栈(OPND)，以便分别存放表达式中的运算符和操作数表达式的表示法及计算——不带括号1.建立操作数和运算符堆栈，初始为空2.当表达式尚未读取完时：(从左到右）

读取一个运算单元（1）若是操作数，则将其存入操作数堆栈（2）若是运算符：

14if(运算符堆栈为空)

运算符直接入栈15

else{和栈顶运算符比较优先级（比较优先数的大小）；

if(比栈顶运算符优先级高)运算符直接入栈

else{while(比栈顶运算符优先级低或等&&运算符栈不为空) {从操作数堆栈取两个操作数 从操作符堆栈取一个操作符 运算后将结果压入操作数堆栈 }

将运算符直接入栈

}}1＋2×4－9/3

操作数栈运算符栈16124+*89/36-9317

步骤OPTR栈OPND栈输入字符主要操作────────────────────────────────────

1#1+2*4-9/3#PUSH(OPND,'1')2#1+2*4-9/3#PUSH(OPTR,'+')3#+12*4-9/3#PUSH(OPND,'2')4#+12*4-9/3#PUSH(OPTR,'*')5#+*124-9/3#PUSH(OPND,'4')6#+*124-9/3#operate('2','*','4')7#+18-9/3#operate('1','+','8')8#9-9/3#PUSH(OPTR,'-')9#-99/3#PUSH(OPND,'9')10#-99/3#PUSH(OPTR,'/')11#-/993#PUSH(OPND,'3')12#-/993#operate('9','/','3')13#-93#operate('9','-','3')14#6#RETURN(TOP(OPND))────────────────────────────────────

利用算法对算术表达式1+2*4-9/3求值的操作过程栈与递归18

递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数。在每次调用时系统将属于各个递归层次的信息组成一个活动记录（ActivaTionRecord），这个记录中包含着本层调用的实参、返回地址、局部变量等信息，并将这个活动记录保存在系统的“递归工作栈”中，每当递归调用一次，就要在栈顶为函数建立一个新的活动记录，一旦本次调用结束，则将栈顶活动记录出栈，根据获得的返回地址信息返回到本次的调用处。举例如下：19

main(){intm，n=3;m=fact(n);A1：

printf(“%d!=%d\n”，n，m);}

intfact(intn){

intf;

if(n==1)f=1;

elsef=n*fact(n-1);A2:returnf;}20

参数返回地址fact(0)0A2fact(1)1A2fact(2)2A2fact(3)3A1其信息如下：定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)或后进后出(LILO)21a1a2a3…….an入队出队frontrear队列队列的顺序存储结构

定义：队列的顺序存储结构，简称顺序队列，它是由一个存放队列中元素的一维数组，及分别指示队头和队尾的“指针”所组成。

22cb尾指针头指针23顺序队列的类型定义：

#defineMAXSIZE1024/*队列的最大容量*/typedefstruct{intdata[MAXSIZE];/*队员的存储空间*/intrear,front;/*队头队尾指针*/}SeQueue;

顺序队列的几种状态24front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rear设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront循环队列的引入

顺序队列存在的问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出当front-1,rear=M-1时，再有元素入队发生溢出——假溢出解决方案——循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];新问题：队满、队空判定条件250M-11frontrear…...…...rear123450已入J4,J5,J6J4J5J6front26012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front

解决方法：规定当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：(rear+1)%M==front。27a2a3a4a5a7a6a101234567frontrear队满28#defineMAXSIZE100

typedefstruct{intdata[MAXSIZE];intfront,rear;}c_SeQueue;/*循环队*/循环队列的类型定义在循环队列上实现的操作

初始化操作的实现判队空函数判队满入队列操作出队列操作29队列的链式存储结构

定义:队列的链式存储结构，简称链队列,它实际上是一个同时带有头指针和尾指针的单链表，头指针指向头结点，尾指针指向队尾结点3031头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾typedefstruct{elemtpdata;nodetype*next;}nodetype链队列的类型定义typedefstruct{nodetype*front;nodetype*rear;}lqueuetp在链队列上实现的操作

初始化操作的实现判队空函数入队列操作出队列操作32队列的应用--求迷宫的最短路径33

迷宫问题是指在一个m*n的矩阵中，其中“0”代表可以行走的区域，“1”代表不可行走的区域，当你处在迷宫的任何一个位置，可以往上、下、左、右、左上、右下、左下、右上八个方向行走来找寻迷宫出口。迷宫示例34入口1234567810111011121010101030100111140111