栈和队列

　　容器数据结构是指一些包含了若干个其他相同或不同的数据结构的数据结构，被包含的这些每一个独立的数据结构都被称为一个元素，在一个容器中的元素往往支持相同的操作，具有类似的性质。之前说到过的线性表其实就是一种容器数据结构，本文中介绍的两种最常用的容器数据结构是栈和队列。

         从功能上看，栈和队列大多用于计算过程中保存临时数据，这些数据是在计算过程中发现或产生的。在而后的计算中可能会用到这些数据。如果这些数据是固定的个数以及大小的话，可以构建几个变量来储存它们，但是如果这些数据不确定的话，就需要一种规划更好的数据结构来存储它们，这就是栈和队列。从功能这个角度看，栈和队列也是常见的缓冲存储结构。

         反过来，一个缓冲存储结构的话，肯定有规定好的存取信息的方式。比如后进先出（LIFO）和先进先出（FIFO）。栈采取的是前者而队列采取的是后者的方式。从元素操作的层面来看，栈和队列的性质完全是抽象且逻辑的，但是具体的实现方式考虑到实现的复杂度和自然性，一般还是选用线性表来实现。

栈

         正如前面提到的，栈中存储的元素之间是没有特定关系，互相独立的。决定栈对元素操作和识别的只是元素存入栈的时间顺序。栈的基本性质保证了，在任何时刻访问栈，删除的元素都是在此之前最后存入栈的那个元素。考虑到一些常用的操作，可以给出下面这样一个抽象类型作为栈的描述：

ADT Stack:         Stack(self)         #创建空栈         is_empty()        #判断是否为空栈         push(self,elem)         #将一个新元素压入栈中         pop(self)            #删除栈中压入的最后一个元素，并将其返回         top(self)            #取得栈里最后压入的元素，但不删除

         有时候考虑到栈有限的存储空间还可以加上一些其他的函数比如判断栈是否满了。一个栈频繁地进行压入，删除操作的一端被称为栈顶，另一端则为栈底，就像一摞碗，经常取用的碗总是那几个最上面的。根据之前对线性表的分析可以看出，当用顺序表来实现一个栈的时候，由于后端插入和删除都是O(1)的操作，所以表末比较适合做栈顶。另一方面，链接表的前端插入和删除都是O(1)操作，所以表头可以作为栈顶。

■  用list来实现栈

         方便地来考虑的话，可以用python中的list来实现一个栈，但是list支持很多栈并不存在的操作，比如list还可以在任意位置删除元素。如果直接拿list作为栈使用的话无疑会在安全性上带来一些缺陷。相应的解决办法就是创建一个类，把一个list包装在这个类里面且对外部不开放，这样就可以避免使用者调用一些超越栈定义的一些操作。比如下面这样一个类：

class SStack():    #注意，并不是继承list这个类，因为我们不是想要扩展list的功能，相反是要限制一部分list的功能    def __init__(self):        self._elem = []    #创建空栈        def is_empty(self):        return self._elem == []    def top(self):        if self._elem == []:            raise StackUnderflowException("in SStack.top()")    #自定义了一个异常，用来表示访问空栈时引发的错误        return self._elem[-1]    def push(self,elem):        self._elem.append(elem)    def pop(self):        if self._elem == []:            raise StackUnderflowException("in SStack.pop()")        return self._elem.pop()

         *用链接表来实现栈也是类似的，不再详细写了。需要注意的仅仅是在插入删除元素时应该在表头操作且应该注意链表指向下一个节点部分的变化

■  应用：括号匹配问题

这个问题在前面的笔记中应该有提到过，问题的描述就是在一串字符串中检查括号匹配的合法性。大中小括号可以同时存在且互相嵌套，但是不允许有不配对或者配对不正确的括号存在比如”[](”或者”{([)]}”都是不合法的。

利用栈来解决这个问题的思路就是从开头开始扫描字符串，碰到左括号就压入栈，碰到右括号就拿它和当前栈顶的括号比较，如果匹配的话那么就把栈顶的删除之后继续向右扫描字串。下面是一个检查括号字符串合法性的函数

def check_brack(mat):    if mat is ‘‘:        return True    stack = SStack()    match_dict = {‘)‘:‘(‘,‘]‘:‘[‘,‘}‘:‘{‘}    for c in mat:        if c not in "()[]{}":            continue        if c in "([{":            stack.push(c)        elif c in match_dict:            if stack.pop() is match_dict[c]:                continue            else:                return Falsereturn True

书上面采用了把扫描字符串单独做成一个闭包函数生成器，来逐个生成括号同时还能给出发生错误的位置信息，这里就不具体展开了。

■  应用：自然算式的计算

书上首先提到了一个概念，即后缀算术表达式和中缀算术表达式的区别。我们从小学开始学的都是中缀算术表达式，即把四则运算的算术符号放在算术对象的中间比如”2 + 3”。但是实际上还存在前缀和后缀算术表达式，比如”2 3 +”这就是后缀算术表达式。

相比于传统的中缀，后缀表达式的优势在于不需要括号以及算符优先级之类的辅助概念。（我想了一下，中缀式需要括号和优先级根本原因在于运算对象前后都有运算符，结合情况不清楚，但是后缀的话，只要关注运算对象后面的运算符即可。但是这么做的代价就是当没有空格的时候后缀式没有办法识别运算对象的界限。比如11+12很清楚，但是1112+就不知道是11+12还是111+2了。）运用了栈之后，后缀表达式更加适应计算机的计算，或者说计算机处理自然算式时，还是处理后缀算术式最方便。

比如(3 + 4) * (6 + 4 * 7) / 3这个式子，转化为后缀表达式之后就变成了 3 4 + 6 4 7 * + * 3 /。运用栈在求解时只要扫描式子，碰到运算对象就入栈，碰到运算符就把当前栈顶两个（因为这里的四个运算符都是二元运算符）对象取出，进行相应运算，获得结果再放入栈顶，直到扫描到末尾。

• 中缀表达式到后缀表达式的转换

基本思想还是扫描中缀表达式，然后将其输出成一个后缀表达式。在扫描时碰到计算对象可以直接输出，碰到运算符就入栈然后待其后面的运算对象全部输出完毕后再输出。但是考虑到中缀和后缀的不同，有几点必须要考虑。

首先，中缀运算符具有优先级的设定，所以扫描到运算符时有必要先和当前栈顶比较，如果优先级是当前栈顶较高的话那么输出时应该先输出栈顶将扫描到的入栈，否则反之。

其次，对于括号的处理。可以把它视作一种运算符，其优先级低于加减。扫描到左括号时入栈，栈中有了一个左括号标记表明在此之后的所有运算都属于括号内的。扫描到右括号的时候就反向处理当前栈中所有存留的运算符直到左括号。

再次，扫描完整个中缀式之后栈有可能还存在运算符，此时后缀表达式尚未完成，应该把这些运算符再输出。

def trans_infix_suffix(line):    st = SStack()    exp = []    priority = {"(":1,"+":3,"-":3,"*":5,"/":5}        for x in tokens(line):  #tokens是将中缀式扫描后获得的元素，如数字，运算符输出的生成器。这里没具体写出        if x not in ‘+-*/()‘:            exp.append(x)        elif x == ‘(‘ or st.is_empty():            exp.append(x)        elif x == ‘)‘:            while not st.top() != ‘(‘ and not st.is_empty():                exp.append(st.pop())            if st.is_empty():   #没有左括号的情况                raise StackUnderflowException            st.pop()        else:            while not st.is_empty() and priority[x] <= priority[st.top()]:  #优先级相等的情况应该算在这里面，因为优先级相等时看的就是写出来的顺序。而后写者转换为后缀时应该先输出                exp.append(st.pop())            st.push(x)            while not st.is_empty():        if st.top() == ‘(‘:            raise Exception("Extra left-bracket")        else:            exp.append(st.pop())                return exp

         有了这样一个转换函数之后，就可以自己来做python的eval函数做的一部分事情了。也就是说把传统的中缀式转化成后缀式，然后再把后缀式求值。当然这仅仅限于简单的四则运算。

如果想进一步优化这个操作，可以结合中缀式转换和后缀式求值的操作。具体来说可能需要在程序中额外引进一个保存数的栈，然后把上面的exp.append()换成相应的求值操作。详细的程序就不写了。

■  关于递归和栈

接触过编程的人应该都知道递归，就是函数自己调用自己的用法。其实仔细想想递归的过程会发现和栈有很大关系，递归进入每一层时都会保存当前层调用时函数的一些局部信息，当递归完成了最底层处理开始返回的时候这些信息就可以拿出来用，然后一层层向上返回了。如果把这些信息都存储在一个地方的话，那么这个地方无疑是一个栈（因为信息都是后进先出的）。这个栈被称为函数的运行栈。

其实递归只是一个比较特殊的情况，事实上所有函数之间互相调用时都会涉及到这个栈的问题。比如f()函数体中调用了g()而g()函数体中又调用了h()，此时f函数体中的一些局部信息先入栈，然后是g，最后才是h。各个函数调用完成开始删除信息时是先删h再是g再是f。

递归和非递归之间一定可以互相转化，最简单的一个转化方法就是手动控制一个栈数据类型来手动充入信息再手动使用信息。比如把一段递归求阶乘的程序改造成非递归的：

def fact(n):    if n == 0:        return 1    else:        return n*fact(n-1)    #每一层调用，当前层的n是多少被保存进栈中def fact_nonrec(n):    res = 1    st = SStack()    while n > 0:        st.push(n)    #手动给栈充入数据        n -= 1    while not st.is_empty():        res *= st.pop()    #手动从栈中取出数据    return res

但是碰到比较复杂的递归情况的话，那么改造会很复杂，通常的做法是领会递归的精神之后再按照自己的理解转化为非递归的。

• 应用：递归于背包问题

背包问题的描述是，一个背包中可以放入重weight的东西，现在有n件物品分别为w0,w1…wn-1，问可否从这n件物品中取出若干件刚好装满背包？当然这是个最简单的背包问题，实际上还有很多复杂的条件设定比如不是n件而是n类物品，或者要求所有解而非单个解等。这里只说明最简单的情况。

     问题的分析是这样的，一个背包问题knap(weight,n)可以分解成两个小问题。

1. 如果故意不选最后一件wn-1，如此knap(weight,n)的解就是knap(weight,n-1)的解，求后者即可
2. 如果选择了最后一件，如此knap(weight,n)的解就是knap(weight-wn-1,n-1)的解加上wn-1这件物品

　　总的来说，两个子问题，一个针对相同重量但是物品个数减一，另一个则是减少了重量且物品个数减一。只要某个子问题有解，原问题就有解。

　　*需要注意的一点，n是指共有n件物品，并不是说一定要拿n件物品。一开始会错意了导致很久没理解程序

程序实现：

def knap_rec(weight,wlist,n):    if weight == 0:    #刚好装满        return True    if weight < 0 or (weight > 0 and n < 1):    #重量爆表或者物品取完但是还没装满        return False    if knap_rec(weight-wlist[n-1],wlist[:-1],n-1):    #取了最后一个物品        print "Item {0}:{1}".format(str(n),wlist[n-1])    #记录取了第几个物品，重量多少        return True    if knap_rec(weight,wlist[:-1],n-1):    #不取最后一个物品，求knap(weight,n-1)问题        return True    else:        return False

 队列

　　狭义上来说，队列就是指FIFO队列（事实上在Python中，LIFO的栈也被视作一种队列而整合进了Queue这个模块中）。队列支持的操作和性质与栈有很大的相似性，不过由于习惯问题，这些操作的名字和栈的操作的名字不尽相同。一个典型的队列可以有如下的抽象结构：

ADT Queue:    Queue(self)  #创建空队列    is_empty(self)  #判空操作    enqueue(self,elem)  #向队尾添加一个新元素，类似append    dequeue(self)  #删除队首元素并将其返回，类似pop    peek(self)  #查看当前队首元素，不删除

　　与栈不同，队列通常要求对结构两端都进行操作。这样一来，就使得合理的实现方式变少了。比较常见的队列的实现方式是链接表，而且是之前说过的带有尾指针的链接表。这样可以让队列首尾的操作都可以高效地进行。另外，优化得比较好的高级数据结构比如python中的list类型就可以比较好地实现一个队列。介于python中已经有现成的队列模型了就不多说了。

　　队列应用的场景非常多，比如打印机安排打印任务，服务器处理请求时，windows系统的消息队列等等。

■　　迷宫问题（虽然不一定跟队列有关。。放在这里了）

　　迷宫问题，顾名思义就是解决如何走迷宫的问题。这里只涉及比较简单的模式，比如只找出一条可行的路径，不必是最短的，不能走重复的格子等。迷宫问题通常知道迷宫的入口和出口位置以寻求走出迷宫的路。迷宫可以用一个二维数组（python中的话就是一个列表中包含列表的二维列表）来抽象，每一个格子的位置的值可以是0或者1,0代表是空格而1代表这一格是墙。

　　一个比较自然的想法就是递归求解，初始位置位于入口，每到一个格子就判断是不是终点，如果不是就依次向周围四个方向探索，问题转化为寻找这个格子到出口的路径。当一个格子周围没有未涉足的空格时表明这次探索失败，应该回到上一格，寻找另一种路径。基于这样一种方法，给出下面这段程序：

dirs = [(0,1),(1,0),(0,-1),(-1,0)]  #方向的集合def mark(maze,pos): #标记走过的空格    maze[pos[0]][pos[1]] = 2def passable(maze,pos): #判断一格是否未涉足    return maze[pos[0]][pos[1]] == 0def find_path(maze,pos,end):    mark(maze,pos)    if pos == end:  #如果位置是终点        print pos        return True    for i in range(4):        nextp = pos[0] + dirs[i][0] ,pos[1] + dirs[i][1]        if nextp[0] >= len(maze) or nextp[1] >= len(maze):  #边界判断，如果超出迷宫范围了就不用尝试这种方向            continue        if passable(maze,nextp):            if find_path(maze,nextp,end):                print pos                return True    return False

　　另一种解决的思想是，不递归而用回溯方法解决。回溯法时要利用到栈，即每走一格就把这一格的信息加入到栈中，然后对这格周围进行探索，如果发现是死路就把栈中这格信息去掉，这样就自然回到了上一格。其实递归就是利用了python解释器自带的运行栈来做了类似的这么一件事。

　　草草看完这章，大概对栈和队列有了个模糊的认识，具体运用遥遥无期，也不知道知道如此浅薄的一点知识有没有用。越来越感到自己可能在这方面没什么天赋啊，算法数据结构什么的都要看好久才能弄懂一点，和看化学的时候完全不是一个感觉。。

【数据结构】栈和队列