北京理工大学数据结构栈和队列课件.ppt

1、第3章堆栈和队列，3.1堆栈，3.1.1堆栈1的概念。什么是堆栈？堆栈是一个线性表，只能在表的末尾插入和删除。(a1，a2，ai -1，ai，ai 1，an)，插入和删除。可以插入和删除的末端称为堆栈顶部。插入操作称为推栈，删除操作称为推栈。栈入和栈出操作只能在栈顶执行。3.1堆叠，堆叠的特征是后进先出，堆叠底部的第一个堆叠元素，堆叠顶部的第一个堆叠元素，堆叠底部的最后一个堆叠元素，3.1堆叠，2。堆栈的基本操作1)初始化操作初始化堆栈(/堆栈空间基地址元素类型*顶部；/堆栈顶部指针int stacksize/当前分配的堆栈空间大小SqStack，3.1堆栈，3.1.2堆栈顺序存储和实现，顺序

2、堆栈图，S.stacksize S.top S.base，100，同意顶部指针指向顶部元素的下一个位置，3.1堆栈，3.1.2堆栈顺序存储和实现，顶部，底部，空堆栈，B C D .空堆栈顶部=基础堆栈满顶部-底部=stacksize(无分配空间)，3.1堆栈，不可扩展堆栈操作，堆栈空，堆栈顶部指针顶部，指向实际堆栈后面的空位置推入堆栈，a，堆栈满，B，C，D，E，将数组大小设置为M top=M，堆栈满，此时进入Top=base，堆栈为空，当堆栈弹出时，它下溢并弹出。3.1堆栈可以扩展。堆栈顶部指针指向实际堆栈顶部后面的下一个位置，初始值top=base，推入堆栈，A，弹出，当前堆栈空间不足，需

3、要扩展，b .如果top=Stacksize，堆栈已满，需要扩展堆栈空间，扩展STACK _ INDENTATION；每次。如果没有可用的存储空间，则溢出。堆栈为空，如果top=base，则堆栈为空，然后下溢)，base，堆栈为空，top，3.1堆栈，2。顺序堆栈的基本操作算法1)初始化操作初始化堆栈(SqStack Push (OPTR，#)；初始堆栈(OPND)；c=getchar()；而(c！=# | GetTop(OPTR)！=# ) if(！在(c，OP)中/在(c，OP)中判断c是否是操作符推送(OPND，c)；c=getchar()；/stack else如果不是运算符，3.2堆

4、栈应用示例，switch(preference(gettop(OPTR)，c)/确定OPTR的顶级运算符1和读入运算符2之间的优先级关系(case 3360/新输入的运算符c优先级较低，即顶级运算符优先级较高/将运算结果堆栈到OPND Pop (OPTR，theta) Pop (OPND，b)中；流行音乐(OPND，a)；推动(OPND，操作(a，b)；/执行二进制运算a b中断；/返回GetTop(OPND)时切换/；/EvaluateExpression，3.2堆栈应用示例，递归是一个非常有用的工具，它被用在很多领域，比如数学和编程。递归定义：简单地说，一个自己定义自己的概念叫做递归定义。

5、任何递归程序都可以用非递归程序来实现。3.3堆栈和递归，3.4.1队列1的概念。什么是队列？队列是一个线性表，只能在页眉处删除，在页脚处插入。(a1，a2，ai -1，ai，ai 1，an，insert，delete，可插入的末端称为队列尾部，可删除的末端称为队列头部。插入操作称为入队，删除操作称为出列。3.4队列、a1a23an、队列头、队列尾、队列出口、队列特征先入先出，首端第一个入队元素和尾端最后一个入队元素是头元素，最后一个入队元素是尾元素、3.4队列、2。队列1/队长指针的基本操作，指向后方的队长元素；/行尾指针，指向行尾元素的下一个位置SqQueue团队领导和团队尾指针由整数实现，

6、3.4队列，(a)空队列，(b)J1、J2和JBOY3乐队相继加入队列，(c)J1和J2相继离开团队，(d)J4、J5和J6相继加入团队，JBOY3乐队离开团队，q .前端和q .后端都是整数，用箭头表示只是为了直观。尾部指向队列末尾元素的下一个位置；前面指向团队领导元素。初始值为前=后=0，队列条件为：前=后；队列：q .基地后方=e；后方；排队外：e=Q .基地前沿；正面；Q.base、3.4队列、有问题。如果数组大小为M，那么：当前端=0，后端=M时，当前端0，后端=M时发生溢出，当重新排队时发生溢出。错误的溢出解决方案队列的第一个元素是固定的，剩余的元素在每个队列之后下移，这浪费了时间

7、。循环队列的基本思想是：后方，j4，j5，j6入队，J4，J5，J6，前方，3.4队列，实现：通过“模”运算入队：后部=(后部1)% M；团队外：e=Q基地前沿；前=(前1)% M；判断一个团队是满还是空的标准是什么？J7，J9，J8，团队空：前=后，解决方案：1。设置另一个标志，以区分空队和满队；2.少用一个元素空间：组空：前=后满：(后1)% M=前，满：前=后，3.4少用一个元素空间：队列空：前=后队列满：(后1)% M=前，队列空：前=后，J7，J8，1)初始化操作init queue _ sq(sqqueue/init queue _ sq，2)。循环队列的基本运算算法，3.4队列，QNode，* QueuePtr，3.4 queue，typedef struct /链队列的头节点的类型定义了QueuePtr front/队列头指针，指向链表尾部的队列头节点；/团队尾部指针，指向团队尾部节点链接队列；前端指向头节点，后端指向队列的末端，3.4