《一章栈和队列.ppt》由会员分享，可在线阅读，更多相关《一章栈和队列.ppt（61页珍藏版）》请在三一办公上搜索。
1、第三章 栈和队列,本章内容3.1 栈3.1.1 栈的定义及基本运算3.1.2 栈的存储结构和实现3.1.3 栈的应用3.2 队列3.2.1 队列的定义及基本运算3.2.2 队列的存储结构和实现3.2.3 队列的应用,3.1.1 栈的定义及基本运算,栈(Stack)的定义 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(top),另一端为栈底(bottom)。当表中没有元素时称为空栈。,入栈,出栈,栈的特点栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,3.1.1 栈的定义及基本运算,栈的运算演示(1)A、B、C、D四个元素依次
2、进入一个栈，再依次出栈，得到一个输出序列DCBA。,ABCD,DCBA,3.1.1 栈的定义及基本运算,栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,ABCDE,操作序列：,出栈序列：,元素A入栈,A,A,元素B入栈,B,B,元素C入栈,C,C,3.1.1 栈的定义及基本运算,栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,DE,操作序列：,出栈序列：,元素A入栈,A,元素B
3、入栈,B,元素C入栈,元素C出栈,C,C,元素B出栈,B,3.1.1 栈的定义及基本运算,栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,DE,操作序列：,出栈序列：,元素A入栈,A,元素B入栈,元素C入栈,元素C出栈,C,元素B出栈,B,元素D入栈,D,D,元素D出栈,D,元素A出栈,A,3.1.1 栈的定义及基本运算,栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？,E,操作
4、序列：,出栈序列：,元素A入栈,元素B入栈,元素C入栈,元素C出栈,C,元素B出栈,B,元素D入栈,元素D出栈,D,元素A出栈,A,元素E入栈,E,E,元素E出栈,E,栈的基本运算InitStack(&S):初始化栈SStackEmpty():判断栈是否为空Push(e):将元素e放入栈顶Pop(e):移走栈顶的元素，同时由e带回该元素的值Gettop():获取栈顶的元素，但不从栈中移走,3.1.1 栈的定义及基本运算,3.1.2 栈的存储结构和实现,栈,栈的表示和实现 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，,an的次序进栈，退栈
5、的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表(Last In First Out，LIFO),3.1.2 栈的存储结构和实现,顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。,3.1.2 栈的存储结构和实现,顺序栈的类型定义/-栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SElemType*base;/栈底指针，栈构造前和销毁后为空 SEl
6、emType*top;/栈顶指针，指向栈顶元素的下一位置 int stacksize;/当前分配的栈的存储空间数SqStack;,顺序栈设S是SqStack类型的指针变量。base是栈底指针。Top是栈顶指针。栈不存在条件S.base=NULL 栈空条件S.top=S.base 插入栈顶元素，栈顶指针S.top=S.top+1 删除栈顶元素，栈顶指针S.top=S.top-1 栈满条件S.top-S.base=S.stacksize,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现,顺序栈的C语言实现(1)初始化Status InitStack(SqStack/InitStack
7、,(2)判断栈空int StackEmpty(SqStack*S)return(S.base=S.top);(3)判断栈满int StackFull(SqStack*S)return(S.top-S.base=S.stacksize);,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现,(4)元素入栈Status Push(SqStack/Push,(5)出栈void Pop(SqStack*S,SElemType,3.1.2 栈的存储结构和实现,3.1.2 栈的存储结构和实现,链栈 栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能
8、在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedef struct stacknode SElemType data;struct stacknode*next;stacknode,*linkstack;,3.1.2 栈的存储结构和实现,链栈,栈,思考 链栈是否需要另外设置头指针？建立链栈适合用哪种插入法？链栈的基本操作的实现。,链栈的基本操作 置空栈void InitStack(linkStack,3.1.2 栈的存储结构和实现,链栈的基本操作 进栈void Push(linkstack/设置栈顶指针,3.1.2 栈的存储结构
9、和实现,链栈的基本操作 退栈SElemType Pop(linkstack,3.1.2 栈的存储结构和实现,链栈的基本操作 取栈顶元素SElemType GetTop(linkstack p)if(p=NULL)error(“stack is empty.”);return pdata;,3.1.2 栈的存储结构和实现,3.2 栈的应用举例,根据栈的FILO特性，用作某些处理问题的工具。3.2.1 数制转换例：4310=1010112,输出,void conversion()InitStack(S);/构造空栈scanf(“%d”,3.2 栈的应用举例,3.2.2 括号匹配设一个表达式中可以包
10、含三种括号：“(”和“)”、“”和“”、“”和“”，并且这三种括号可以按照任意的次序嵌套使用，考查表达式中的括号是否匹配。例如：.(.).).例：a=b+(c-d)*(e-f);while(m(a8+t)m=m+1;t=t-1;实现方法利用栈进行表达式中的括号匹配自左至右扫描表达式，若遇左括号，则将左括号入栈，若遇右括号，则将其与栈顶的左括号进行匹配，若配对，则栈顶的左括号出栈，否则出现括号不匹配错误。思考：匹配的充要条件？,3.2 栈的应用举例,3.2.3 迷宫问题寻找一条从入口到出口的通路。,前进方向：上(北)、下(南)、左(西)、右(东),走步规则：首先从向下开始，按照逆时针方向搜索下一
11、步可能前进的位置,3.2 栈的应用举例,迷宫问题,(1,1),3.2 栈的应用举例,迷宫问题,3.2 栈的应用举例,迷宫问题迷宫的表示const int N=8;struct PosType int x,y;char mazeNN;/位置上的标识，是否可通过迷宫初始化用二层嵌套循环对迷宫赋值迷宫求解(见教材算法)输出栈中的路径,3.2 栈的应用举例,Status MazePath(maze,start,end)/若迷宫中存在一条从入口start到出口end的通道，则求出这样的一条通路 InitStack(S);curpos=start;curstep=1;do if(pass(curpos)/
12、当前位置可以通过 Mark(maze,curpos);/留下记号 e=(curstep,curpos,1);push(S,e);/加入路径 if(curpos=end)return true;/到达出口 curpos=NextPos(curpos,1);/下一个位置 curstep+;else/当前位置不能通过 if(!StackEmpty(S)pop(S,e);/退回一步 while(e.di=4,3.2.4 表达式求值算符优先法 4+23-10/5 先乘除,后加减;从左算到右 先括号内,后括号外 4+23-10/5=4+6-10/5=10-10/5=10-2=8 表达式由操作数(opera
13、nd)、运算符(operator)和界限符(delimiter)组成的。将运算符和界限符统称为算符。它们构成的集合命名为OP,3.2 栈的应用举例,表达式求值 算符优先算法:用两个工作栈。一个称作OPTR,用于存放运算符;另一个称作OPND,用以存放操作数或运算结果。首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直到整个表达式求值完毕(OPTR栈的栈顶元素和当前读入的字符均为“#”),3.2 栈的应用举例,OperandType EvaluateExpression(
14、)InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();else/不是运算符则进栈 switch(Precede(GetTop(OPTR),c)case:/栈顶元素优先权低 Push(OPTR,c);c=getchar();break;case=:/脱括号并接收下一字符 Pop(OPTR,x);c=getchar();break;,3.2 栈的应用举例,case:/退栈并将运算结果入栈 Pop(OPTR,th
15、eta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/while return GetTop(OPND);/EvaluateExpression,3.2 栈的应用举例,3.3 栈与递归的实现,栈与递归的实现用栈结构实现程序设计语言中函数的嵌套调用和递归调用例：long f(int n)if(n1)return n*f(n-1);else return 1;void main()int n=4;printf(“%ld”,f(n);,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔 问题假设有三个分别命名为
16、X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1，2，,n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排。每次只能移动一个圆盘；圆盘可以插在X、Y和Z中的任一塔座上；任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Base case:n=1 X Z,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Base case:n=1 X Z,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Recursion:n 1 前n-1 个盘:X Y,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Re
17、cursion:n 1 前n-1 个盘:X Y,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Recursion:n 1 最大盘:X Z,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Recursion:n 1 最大盘:X Z,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Recursion:n 1 前n-1个盘:Y Z,栈与递归,3.3 栈与递归的实现,n阶Hanoi塔问题Recursion:n 1 前n-1个盘:Y Z,栈与递归,3.4.1 队列的定义及基本运算,队列(Queue)的定义队列是仅限定在表尾进行插入和表头进行删除操作的线性表。术语队头(front)队列
18、的表头，即只允许删除的一端。队尾(rear)队列的表尾，即只允许插入的一端。入队(EnQueue)向队尾插入元素。出队(DeQueue)从队头删除元素。,队列的特点队列的修改是按先进先出的原则进行的。因此，队列称为先进先出表（FIFO）。,3.4.1 队列的定义及基本运算,队列的基本运算InitQueue(&Q):初始化队列QQueueEmpty():判断队列是否为空EnQueue(e):将元素e放入队尾DeQueue(e):移走队头元素，由e带回该元素的值GetFront():获取队头元素的值，但不从队列中移走该元素Length():计算并返回队列中元素的个数,3.4.2 队列的存储结构和实
19、现,链队列队列的链式存储结构,3.4.2 队列的存储结构和实现,链队列的C语言实现/-单链队列的存储结构-typedef struct QNode/链表结点类型 QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct/队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针LinkQueue;,Status InitQueue(LinkQueue,3.4.2 队列的存储结构和实现,链队列基本操作的实现(1)初始化,(2)入队Status EnQueue(LinkQueue,3.4.2 队列
20、的存储结构和实现,Status DeQueue(LinkQueue,3.4.2 队列的存储结构和实现,(3)出队列,思考：如果不设置头结点，需要考虑那些特殊情况？,3.4.2 队列的存储结构和实现,循环队列队列的顺序存储结构,循环队列,循环队列的C语言实现/-循环队列的存储结构-#define MAXSIZE 100typedef struct QElemType*base;int front;int rear;SqQueue;,3.4.2 队列的存储结构和实现,循环队列基本操作的实现(1)初始化Status InitQueue(SqQueue,3.4.2 队列的存储结构和实现,3.4.2 队
21、列的存储结构和实现,循环队列基本操作的实现(2)入队Status EnQueue(SqQueue,循环队列基本操作的实现(3)出队Status DeQueue(SqQueue,3.4.2 队列的存储结构和实现,双端队列,双端队列,队头,队尾,出队,入队,出队,入队,输出受限的双端队列,队头,队尾,出队,入队,入队,双端队列,输入受限的双端队列,队头,队尾,出队,入队,出队,优先队列,在许多情况下，简单的队列结构是不够的，需要使用某些优先规则来完善先入先出机制，例如,优先队列的问题是如何找到一种实现优先的方法，使得入队和出队列操作得以相对容易实现。,优先队列可以通过两种修正的链表结构来实现。一种结构是元素仍然依次进入（即加入元素时，时间复杂度为O(1)），而取出元素时则需遍历队列（即出队时的时间复杂度为O(n)），另一种是根据元素的优先级决定其插入的位置（即入队时的时间复杂度为O(n)，出队时的时间复杂度为O(1)）。,3.4.3 队列的应用,同栈一样，队列也是一种应用广泛的线性表，在日常生活和计算机科学中很常见：离散事件模拟排队问题作业控制广度优先搜索.,本章小结,本章应掌握的内容栈的定义、运算顺序栈、链栈队列的定义、运算及实现循环链队列、循环顺序队列,
