数据结构与算法：Python语言描述-栈和队列

数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/1/4，栈和队列栈和队列的概念数据的生成，缓存，使用和顺序栈的实现和问题栈应用实例栈与递归，递归和非递归队列的实现和问题队列应用实例搜索问题相关问题数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/2/概述栈（stack）和队列（queue）是两种使用最广泛的数据结构，它们都是保存数据元素的容器，可以将元素存入其中，或者从中取出元素使用（查看，或弹出，即在取得元素的同时将其从容器里删除）容器是一大类能保存数据元素的数据结构，它们都保证存入的元素可以在将来取得，而被删除的元素不再存在于容器之中栈和队列主要用于在计算过程中临时性地保存元素这些元素是前面计算中发现或产生的中间数据，需要在后面使用如果产生的中间数据暂时不用或者用不完，但将来可能要用到，就有必要临时保存起来栈和队列常用于生成和使用之间的缓冲，称为缓冲存储或缓存栈和队列的操作都比较简单最重要的就是存入元素和取出元素两个操作还可能有另外一些辅助操作，如创建，检查，判断空/满等数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/3/概述中间数据的生成有早有晚，时间上有先后。在实际应用中，使用这些元素也可能需要按时间顺序。有两种最典型的顺序如下：按数据生成的顺序，后生成的数据需要先处理按数据生成的先后顺序处理，先生成的数据先处理如去银行办事，先到的应先得到服务，具体等待方式不重要，如o直接排在一个等待队列上o拿（顺序）号后等叫号，每次叫尚未服务的最早来的顾客在这两种情况下，访问（并可能删除）都按默认方式确定元素栈和队列就是支持按这两种顺序使用元素的缓存数据结构栈和队列存入操作只需要保证元素存入和将来取出的顺序，不记录也不保证新存入元素与容器中已有元素之间的任何关系数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/4/概述栈和队列保证元素存取之间的时间关系，特点是：栈是保证缓存元素后进先出（LastInFirstOut，LIFO）的结构队列是保证缓存元素的先进先出（先存者先用，FirstInFirstOut，FIFO）关系的结构对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。只有新的存入或删除（弹出）操作可能改变下次的默认元素栈和队列的性质完全是抽象的、逻辑的，对实现方式（如何实现相应时间顺序）并没有任何约束，任何能满足要求的技术均可使用最方便的技术是利用元素的排列顺序表示其先来后到关系，也就是说，可以用线性表作为栈和队列的“实现结构”例如：把元素进入实现为表的后端插入，这样o最老的元素总是最前面的元素（作为队列下次应访问和删除）o最新的元素总是最后一个元素（作为栈下次应访问和删除）数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/5/概述栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下：计算过程分为一些顺序进行的操作步骤执行的操作时会产生一些后面可能需要用的中间数据产生的某些数据无法立即用掉，需要保存起来以备后面使用需要保存的数据的项数不能事先确定这种情况下，通常就需要用一个栈或一个队列作为缓存栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和操作效率，也是许多算法设计中的关键因素由于栈和队列在应用中的重要性，Python的基本功能中包括了对栈的支持（可直接用list），标准库提供了支持队列用途的结构下面分别讨论这两种结构的情况，包括性质和模型；实现和问题；一些应用；一些一般性问题数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/6/栈：概念栈（stack），有的书籍里称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素。在这里没有位置的概念栈保证任何时刻可以访问、删除的元素都是在此之前最后存入的那个元素。因此确定了一种默认的访问顺序栈的基本操作是一个封闭集合（与表不同），通常包括：创建空栈判断栈是否为空（还可能需要判断满），is_empty()向栈中插入（通常称推入/压入，push）一个元素，push(...)从栈中删除（弹出，pop）一个元素，空栈弹出报错，pop()取当前（最新）元素的值（并不删除），top()数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/7/栈：特性和基本实现考虑栈可以实现为（可以看作）只在一端插入和删除的表因此有人（有书籍中）把栈称为后进先出（LIFO）表进行插入或删除操作的一端称为栈顶，另一端称为栈底用线性表技术实现栈时，由于只需要在一端操作，自然应该利用实现最方便，而且能保证两个主要操作的效率最高的那一端采用连续表方式实现，在后端插入删除都是O(1)操作（!!!）采用链接表方式实现，在前端插入删除都是O(1)操作栈通常都采用这两种技术实现实现栈之前，先定义一个自己的异常类（Python的内部异常是一组类，都是Exception的子类，可以继承已有异常类定义自己的异常类）classStackUnderflow(ValueError):#栈下溢（空栈访问）pass数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/8/栈：实现采用连续表技术实现，也会遇到连续表的各种相关问题用简单连续表，还是采用动态连续表（分离式实现的连续表）？如果用简单连续表，就可能出现栈满的情况采用动态连续表，栈存储区满时可以换一块更大的存储区。这时又会出现置换策略问题，以及分期付款式的O(1)复杂性Pythonlist及其操作实际上提供了一种栈功能，可以作为栈使用建立空栈，对应于创建一个空表[]，判空栈对应于判空表由于list采用动态连续表技术（分离式实现），作为栈的表不会满压入元素操作应在表尾端进行，对应于lst.append(x)弹出操作也应在尾端进行，无参的lst.pop()默认弹出表尾元素由于采用动态连续表技术，压入操作具有分期付款式的O(1)复杂性，其他操作都是O(1)操作数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/9/栈：实现为了概念清晰、操作名更易理解、排除不符合栈性质的其他操作，应该基于连续表定义一个栈类，用list作为其实现的基础classSStack():#基于顺序表技术实现的栈类def__init__(self):#用list对象_elems存储栈中元素self._elems=[]#所有栈操作都映射到list操作defis_empty(self):returnself._elems==[]deftop(self):ifself._elems==[]:raiseStackUnderflow(inSStack.top())returnself._elems[-1]defpush(self,elem):self._elems.append(elem)defpop(self):ifself._elems==[]:raiseStackUnderflow(inSStack.pop())returnself._elems.pop()数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/10/栈：链接表实现采用链接技术，可以借用LNode类实现一个链接栈：classLStack():#基于链接表技术实现的栈类，用LNode作为结点def__init__(self):self._top=Nonedefis_empty(self):returnself._topisNonedeftop(self):ifself._topisNone:raiseStackUnderflow(inLStack.top())returnself._top.elemdefpush(self,elem):self._top=LNode(elem,self._top)defpop(self):ifself._topisNone:raiseStackUnderflow(inLStack.pop())p=self._topself._top=p.nextreturnp.elem数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/11/栈的应用栈是算法和程序里最常用的辅助结构，基本用途基于两方面：用栈可以很方便地保存和取用信息，因此常作为算法或程序里的辅助存储结构，临时保存信息，供后面的操作使用利用栈后进先出的特点，可以得到特定的存储和取用顺序许多实际运用结合了这两方面的特性作为最简单的应用实例，栈可用于颠倒一组元素的顺序将一组元素依次全部存入后取出，就能得到反序的序列通过不同的存入取出操作序列，可以得到不同的元素序列。但请注意，这种做法不能得到任意的排列，结果序列有一定的规律性下面介绍栈的若干典型应用有些比较具体，是特殊的应用有些实例代表一大类应用，更具典型性数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/12/简单应用：括号配对问题在许多正文中都有括号，特别是在表示程序、数学表达式的正文片段里。括号有正确配对问题。作为例子，考虑Python程序里的括号存在不同的括号：如圆括号、方括号和花括号每种括号都有开括号和闭括号，括号括起的片段可能相互嵌套，各种括号需要分别正确嵌套配对配对的原则遇到的闭括号应该匹配此前遇到的最近的尚未匹配的对应开括号由于多种/多次/可能嵌套，为检查配对，遇到的开括号必须保存由于括号可能嵌套，需要逐对匹配，闭括号应与前面最近的尚未有匹配的开括号匹配，后面括号应与更前面次近的括号匹配可以删除匹配的括号，为后面的匹配做好准备后遇到并保存的开括号应该先删除，这就是后进先出，而且要按照出现顺序，显然应该/可以用一个栈保存开括号数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/13/简单应用：括号配对问题问题处理的线索已经清楚了：顺序检查被处理正文（是一个字符串）里的一个个字符跳过无关字符遇到开括号时将其压入一个栈遇到闭括号时弹出栈顶元素与之匹配括号匹配则继续遇到不匹配时检查以失败结束下面考虑定义一个函数完成这个检查，其中先定义一些检查中需要使用的数据和变量数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/14/简单应用：括号配对问题函数定义（很简单）：defcheck_pares(text):pares=()[]{}open_pares=([{opposite={):(,]:[,}:{}#表示配对关系的字典defparetheses(text):...#括号生成器，定义见后st=SStack()forpr,iinparetheses(text):#对text里各括号和位置迭代ifprinopen_pares:#开括号，压进栈并继续st.push(pr)elifst.pop()!=opposite[pr]:#不匹配就是失败，退出print(Unmatchingisfoundat,i,for,pr)returnFalse#else是一次括号配对成功，什么也不做，继续print(Allparethesesarecorrectlymatched.)returnTrue数据结构和算法（Python语言版）：栈和队列(1)裘宗燕，2020/6/27-/15/简单应用：括号配对问题括号生成器定义为（局部）函数defparetheses(text):i,text_len=0,len(text)whileTrue:whileitext_lenandtext[i]notinpares:i+=1ifi=text_len:returnyieldtext[i],ii+=1生成器（回忆一下