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

4，栈和队列,栈和队列的概念数据的生成，缓存，使用和顺序栈的实现和问题栈应用实例栈与递归，递归和非递归队列的实现和问题队列应用实例搜索问题相关问题,概述,栈（stack）和队列（queue）是两种使用最广泛的数据结构，它们都是保存数据元素的容器，可以将元素存入其中，或者从中取出元素使用（查看，或弹出，即在取得元素的同时将其从容器里删除）容器是一大类能保存数据元素的数据结构，它们都保证存入的元素可以在将来取得，而被删除的元素不再存在于容器之中栈和队列主要用于在计算过程中临时性地保存元素这些元素是前面计算中发现或产生的中间数据，需要在后面使用如果产生的中间数据暂时不用或者用不完，但将来可能要用到，就有必要临时保存起来栈和队列常用于生成和使用之间的缓冲，称为缓冲存储或缓存栈和队列的操作都比较简单最重要的就是存入元素和取出元素两个操作还可能有另外一些辅助操作，如创建，检查，判断空/满等,概述,中间数据的生成有早有晚，时间上有先后。在实际应用中，使用这些元素也可能需要按时间顺序。有两种最典型的顺序如下：按数据生成的顺序，后生成的数据需要先处理按数据生成的先后顺序处理，先生成的数据先处理如去银行办事，先到的应先得到服务，具体等待方式不重要，如直接排在一个等待队列上拿（顺序）号后等叫号，每次叫尚未服务的最早来的顾客在这两种情况下，访问（并可能删除）都按默认方式确定元素栈和队列就是支持按这两种顺序使用元素的缓存数据结构栈和队列存入操作只需要保证元素存入和将来取出的顺序，不记录也不保证新存入元素与容器中已有元素之间的任何关系,概述,栈和队列保证元素存取之间的时间关系，特点是：栈是保证缓存元素后进先出（LastInFirstOut，LIFO）的结构队列是保证缓存元素的先进先出（先存者先用，FirstInFirstOut，FIFO）关系的结构对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。只有新的存入或删除（弹出）操作可能改变下次的默认元素栈和队列的性质完全是抽象的、逻辑的，对实现方式（如何实现相应时间顺序）并没有任何约束，任何能满足要求的技术均可使用最方便的技术是利用元素的排列顺序表示其先来后到关系，也就是说，可以用线性表作为栈和队列的“实现结构”例如：把元素进入实现为表的后端插入，这样最老的元素总是最前面的元素（作为队列下次应访问和删除）最新的元素总是最后一个元素（作为栈下次应访问和删除）,概述,栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下：计算过程分为一些顺序进行的操作步骤执行的操作时会产生一些后面可能需要用的中间数据产生的某些数据无法立即用掉，需要保存起来以备后面使用需要保存的数据的项数不能事先确定这种情况下，通常就需要用一个栈或一个队列作为缓存栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和操作效率，也是许多算法设计中的关键因素由于栈和队列在应用中的重要性，Python的基本功能中包括了对栈的支持（可直接用list），标准库提供了支持队列用途的结构下面分别讨论这两种结构的情况，包括性质和模型；实现和问题；一些应用；一些一般性问题,栈：概念,栈（stack），有的书籍里称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素。在这里没有位置的概念栈保证任何时刻可以访问、删除的元素都是在此之前最后存入的那个元素。因此确定了一种默认的访问顺序栈的基本操作是一个封闭集合（与表不同），通常包括：创建空栈判断栈是否为空（还可能需要判断满），is_empty()向栈中插入（通常称推入/压入，push）一个元素，push(.)从栈中删除（弹出，pop）一个元素，空栈弹出报错，pop()取当前（最新）元素的值（并不删除），top(),栈：特性和基本实现考虑,栈可以实现为（可以看作）只在一端插入和删除的表因此有人（有书籍中）把栈称为后进先出（LIFO）表进行插入或删除操作的一端称为栈顶，另一端称为栈底用线性表技术实现栈时，由于只需要在一端操作，自然应该利用实现最方便，而且能保证两个主要操作的效率最高的那一端采用连续表方式实现，在后端插入删除都是O(1)操作（!）采用链接表方式实现，在前端插入删除都是O(1)操作栈通常都采用这两种技术实现实现栈之前，先定义一个自己的异常类（Python的内部异常是一组类，都是Exception的子类，可以继承已有异常类定义自己的异常类）classStackUnderflow(ValueError):#栈下溢（空栈访问）pass,栈：实现,采用连续表技术实现，也会遇到连续表的各种相关问题用简单连续表，还是采用动态连续表（分离式实现的连续表）？如果用简单连续表，就可能出现栈满的情况采用动态连续表，栈存储区满时可以换一块更大的存储区。这时又会出现置换策略问题，以及分期付款式的O(1)复杂性Pythonlist及其操作实际上提供了一种栈功能，可以作为栈使用建立空栈，对应于创建一个空表，判空栈对应于判空表由于list采用动态连续表技术（分离式实现），作为栈的表不会满压入元素操作应在表尾端进行，对应于lst.append(x)弹出操作也应在尾端进行，无参的lst.pop()默认弹出表尾元素由于采用动态连续表技术，压入操作具有分期付款式的O(1)复杂性，其他操作都是O(1)操作,栈：实现,为了概念清晰、操作名更易理解、排除不符合栈性质的其他操作，应该基于连续表定义一个栈类，用list作为其实现的基础classSStack():#基于顺序表技术实现的栈类def_init_(self):#用list对象_elems存储栈中元素self._elems=#所有栈操作都映射到list操作defis_empty(self):returnself._elems=deftop(self):ifself._elems=:raiseStackUnderflow(inSStack.top()returnself._elems-1defpush(self,elem):self._elems.append(elem)defpop(self):ifself._elems=:raiseStackUnderflow(inSStack.pop()returnself._elems.pop(),栈：链接表实现,采用链接技术，可以借用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程序里的括号存在不同的括号：如圆括号、方括号和花括号每种括号都有开括号和闭括号，括号括起的片段可能相互嵌套，各种括号需要分别正确嵌套配对配对的原则遇到的闭括号应该匹配此前遇到的最近的尚未匹配的对应开括号由于多种/多次/可能嵌套，为检查配对，遇到的开括号必须保存由于括号可能嵌套，需要逐对匹配，闭括号应与前面最近的尚未有匹配的开括号匹配，后面括号应与更前面次近的括号匹配可以删除匹配的括号，为后面的匹配做好准备后遇到并保存的开括号应该先删除，这就是后进先出，而且要按照出现顺序，显然应该/可以用一个栈保存开括号,简单应用：括号配对问题,问题处理的线索已经清楚了：顺序检查被处理正文（是一个字符串）里的一个个字符跳过无关字符遇到开括号时将其压入一个栈遇到闭括号时弹出栈顶元素与之匹配括号匹配则继续遇到不匹配时检查以失败结束下面考虑定义一个函数完成这个检查，其中先定义一些检查中需要使用的数据和变量,简单应用：括号配对问题,函数定义（很简单）：defcheck_pares(text):pares=()open_pares=(opposite=):(,:,:#表示配对关系的字典defparetheses(text):.#括号生成器，定义见后st=SStack()forpr,iinparetheses(text):#对text里各括号和位置迭代ifprinopen_pares:#开括号，压进栈并继续st.push(pr)elifst.pop()!=oppositepr:#不匹配就是失败，退出print(Unmatchingisfoundat,i,for,pr)returnFalse#else是一次括号配对成功，什么也不做，继续print(Allparethesesarecorrectlymatched.)returnTrue,简单应用：括号配对问题,括号生成器定义为（局部）函数defparetheses(text):i,text_len=0,len(text)whileTrue:whilei=text_len:returnyieldtexti,ii+=1生成器（回忆一下）：用yield语句产生结果可以用在需要迭代器的地方函数结束导致迭代结束,简单应用：括号配对问题,总结：这个函数利用了栈的性质，这是关键函数开始先准备好处理中需要用的数据。虽然各种数据在程序里都只有一处使用，但这样定义使程序清晰易读，更易修改利用了Python丰富的数据结构和操作，如in，notin和字典等定义理一个独立的括号生成器函数，使代码功能清晰。例如，要检查实际Python程序里的括号，还需要考虑跳过程序里的注释和字符串等，修改括号生成规则时只需要修改这个函数请自己考虑和练习,表达式的表示、计算和变换,小学生就开始写表达式，先是算术表达式，后来是代数表达式对二元运算符，通常把它们写在两个运算对象中间，这种写法称为中缀表示，按中缀表示法写出的表达式称为中缀表达式中缀表示很难统一贯彻，一元和多元运算符很难用中缀表示代数表达式里的函数符号通常写在运算对象前面，这种写法称为前缀表示。为界定函数参数的范围，通常用括号将它们括起可见，常见的表达式习惯表示是前缀表示和中缀表示的组合实际上，表达式并不一定采用这种习惯写法可以用纯粹的前缀表示，这样写出的表达式称为前缀表达式还有一种表达式写法称为后缀表示，其中运算符（函数）总写在它们的运算对象之后，这样写出的表达式称为后缀表达式。实际上，后缀表达式特别适合计算机处理前缀表达式也称为波兰表达式（由波兰数学家J.Lukasiewicz于1929提出），后缀表达式也称为逆波兰表达式,表达式的表示、计算和变换,首先假设每个运算符有确定的元数（运算对象个数），而且元数唯一写表达式时，最重要的问题是准确描述计算的顺序中缀表达式的一个重要缺点是不能直接表示运算的顺序，需要借助于辅助性约定和/或辅助描述机制，实际情况：必须引进括号机制，表示括号里的运算先做（显式描述计算顺序）为减少总写括号的麻烦，还引进优先级概念，规定运算符的优先级（或优先级关系），高优先级运算符的结合性强，运算符相邻出现时，优先级高的运算先做还需规定相同优先级的运算符相邻出现时的计算顺序（结合性）与之对应的情况：在上述基本假定下，前缀表达式和后缀表达式都不需要括号，也不需要优先级，就能自然地描述任意复杂的计算顺序可见，中缀表达式的表达能力最弱中缀表达式增加了括号后，几种表达方式具有同等表达能力,表达式的表示、计算和变换,对比几种不同表达式形式。下面三个算术表达式等价中缀：(3-5)*(6+17*4)/3前缀：/*-35+6*1743后缀：35-6174*+*3/三个表达式描述的是同一个计算过程下面先考虑后缀表达式的求值，假定被处理的是算术表达式其中的运算对象是浮点数形式表示的数运算符只有+、-、*、/，都是二元运算符后面还要讨论不同表达式形式的转换（考虑中缀形式到后缀形式）研究相应的转换算法，以及中缀表达式的求值,后缀表达式的计算,考虑计算过程，设有函数nextItem()得到下一个运算对象或运算符：遇到运算对象，需要记录以备后面使用遇到运算符（或函数名），需要根据其元数取得前面最近遇到的几个运算对象或已做运算得到的结果，实施计算并记录结果问题：应该用什么结构记录信息？看看计算过程的性质：需要记录的是已经掌握但还不能立即使用的中间结果遇到运算符时，要用的是此前最后记录的几个结果（根据元数）显然应该用栈作为缓存结构上面分析也说明了算法的基本结构实际程序就是把这个算法用Python的语言写出来,后缀表达式的计算,先考虑算法的框架假定st是栈，算法核心是个循环（逐个处理运算符或运算对象）：while还有输入:x=nextItem()ifnotis_operator(x):st.push(float(x)else:a=st.pop()#第二个运算对象b=st.pop()#第一个运算对象.#根据运算符x对a和b计算.#计算结果压入栈这里写了几个辅助过程，其具体实现依赖于一些情况被求值的表达式从哪里获得表达式里的元素如何表示（下面假定用字符串）,后缀表达式的计算,假定从函数参数获得输入参数是一个字符串，内容是需要求值的后缀表达式表达式中不同的项之间有空格分隔为程序清晰，定义了一个包装过程：#定义一个函数把表示表达式的字符串转化为项的表defsuffix_exp_evaluator(line):returnsuf_exp_evaluator(line.split()定义一个扩充的栈类，增加一个检查栈深度的方法：classESStack(SStack):defdepth(self):returnlen(self.elems)下面是核心求值过程的定义（与前面设计相比有一些小修改）由于函数的输入就是一个项的表,后缀表达式的计算,defsuf_exp_evaluator(exp):operators=+-*/st=ESStack()#扩充功能的栈，可用depth()检查栈内元素个数forxinexp:ifnotxinoperators:st.push(float(x);continue#不能转换时自动引发异常ifst.depth()=priorityx):exp.append(st.pop()st.push(x)#当前运算符进栈,中缀表达式到后缀表达式的转换,whilenotst.is_empty():#处理栈里剩下的运算符ifst.top()=(:#如果还有左括号，就是不配对raiseSyntaxError(Extra(.)exp.append(st.pop()returnexp为测试方便，定义一个专门用于测试的辅助函数：deftest_trans_infix_suffix(s):print(s)print(trans_infix_suffix(s)print(Value:,suf_exp_evaluator(trans_infix_suffix(s),中缀表达式到后缀表达式的转换,把生成表达式里各个项的工作定义为一个生成器：deftokens(line):i,llen=0,len(line)whileillen:iflinei.isspace():i+=1;continueiflineiininfix_operators:#遇到运算符yieldlinei;i+=1;continuej=i+1#处理运算对象while(jllenandnotlinej.isspace()andlinejnotininfix_operators):if(linej=eorlinej=E)#处理负指数andj+10:st.push(n)n-=1whilenotst.is_empty():res*=st.pop()returnres这里并没有严格地按规矩翻译，只保存了必要的信息。例如这里的计算结果没有进栈,递归过程和非递归过程,前面先给求阶乘的递归算法，而后给出了一个使用栈保存搜索的中间信息的非递归算法可以证明：任何递归定义的函数（程序），都可以通过引入一个栈保存中间结果，翻译为一个非递归的过程。与此对应，任何一个包含循环的程序都可翻译为一个不包含循环的递归程序这两个翻译过程都可计算，可以写出完成这两种翻译的程序，把任何递归定义的函数翻译到完成同样工作的非递归的函数，或者把任何包含循环的程序翻译为不包含循环的递归程序阶乘的递归算法里只有一个递归调用，很容易翻译成非递归算法前面的翻译并没有采用通用的方法，而是根据自己对函数执行过程的分析，尽可能地做了些简化。这样写出的程序比较简单有关自动翻译的算法，这里不再介绍有兴趣的同学可以参考张乃孝老师的算法与数据结构，高教出版社2002年版，4.3.1节，或北大信科学院的数据结构幻灯片,栈的应用：简单背包问题,问题描述：背包里可放入重量为W的物品，现有n件物品的集合S，其中物品的重量分别为w1,w2,wn。问能否从中选出若干件物品的重量之和正好是W。若存在则称此背包问题有解，否则无解可以要求当存在解时给出一个解许多实际的货物安排，装车，剪裁材料等，都与这一问题类似问题的表示：设W0，n0。用knap(W,n)表示n件物品相对于W的背包问题，如果它有解如果不选wn，则knap(W,n-1)的解就是knap(W,n)的解如果选wn，则knap(W-wn,n-1)的解就是knap(W,n)的解问题有递归性质，n件物品的背包问题可归结到n-1件物品的问题可能是对另一个总容量W通过不断归结，最后可以归结到最简单的情况,简单背包问题,背包问题的递归定义：,这里的True表示有解；False表示无解前三种情况可以直接知道有没有解后两种情况都是把原问题归结到规模较小的问题。这样归结下去，最终会达到前三种情况注意：每件物品有且仅有一件，用去了就没有了,简单背包问题,完全根据上面的递归定义，写出的递归函数定义如下：defknap_rec(weight,wlist,n):ifweight=0:returnTrueelifweight0andn1):returnFalseelifknap_rec(weight-wlistn-1,wlist,n-1):print(Item+str(n)+:,wlistn-1)returnTrueelifknap_rec(weight,wlist,n-1):returnTrueelse:returnFalse函数还产生了输出，列出所选的各物品的顺序号和重量,简单背包问题,对背包问题，有关算法里出现了两个递归调用defknap_rec(weight,wlist,n):if.elifknap_rec(weight-wlistn-1,wlist,n-1):print(Item+str(n)+:,wlistn-1);returnTrueelifknap_rec(weight,wlist,n-1):returnTrueelse:.按规范方式翻译得到的非递归函数定义比较长，这里不讨论了有兴趣的同学可以查阅张乃孝老师主编的算法与数据结构，高教出版社，2002版，4.3.1节，或者信息学院的数据结构幻灯片可以自己想想如何写出一个（简单些的）非递归算法（作为自由练习，可以在教学网的课程讨论组交流）在现在的计算机上，函数调用的效率比较高，一般情况下直接采用递归定义的函数就可以满足需要，不必考虑做出非递归的函数定义,队列（queue）,队列（queue），或称为队，也是一种容器可存入数据元素、访问元素、删除元素这里也没有位置的概念。队列保证任何时刻可访问、删除的元素都是在此之前最早存入队列而至今未删除的那个元素队列确定了一种由存储顺序决定的访问顺序队列的基本操作也是一个封闭集合，通常包括：创建空队列判断队列是否为空（还可能需要判断满）将一个元素放入队列（常称为入队，enqueue）从队列中删除（常称为出队，dequeue）一个元素取当前（最老的）元素的值（并不删除）我们也可以为队列建立一个理论模型，从略,队列：特征,队列的特性：保证任何时刻访问或删除的元素的先进先出（FIFO）顺序是一种与“时间”有关的结构队列可看作（可实现为）只在一端插入另一端访问和删除的表有些书籍里把队列称为先进先出（FIFO）表出队操作的一端称为队头入队操作的一端称为队尾,队列的链接表实现,用线性表的技术实现队列，就是利用元素位置的顺序表示入队的先后。先进先出需要在表的两端操作，实现起来比栈麻烦一些首先考虑用链接表的实现，为操作的效率，考虑带表尾指针的链接表这样才能保证入队/出队操作都能在O(1)时间完成如果没有表尾指针，入队就是O(n)操作，不好,队列的顺序表实现,现在考虑用顺序表技术实现队列假设用尾端插入实现enqueue，出队操作应在表的首端进行为维护表中数据的完整性，出队操作取出首元素后，必须把它之后的元素逐个前移，这样得到的是O(n)操作反过来实现：虽然从尾端弹出元素是O(1)操作，但首端插入也是O(n)操作。也出现了O(n)操作，同样很不理想考虑首元素出队后元素不前移，记住新队头位置。这一设计也有问题：反复入队出队，如果元素存储区固定，一定会在某次入队时出现队尾溢出表尾（表满）的情况出现这种溢出时，顺序表前部一般会留下一些空位这是“假溢出”，并不是真的用完了整个元素区如果元素存储区自动增长（如list），首端将留下越来越大的空区。而且这片空区永远也用不到（完全浪费了）,队列的顺序表实现,简单实现方式有问题的示意图（设q是队列对象）：,实现方法不合适！,队列的顺序表实现,人们提出了一种称为“环形队列”的技术，来解决这个问题,实现中的不变关系（不变式）：q.rear是最后元素之后空位的下标q.head是首元素的下标q.head,q.rear)是队列中所有元素（看作按照环形排列）入队时，先存入，后移位,当q.head=q.rear时队列空队列满如何判断？条件不能与队列空判断相同,队列的顺序表实现,入队出队时的下标更新语句q.head=(q.head+1)%q.lenq.rear=(q.rear+1)%q.len保证更新后的下标的值正确,存在其他设计。下面考虑：用head域记录队头元素位置，num记录队中元素个数队尾空位在（q.len是表长）(q.head+q.elnum)%q.len基于这两个变量实现操作，就可以不留空置单元,队列的list实现,可以基于Python的list实现顺序表示的队列最简单的实现方法得到O(1)的enqueue和O(n)的dequeue由于Pythonlist没提供检查元素存储区容量的机制，我们很难利用其自动扩充元素区的机制，但是可以自己做（看下面的做法）首先，队列可能由于空而无法dequeue，自定义一个异常classQueueUnderflow(ValueError):passSQueue类的基本考虑：用SQueue对象的一个list类型的成分_elems存放队列元素用_head和_num记录首元素所在位置的下标和表中元素个数为能判断存储区满以便换一个表，需要记录表的长度，用_len,数据不变式,这里的队列实现是一个比较复杂的问题要考虑一组操作和队列对象的一组成分，其中一些操作的执行可能改变一些对象成分的取值。问题：允许怎样的改变？如果一个操作有错或与其他操作不一致，就会破坏整个对象。可见，所有操作在成分修改方面必须有统一的原则，相互合作为保证对象的完整性，各操作的实现都必须遵循这些些原则为解决这类问题（一个数据结构的操作需相互协调，具有某种统一性），人们提出了“数据不变式”概念，它刻画“什么是一个完好的对象”数据不变式基于对象的成分，描述它们应满足的逻辑约束关系对象的成分取值满足数据不变式，说明这是一个状态正确的对象数据不变式提出了对操作的约束和基本保证：构造对象的操作必须把对象成分设置为满足数据不变式的状态每个操作保证其对于对象成分的修改不打破数据不变式,数据不变式,针对下面实现，考虑的数据不变式是（用非形式的描述方式）：_elems成分引用着队列的元素存储区，是一个list对象，_len是该存储区的有效容量（我们并不知道该list对象的实际大小）_head是队列首元素（当时在队列里的存入最早的那个元素）的下标，_num始终记录着队列中元素的个数队列里的元素在_elems里连续存放，但需要在下标_len存入元素时，操作改在下标0的位置存入在_num=_len时出现的入队列操作将自动扩张存储区下面用一个类实现一种连续表示的队列_init_操作建立空队列，设置对象成分保证上述不变式成立两个修改对象的变动操作都维持不变式的成立，我们将仔细检查有关情况。这样一组操作形成了一套相互协调的实现前面提出过队列的其他设计，同样可以写出有关的数据不变式,队列的list实现,类定义里的几个简单方法：classSQueue():def_init_(self,init_len=8):self._len=init_len#存储区长度self._elems=0*init_len#元素存储self._head=0#表头元素下标self._num=0#元素个数defis_empty(self):returnself._num=0defpeek(self):ifself._num=0:raiseQueueUnderflowreturnself._elemsself._head#（下页继续）,队列的list实现,出队列的方法很简单#注意head更新的计算，defdequeue(self):ifself._num=0:raiseQueueUnderflowe=self._elemsself._headself._head=(self._head+1)%self._lenself._num-=1returne入队列操作比较麻烦需要检查队列存储区是否已满存储区满时需要建一个新的，拷贝已有元素,队列的list实现,入队列方法，defenqueue(self,elem):ifself._num=self._len:self._extend()self._elems(self._head+self._num)%self._len=eself._num+=1def_extend(self):old_len=self._lenself._len*=2new_elems=0*self._lenforiinrange(old_len):new_elemsi=self._elems(self._head+i)%old_lenself._elems,self._head=new_elems,0扩张存储区定义内部过程，使程序更清晰，扩张策略也被局部化。名字加两个下划线是Python内部方法惯用命名法,队列的应用,队列在各种计算机程序和软件里使用广泛，看几个例子计算机可能连着一台打印机，可以把一些文件送去打印打印机速度有限，可能出现这样的情况：它正在打印一个文件的过程中，人们又送去一个或几个文件。对多人共享的网络打印机，很可能出现接到了很多打印任务但不能立即处理的情况打印机管理程序管理着一个缓存打印任务的队列。接到新打印任务时，如果打印机忙，该任务就被放入队列。一旦打印机完成了当前工作，管理程序就查看队列，取出最早的任务送给打印机考虑网络上的一台Web服务器服务器会不断接到来自网络的网页请求，这时它应该设法找到或做出所需要的页面，发送给提出请求的网络客户来自网络的请求在速率上会有很大波动，如果瞬时请求很多，服务器就会把来不及处理的请求放入一个队列。一个处理器（或处理线程）完成当时的工作后，就会到队列里取走一个未处理请求,队列的应用,Windows系统是围绕着“消息”概念和机制构造和活动的（称为是消息驱动的系统），所有应用程序都需要围绕消息构造起来的各种活动（窗口界面操作，各种输入输出，程序活动）都可能/可以产生各种消息，要求某些系统程序或用户程序响应Windows系统维护着一些消息队列，保存接到的各种消息；消息分发机制检查消息里的信息，把它们分发给相应程序；程序在处理消息的过程中又可能生成新的消息在Windows系统里工作的每个程序都有一个隐含的消息队列。程序里有一个消息处理循环，每次循环检查自己的消息队列，如果没有消息就进入等待，有消息就取出来处理计算机里不同处理器或处理进程（线程）之间的通讯也可能需要消息队列作为缓冲（这种方式称为异步通讯）通讯服务软件把发给一个进程的消息放入该进程的消息队列进程需要消息时查看自己的消息队列，根据情况取出处理或等待,队列应用：离散事件模拟,队列的另一种常见应用是做离散事件系统模拟离散事件系统的典型情况被模拟的（真实世界的）系统的行为表现为一些活动，各种活动进行中又可能产生新的活动。这些活动都需要处理，最简单最常见的处理方式是采用“先发生先处理”的工作原则由于事件的产生和处理之间存在着速度上的波动和差异，因此系统里可能存在一些已经在等待处理的活动。模拟这种系统，就需要用队列记录正在等待的序列离散事件系统的实例银行等待服务的顾客、服务席位和服务时间高速公路收费站通道和服务安排大楼电梯系统设计和安排计算机网络中的各种服务系统,队列应用：离散事件模拟,做系统模拟，是希望通过计算机程序的运行模拟真实系统的活动，以理解真实系统运行时的行为，或在未实现系统之前做出一些设计决策在实现这种模拟系统时，一般而言，需要通过调查或设计，选择一批模拟参数（例如，顾客抵达的频度）引入一些随机因素，反映真实世界中的各种非确定性情况（例如，确定顾客到达约为每2分钟一人，正负1分钟，有随机性）用一个或一批队列保存各种待处理活动（例如正等待的顾客）在生成的活动中保存一些反映真实世界情况的信息（例如，顾客到达的时间，接受服务的开始时间，离开的时间等），以便所实现的模拟系统最后能完成一些统计工作，得到有参考价值的模拟结果（例如：平均等待时间等），用以指导系统设计离散系统模拟还常要考虑另外的一些顺序因素，如服务完成的时间等。我们将在后面讨论“优先队列”之后再考虑离散事件模拟系统的实例,应用：迷宫问题,迷宫是一类常见的智力游戏，也是许多实际问题的反映和抽象，例如,在公路网或铁路网上找可行或最优路线，电子地图路径检索，计算机网络的路由检索，情况都与此类似。下面的讨论从具体到一般迷宫问题：给定一个迷宫，包括一个迷宫图，一个入口点和一个出口点设法找到一条从入口到出口的路径搜索从入口到出口的路径的问题具有递归性质：如果当前位置就是出口，问题已经解决如果从当前位置已无路可走，当前的探查失败（下面怎么办？）取一个可行方向前进一步，从那里继续探查通往出口的路径每个具体迷宫是这个问题的一个实例各种具体的迷宫可能具有不同的表面结构，但问题实质都差不多,迷宫问题,现在考虑一种抽象迷宫，它是平面的，形式比较规范在每个可行位置，上/下/左/右四个方向可能有通路，可以移动一步这种迷宫可以直接映射到二维的0/1矩阵，如下图：,迷宫问题,迷宫问题的特点：存在一集可能位置，一些位置相互连通，一步可达一个位置可能连通若干位置，出现向前探查的多种可能（有分支）目标是找到一条路径（而不是找所有的能行路径）为了找到路径，可能需要逐一探查不同的可能分支工作中需要缓存信息：如果当前位置存在多个可能探查方向，由于下步只能探查一个，需要把不能立刻处理的方向记下来，后面可能使用向前搜索也有一些不同方式，可以比较冒进，也可以稳扎稳打如果搜索还没找到出口，有一些可能做法。例如：直到无路可走时才考虑其他选择，换一条没走过的路继续每步都从最早记录的有选择位置向前，检查并保存另一个可达位置无论如何，路径搜索中必须记录（缓存）有关信息，以供后面使用,迷宫问题,实现不同的路径搜索过程，需要用不同缓存结构保存分支点信息用栈保存和提供信息，实现的是回到之前最后选择点继续的过程用队列保存信息，就是总从最早遇到的选择点继续搜索用栈保存信息，实际上是尽可能利用已经走过的路（改变最少）下面先考虑实现这一过程的算法。算法里用一个栈保存分支点信息用队列方式记录信息的可能性后面考虑解决这个问题需要设计一种问题表示形式和一种确定可行方向的方式注意：还要防止出现兜圈子的情况，为此需要记录到过的位置如果不记录试探过的位置，在搜索通路的过程中就有可能重复探查某些局部路径，即使出口是可达的，也永远找不到记录了探查过的位置，在搜索中检查，保证不重复探查任一位置两种记录方式：1,专门保存信息；2,或直接记在“地图”(迷宫图)上,迷宫问题,问题求解中的一项关键工作是选择合适的问题表示。这里采用：一个整数“矩阵”（两层的list）表示迷宫入口和出口都用一对表下标表示（位置）初始时，通路上的点用元素值为0表示，非通路点用1为避免无穷循环，搜索中把检查过的点标记为2（记录方法2）这样，尚未考虑过的通行位置的值是0，否则都是不需要进一步考虑的（或者根本不是通路，或者是已经探查过的位置）,每个位置有四个相邻位置。为正确（且方便）地处理可能前进方向，要确定一种系统的检查方法。我们把一个位置的四邻看作“东南西北”四方位置，按这个顺序逐方向处理对单元(i,j)，其相邻的四个位置的数组元素下标如右图所示,迷宫问题,用一个序对的list表示从任一(i,j)得到其四邻位置应该加的数对：dirs=(0,1),(1,0),(0,-1),(-1,0)对于当前位置(i,j)，顺序加dirs0,dirs1,dirs2,dirs3，就可以得到其东西南北的四个相邻位置这一设计使检查当前位置四邻的工作可以通过一个循环完成先定义两个简单的辅助函数（设pos是形式为(i,j)的序对）：defmark(maze,pos):#给迷宫maze的位置pos标2表示“到过”mazepos0pos1=2defpassable(maze,pos):#检查迷宫maze的位置pos是否可行returnmazepos0pos1=0先考虑用递归方式写出的算法，它比较简单，不需要辅助数据结构如前所述，为支持递归执行，语言系统内部实际上有一个运行栈。采用递归的方式描述迷宫搜索，也就是利用这个运行栈,迷宫的递归求解,前面提出了对迷宫求解问题的递归观点，改写如下：每个时候总有一个当前位置，开始时这个位置是迷宫入口如果当前位置就是出口，问题已解决如果从当前位置已无路可走，当前的探查失败取一个与当前位置相邻的可行位置用同样方式探查，如果从那里有路径通往出口，也就找到了从当前位置到出口的路径递归的迷宫求解算法是上述描述的实现，开始时把入口作为当前位置mark当前位置检查它是否出口，如果是则成功结束逐个检查当前位置的四邻是否可以通到出口（递归）成功时，整个求解也成功失败时放弃这个可能性,迷宫问题,递归实现的主函数如下：deffind_path(maze,start,end):mark(maze,start);ifstart=end:#已到达出口print(start,end=)#输出这个位置returnTrue#成功结束foriinrange(4):#否则按四个方向顺序探查nextp=start0+dirsi0,start1+dirsi1#下一个考虑ifpassable(maze,nextp):#不可行的相邻位置不用考虑iffind_path(maze,nextp,end):#如果从nextp可达出口print(start,end=)#输出这个点returnTrue;#成功结束returnFalse函数按从出口到入口的顺序输出路径上的位置（下标序对）,迷宫问题：回溯法和栈,不用递归技术求解迷宫问题的一种方法称为回溯法，需要用一个栈：前进：如果当前位置存在尚未探查的向前分支，就选定一个这样的分支向前探查。如这里还有其他未探查分支，需记录相关信息找到出口时成功结束，所有可能都已探查但不能成功时失败结束后退（回溯）遇死路（已无向前的未探查分支）时退回最近记录的分支点，检查那里是否还存在未探查分支，如没有就将其删除并继续回溯找到存在未探查分支的位置时将其作为当前位置继续探查由于分支位置的记录和使用/删除具有后进先出性质，应该用栈保存信息。遇到分支点将相关信息压入栈，删除分支点时将有关信息弹出回溯法也是一种重要的算法设计模式，通常总用一个栈作为辅助结构，保存工作中发现的回溯点，以便后面考虑其他可能性时使用,回溯法和栈,可以应用回溯法求解的具体问题可能差别很大，但它们都是从一个出发点开始，设法找到目标（因此也称为搜索）都需要使用一个栈，搜索过程的行为分为向前搜索和向后回溯一种典型的实现方法如下：首先，把出发点放入栈，在栈里保存与搜索有关的信息反复做下面几个操作（条件：栈不空）弹出一项以前保存的信息（当前点）检查从这里出发前进的可能性（下一个探查点）如果可以向前，把从当前点出发的其他可能存入栈里把下一个探查点也入栈注意：如果从当前点已无前进可能，算法将直接转到下一次迭代，弹出更早保存的点（这是回溯）。找到下一探查点就是前进,迷宫问题：回溯法,对迷宫问题，需要从入口出发搜索遇到出口时成功结束遇分支结点时按上面介绍的方式记录信息，继续探查并可能回溯搜索中把哪些位置入栈？存在两种合理的选择：从入口到当前探查位置，途径的所有位置都入栈只在栈里保存上述路径中存在未探查方向的那些位置。这一方式要求在入栈操作前检查所考虑位置的情况，有可能节省空间仔细考虑，可以看到两个情况：把一个存在未探查方向的位置入栈，后来回溯到这里时也可能不再是未探查方向了（该方向在此期间已经检查过了）为在算法最后输出找到的路径，也需要知道路径上所有的位置下面算法采用记录经过所有位置的方式，主要是为了输出结果路径,迷宫问题：回溯法,迷宫问题算法框架（用一个栈记录搜索中需保存的信息）：入口start相关信息（位置和尚未探索方向）入栈;while栈不空:弹出栈顶元素作为当前位置继续搜索while当前位置存在未探查方向:求出下一探查位置nextpifnextp是出口:输出路径并结束ifnextp尚未探查将当前位置和nextp顺序入栈并退出内层循环根据迷宫的表示形式，以及回溯后能继续搜索的需要。需要在栈里保存序对(pos,nxt)，记录分支点位置和在该位置还需要考虑的下一方向分支点位置pos用行、列坐标表示，可以用一个序对在pos的下一探索方向nxt是整数，表示回溯到此时应探查的下一方向。4个方向编码为0、1、2、3（dirs的下标）,迷宫问题：回溯法,defmaze_solver(maze,start,end):ifstart=end:print(start);returnst=SStack()mark(maze,start)st.push(start,0)#入口和方向0的序对入栈whilenotst.is_empty():#走不通时回退pos,nxt=st.pop()#取栈顶及其探查方向foriinrange(nxt,4):#依次检查未探查方向nextp=(pos0+dirsi0,pos1+dirsi1)#算出下一点ifnextp=end:#到达出口,打印路径print_path(end,pos,st)returnifpassable(maze,nextp):#遇到未探查的新位置st.push(pos,i+1)#原位置和下一方向入栈mark(maze,nextp)st.push(nextp,0)#新位置入栈break#退出内层循环，下次迭代将以新栈顶为当前位置继续print(Nopathfound.)#找不到路径,注意，栈里一点之下总是到它的路径上的前一个点。这是搜索中的一个不变性质,迷宫问题和搜索,迷宫问题是一大类问题的代表。这类问题的基本特征是：存在一集可能状态（位置、情况等，状态集合可能很大）例：迷宫问题中的所有可能位置有一个初始状态s0，一个或多个结束状态（或者有结束判断方法）例：迷宫问题中的入口是初始状态，出口表示搜索的结束状态对每个状态s，neighbor(s)表示与s相邻的一组状态（一步可达）例：迷宫中每个位置的相邻位置有一个判断函数valid(s)判断s是否为可行的下一状态前面算法定义里的possible实现这种功能问题是：找出从s0出发到达某个（或全部）结束状态的路径或是从s0出发，设法找到一个或全部解（一个或全部结束状态）这类问题被称为状态空间搜索或者路径搜索,迷宫问题和搜索,从前面情况看，这种问题可以用递归的方法求解，其中用递归的方式向前探查也可以用一个栈保存中间信息，通过回溯法求解可以通过状态空间搜索解决的问题很多，经典的简单实例如：八皇后问题（在国际象棋棋盘安排八个皇后，使之不能相互攻击）骑士周游问题（在国际象棋棋盘上为骑士找到一条路径，使之可以经过棋盘的每个格子恰好一次。骑士走法与中国象棋的马一样，走“日”字）；等等这些可以作为空间搜索问题的练习许多实际应用问题需要通过空间搜索的方式解决，如许多调度、规划、优化问题（如背包问题）数学定理证明（有一些事实和推理规则）,状态空间搜索：栈和队列,一般性认识：对一个需要用计算的方法处理的问题如有全局性系统性的认识，就可能做出一个专门的算法解决问题如果只有对问题空间的局部性认识，无法做出直接求解问题的算法，还是有可能将其转化为一个状态空间搜索问题。搜索法是一种通用问题求解方法（generalproblemsolving）搜索过程进展中的情况：已经探查了从初始状态可达的一些中间状态已经探查的某些中间状态存在着尚未探查的相邻状态显然，对任何从初始状态可达的中间状态，与它相邻的状态也是可达的。因此，从一个中间状态向前探查可能得到新的可达状态若新确定的可达状态是结束状态，就么找到了初始状态到结束状态的路径；否则，新可达状态应加入已探查的中间状态集显然，搜索中需要记录存在未探查邻居的中间状态，以备后面使用,状态空间搜索：栈和队列,要记录存在尚未完全探索后继状态的中间状态，需要用缓存结构。原则上说栈和队列都可用，但结构的选择将对搜索进展方式产生重大影响前面的迷宫算法里用的是栈，栈的特