4,栈和队列 -1.PDFVIP

4，栈和队列-1 栈和队列的概念 数据的生成，缓存，使用和顺序 栈的实现和问题 Python 的栈实现 队列的实现和问题 Python 的队列实现 栈应用实例 队列应用实例 有哪些信誉好的足球投注网站问题和其他 数据结构和算法（Python 语言版）：栈和队列(1) 裘宗燕，2014-10-30-/1/ 概述 栈 （stack ）和队列 （queue）是两种使用最广泛的数据结构，它们都 是保存数据元素的容器，可以将元素存入其中，或者从中取出元素使用 （查看，或弹出，即在取得元素的同时将其从容器里删除） 容器是一大类具有保存数据作用的数据结构，它们都保证存入的元素可 以在将来取到，而取出并删除的元素不再存在于容器之中 栈和队列主要用于在计算过程中临时性地保存元素 这些元素是前面计算中发现或产生的中间数据，需要在后面使用 如果工作中产生的中间数据暂时无法使用或用不完，就有必要把已 生成出来但当时还不需要或不能用掉的元素暂时保存起来 栈和队列常用于生成和使用之间的缓冲，称为缓冲存储或缓存 栈和队列的操作都比较简单 最重要的就是放入元素和取出元素两个操作 还可能有另外一些辅助操作，如创建，检查，判断空/满等 数据结构和算法（Python 语言版）：栈和队列(1) 裘宗燕，2014-10-30-/2/ 概述 中间数据元素的生成有早有晚，有时间上的先后顺序。在实际应用中， 使用这些元素也可能需要按时间的顺序。最典型的两种顺序如下： 根据数据生成的顺序，后生成并保存的数据先行处理 如做数学题，遇到做不下去，通常是退回一步考虑别的可能性 根据数据生成的先后顺序处理，先生成的数据先处理 如银行办事，先到的应先得到服务，具体等待方式不重要 o 直接排在一个等待队列上 o 拿（顺序）号后等叫号，每次总叫尚未服务的最早来的顾客 在这两种情况下，访问（并可能删除）都按默认的方式确定元素 栈和队列就是支持按这两种顺序使用元素的缓存数据结构 栈和队列存入操作只需要保证元素存入和将来取出的顺序，不需要 记录或保证新存入的元素与容器中已有元素之间的任何关系 数据结构和算法（Python 语言版）：栈和队列(1) 裘宗燕，2014-10-30-/3/ 概述 栈和队列在保证元素存取之间的时间顺序关系方面的特点： 栈是保证缓存元素后进先出 （Last In First Out，LIFO）的结构 队列是保证缓存元素的先进先出 （先存的先用，First In First Out， FIFO）关系的结构 对栈和队列，在任何时候，下次访问或删除的元素都默认地唯一确定。 只有新的存入或删除（弹出）操作可能改变下次的默认元素 栈和队列的特点完全是抽象的逻辑的，对于如何实现（如何实现相应时 间顺序）并没有任何约束，任何能满足要求的技术均可使用 一种很方便的技术是利用元素的排列顺序表示它们的先来后到，也 就是说，可以用线性表作为栈和队列的“实现结构” 例如：把元素进入实现为表的后端插入，这样 o 队列里最老的（下次访问或删除的）元素总是最前面一个元素 o 栈里最年轻的（下次访问或删除的）元素总是最后一个元素 数据结构和算法（Python 语言版）：栈和队列(1) 裘宗燕，2014-10-30-/4/ 概述 栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下： 计算过程分为一些顺序进行的步骤 所执行的步骤中会不断产生一些后面可能需要的中间数据 产生的一些数据不能立即使用，但必须保存起来准备以后使用 需要保存的数据的项数不能事先确定 这种情况下，通常就需要用一个栈或一个队列作为缓存 栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和 操作效率，也是许多算法的设计中非常关键的因