数据结构（严蔚敏）Chapter 4 Stacks and Queues.pptVIP

Data Structures and Algorithms with Java Chapter 4 Stacks and Queues Overview ① 不同的结构类型 本章所讲的数据结构和算法与前面章节提到的有很大不同，先看看其中的三大区别： 程序员工具 受限访问 更加抽象 程序员工具 数组、链表和树等数据结构，适用于数据库应用中存储数据记录，主要记录那些对应于现实世界的对象和活动的数据，如职员档案、目录和商务数据等等。 --存储对象，常驻内存 ∵便于访问，易于插入、删除和查找特定数据项的操作 栈和队列更多地作为程序员工具，主要作为构思算法的辅助工具，而不是完全的数据存储工具。这些结构的生命周期比那些数据库类型的结构要短得多，在程序操作执行期间被创建，执行某项特殊的任务，任务完成后，被销毁。 受限访问 数组 更加抽象 栈、队列和优先级队列是比数组和其他数据存储结构更为抽象的结构 主要通过接口对栈、队列和优先级队列进行定义，这些接口表明通过它们可以完成的操作，而具体的实现机制对用户来说是不可见的。 如栈的主要机制可以用数组来实现，也可用链表实现。优先级队列的内部实现可以用数组或堆(树)来实现。(第五章ADT-继续讨论如何用一种数据结构实现另外一种数据结构) ② 栈 栈(Stack)是限制在表的一端进行插入和删除运算的线性表 栈只允许访问一个数据项：即最后插入的数据项。移除此数据项之后才能访问倒数第二个数据项，依此类推。 栈的用途： 检验源程序中的小括号、中括号和大括号是否匹配；解析算术表达式； 辅助遍历二叉树节点； 辅助查找图的顶点(迷宫问题)等等 邮政模拟 例 THE POSTAL ANALOGY Terms 栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ JAVA CODE FOR A STACK STACK EXAMPLE 1: REVERSING A WORD First the characters are extracted one by one from the input string and pushed onto the stack. Then they’re popped off the stack and displayed STACK EXAMPLE 2: DELIMITER MATCHING 分隔符匹配程序从字符串中不断地读取字符，每次读入一个字符 如发现是左分隔符，将它压入栈中。 若发现是右分隔符，弹出栈顶的左分隔符，查看是否与当前右分隔符匹配，若不匹配，报错； 分隔符没有被匹配表现为把所有的字符读入后，栈中仍留有分隔符。 每次从字符串中读取一个字符后栈的情况： a{b(c[d]e)f} EFFICIENCY OF STACKS StackX类中实现的栈，数据项的入栈和出栈的时间复杂度都为常数O(1)，即栈操作所耗的时间不依赖于栈中数据项的个数，因此操作时间短，且不需要比较和移动操作 ③ Queues 队列，类似于栈，只是在队列中第一个插入的数据项也应该最先被移除(先进先出,FIFO) Terms Front 队列的表头，即只允许删除的一端。(front) Rear 队列的表尾，即只允许插入的一端(back/rear) EnQueue 向队尾插入元素。(insert) DeQueue 从队头删除元素。(remove) A CIRCULAR QUEUE 为了避免队列空间的浪费(队列不满却不能插入新数据项)，可以让队头队尾的指针绕回到数组开始的位置，即循环队列(有时候也称为”缓冲环”)。 队尾指针回绕，导致队列的队尾下标小于队头下标，思考何时队列恢复初始状态？连续状态？ JAVA CODE FOR A QUEUE EFFICIENCY OF QUEUES 和栈一样，队列中插入数据项和移除数据项的时间复杂度均为O(1). DEQUES 双端队列就是一个两端都是结尾的队列。队列的每一段都可以插入数据项和移除数据项。这些方法可以叫做insertLeft()和insertRight(),以及removeLeft()和removeRight(). 双端队列是一种多用途的数据结构。 双端队列 → 栈 ×insertLeft() removeLeft() 双端队列 → 队列 × inser