数据结构与算法Python语言描述教学课件 DS5-stack-queue.ppt

《数据结构与算法Python语言描述教学课件 DS5-stack-queue.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4，栈和队列栈和队列的概念数据的生成，缓存，使用和顺序栈的实现和问题栈应用实例栈与递归，递归和非递归队列的实现和问题队列应用实例搜索问题相关问题概述栈（stack）和队列（queue）是两种使用最广泛的数据结构，它们都是保存数据元素的容器，可以将元素存入其中，或者从中取出元素使用（查看，或弹出，即在取得元素的同时将其从容器里删除）容器是一大类能保存数据元素的数据结构，它们都保证存入的元素可以在将来取得，而被删除的元素不再存在于容器之中栈和队列主要用于在计算过程中临时性地保存元素这些元素是前面计算中发现或产生的中间数据，需要在后面使用如果产生的中

2、间数据暂时不用或者用不完，但将来可能要用到，就有必要临时保存起来栈和队列常用于生成和使用之间的缓冲，称为缓冲存储或缓存栈和队列的操作都比较简单最重要的就是存入元素和取出元素两个操作还可能有另外一些辅助操作，如创建，检查，判断空/满等概述中间数据的生成有早有晚，时间上有先后。在实际应用中，使用这些元素也可能需要按时间顺序。有两种最典型的顺序如下：按数据生成的顺序，后生成的数据需要先处理按数据生成的先后顺序处理，先生成的数据先处理如去银行办事，先到的应先得到服务，具体等待方式不重要，如直接排在一个等待队列上拿（顺序）号后等叫号，每次叫尚未服务的最早

3、来的顾客在这两种情况下，访问（并可能删除）都按默认方式确定元素栈和队列就是支持按这两种顺序使用元素的缓存数据结构栈和队列存入操作只需要保证元素存入和将来取出的顺序，不记录也不保证新存入元素与容器中已有元素之间的任何关系概述栈和队列保证元素存取之间的时间关系，特点是：栈是保证缓存元素后进先出（LastInFirstOut，LIFO）的结构队列是保证缓存元素的先进先出（先存者先用，FirstInFirstOut，FIFO）关系的结构对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。只有新的存入或删除（弹出）操作可能改变下次的默认元素栈和

4、队列的性质完全是抽象的、逻辑的，对实现方式（如何实现相应时间顺序）并没有任何约束，任何能满足要求的技术均可使用最方便的技术是利用元素的排列顺序表示其先来后到关系，也就是说，可以用线性表作为栈和队列的“实现结构”例如：把元素进入实现为表的后端插入，这样最老的元素总是最前面的元素（作为队列下次应访问和删除）最新的元素总是最后一个元素（作为栈下次应访问和删除）概述栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下：计算过程分为一些顺序进行的操作步骤执行的操作时会产生一些后面可能需要用的中间数据产生的某些数据无法立即用掉，需要保存起来以备后面使

5、用需要保存的数据的项数不能事先确定这种情况下，通常就需要用一个栈或一个队列作为缓存栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和操作效率，也是许多算法设计中的关键因素由于栈和队列在应用中的重要性，Python的基本功能中包括了对栈的支持（可直接用list），标准库提供了支持队列用途的结构下面分别讨论这两种结构的情况，包括性质和模型；实现和问题；一些应用；一些一般性问题栈：概念栈（stack），有的书籍里称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素。在这里没有位置的概念栈保证任何时刻可以访问、删除的元素都是在此之前最后

6、存入的那个元素。因此确定了一种默认的访问顺序栈的基本操作是一个封闭集合（与表不同），通常包括：创建空栈判断栈是否为空（还可能需要判断满），is_empty()向栈中插入（通常称推入/压入，push）一个元素，push(...)从栈中删除（弹出，pop）一个元素，空栈弹出报错，pop()取当前（最新）元素的值（并不删除），top()栈：特性和基本实现考虑栈可以实现为（可以看作）只在一端插入和删除的表因此有人（有书籍中）把栈称为后进先出（LIFO）表进行插入或删除操作的一端称为栈顶，另一端称为栈底用线性表技术实现栈时，由于只需要在一端操作，自然应该

7、利用实现最方便，而且能保证两个主要操作的效率最高的那一端采用连续表方式实现，在后端插入删除都是O(1)操作（!!!）采用链接表方式实现，在前端插入删除都是O(1)操作栈通常都采用这两种技术实现实现栈之前，先定义一个自己的异常类（Python的内部异常是一组类，都是Exception的子类，可以继承已有异常类定义自己的异常类）classStackUnderflow(ValueError):#栈下溢（空栈访问）pass栈：实现采用连续表技术实现，也会遇到连续表的各种相关问题用简单连续表，还是采用动态连续表（分离式实现的连续表）？如果用简单连续表，

8、就可能出现栈满的情况采用动态连续表，栈存储区满时可以换一块更大的存储区。这时又会出现置换策略问题，以及分期付款式的O(1)复杂性Pythonlist及