数据结构：第三章 栈和队列

1、三、栈和队列3.1 栈3.1.1 栈的定义只允许在一端操作（插入和删除）的线性表允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom)特点 后进先出 (LIFO)退栈进栈a0an-1an-2topbottom三、栈和队列 3.1.2 顺序栈 顺序栈包括栈表和栈顶下标top，初始栈为空时，设置top=-1，入栈时top+，出栈时top-。三、栈和队列 顺序栈入栈、出栈操作三、栈和队列 顺序栈入栈、出栈操作三、栈和队列 3.1.3 链栈 链栈使用单链表实现，无栈满，存在栈空，栈的空间可扩展。topa1a2三、栈和队列 链栈入栈操作三、栈和队列链栈入栈操作注意(1)、(2)两步

2、骤不能对换三、栈和队列 链栈出栈操作三、栈和队列链栈出栈操作三、栈和队列链栈取栈顶元素操作三、栈和队列链栈清空元素操作三、栈和队列3.2 栈的应用1.数制转换十进制4325转为转为八进制数: N N/8 N%8 540 5540 67 467 8 38 1 01 0 1 三、栈和队列三、栈和队列3.3 栈与递归 函数1运行期调用另外一个函数2时，系统需要将实参和返回值地址传递给函数2，这些数据域函数2中的局部变量构成一条“工作记录”，被压入系统运行时栈中。函数2调用完毕，按照“工作记录”中的返回地址找到函数1中的下一条指令，并释放运行栈中的工作记录。多个函数嵌套调用时：三、栈和队列三、栈和队列

3、fact(3)执行时 运行栈 的状态三、栈和队列汉诺塔游戏 A B C要将A中的n各圆盘移动到C，要求每次移动一个盘子，任何时候不能将盘子放在比它小的盘子上面（即按照从小到大的顺序保持每根轴上的圆盘位置），问如何移动？三、栈和队列三、栈和队列算法思想：三、栈和队列算法实现：三、栈和队列3.4 队列定义队列是只允许在一端删除，在另一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO, First In First Out)a0 a1 a2 an-1frontrear入队出队3.4.1 队列的定义三、栈和队列3.4.2 队列的实现1.顺序

4、队列顺序队列的进队和出队 frontrear空队列frontrearA进队AfrontrearB进队A BfrontrearC, D进队A B C DfrontrearA退队B C DfrontrearB退队C DfrontrearE,F,G进队C D E F GC D E F GfrontrearH进队,溢出 进队时将新元素按 rear 指示位置加入,队尾指针进一 rear = rear + 1. 出队时将下标为 front 的元素取出,队头指针 进一 front = front + 1 队满时再进队将溢出出错； 队空时再出队将队空处理。 由于在顺序队列中,往往容易造成假满,浪费队列的空间,

5、解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。 三、栈和队列三、栈和队列2.循环队列队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从MaxQSize -1直接进到0，可用语言的取模(余数)运算实现。牺牲一个空单元确保“假溢出”队头指针进1: front = (front+1) % MaxQSize ;队尾指针进1: rear = (rear+1) % MaxQSize ;队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear+1) % MaxQSize = front 2.循环队列类的实现三、栈和队列01234567f

6、ront01234567front01234567frontrearAABCrearrear空队列A进队B, C进队0123456701234567A退队B退队01234567D,E,F,G,H, I进队frontBCrearAfrontBCrearfrontCrearDEFGHI三、栈和队列01234567C出队BfrontrearDEFGHIC出队后，队列非满，(rear+1) % MaxQSize ！= front 012345J入队BfrontrearDEFGHIJ入队后，队列已满，(rear+1) % MaxQSize = front J三、栈和队列2.循环队列类的实现三、栈和队列循环队列的入队操作三、栈和队列循环队列的出队操作3.链队列三、栈和队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front-next = NULLfrontrear三、栈和队列链队列类的实现三、栈和队列链队列的入队操作三、栈和队列链队列入队操作三、栈和队列链队列出队操作三、栈和队列链队列出队操作三、栈和队列3.4.3 队列的应用 习题3（5） 二项式(x+y)n展开式是杨辉三角形三