栈(Stack)
栈这种结构强调的是栈运算，实现了如下3种运算的结构就是栈：
1) \(push(x)\)：存入\(x\)元素(也称为压栈)；
2) \(pop()\)：删除最后一次存入的元素并返回该元素(也称为弹栈)；
3) \(top()\)：返回最后一次存入的元素(也称为栈顶，所以写作top)；
直观上栈像狭长的储物箱，只有一面开口，只能看到最顶上的物品，取最里面的物品时要自顶向下的先拿出所有其他物品。这3种运算使栈中的元素在逻辑上也蕴含着前驱后继关系，所以栈也是线性表。但栈不必像数组和链表那样，必须提供查看任意元素、在任意元素间插入、删除任意元素等各种运算，所以直观上栈并不像一张“表”，而像是有3个运算的“黑箱”，所以栈也被称为操作受限的线性表。当然如果在链表或数组的基础上实现栈运算的话，那也可以作为栈。栈作为后进先出(LIFO, Last In First Out)结构，看起来不够“自然”，但栈的应用很广，其中一个原因是其LIFO的逻辑能让栈每执行完一次\(pop\)就能回到最后一次执行\(push\)前的状态。在一些使用栈的算法中，会用到这个性质。
程序语言中很少有专门实现栈的数据类型，需要栈时一般使用基于数组和链表的数据类型实现。Python的list提供尾部的插入和删除运算，所以list可直接当栈使用，根据Python文档list的尾部操作的代价大致是\(O(1)\)。然后自己在程序中实现基于链表的栈，把栈顶放在表头能更容易实现\(O(1)\)代价的\(push,pop\)，具体如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Node: def __init__(self, key): self.key = key self.next = None class Stack: def __init__(self): self._head = None def top(self): return self._head def push(self, key): oldHead = self._head self._head = Node(key) self._head.next = oldHead def pop(self): if self._head: oldHead = self._head self._head = oldHead.next return oldHead.key raise Exception('栈为空') |
用栈展开递归函数
栈和程序语言中的递归函数有内在联系，在递归调用过程中，外层的递归比内层更早的开始，但只有在内层递归结束后外层递归才结束，所以递归调用和栈一样是“先进后出”的。事实上程序语言底层是在内存这个“大数组”上模拟了栈，进而才能让函数有递归的能力。所以使用递归程序等于使用程序底层提供的“栈”，这就意味着可以不用这个“栈”，直接在程序中自己构建和维护栈，把程序改为非递归的。其具体实现方式因问题而异，比较灵活，良好的实现能有优于递归的性能。
下面第1个程序是递归实现的求\(n\)阶乘(\(n>0\))，然后考虑用栈来模拟该递归逻辑，其步骤如下：
1) 按次序将\(n,n-1,…,1\)入栈；
2) 出栈一个元素并将其计为\(x\)；
3) 若此时栈为空说明\(x\)是原问题的结果，程序在该步返回\(x\)，否则什么也不做；
4) 出栈一个元素并将其计为\(y\)，计算\(xy\)并将\(xy\)入栈，回到步骤(2)；
上述过程中(1)对应一层层进入递归调用，(2)对应一层层结束递归调用，并返回利用子递归和输入计算的结果，下面第2个程序就实现了这个过程。这里也是直接用Python的list来作为栈使用的。
1 2 3 4 | def f(n): if n == 1: return 1 return n * f(n-1) |
1 2 3 4 5 6 7 8 | def f(n): stack = [i for i in range(n, 0, -1)] while True: x = stack.pop() if not stack: return x y = stack.pop() stack.append(x * y) |
队列(Queue)
队列也是操作受限的线性表，其和栈的唯一区别是队列是先进先出(LIFO, First In First Out)的。直观上队列和排队的队伍一样，最先从队尾进入队伍的人一定会最先从队头出队。队列需要实现如下运算：
1) \(get()\)：将队尾元素出队并返回该元素；
2) \(put(x)\)：将元素\(x\)从队头入队；
这种LIFO结构比栈更“自然”，但这使队列不具备栈的性质，即从队列出队一个元素后，队列不会回到最后一次入队前的状态。队列的应用同样广泛，在服务器程序中，经常用队列缓冲短期大量的请求。在多线程编程中，经常用队列实现“生产者-消费者”设计模式。Python内置了队列库Queue，其能够实现\(O(1)\)的出入队运算，但其是专门用来做线程间通信的。下面基于Python单链表实现队列，为使出入队代价都是\(O(1)\)，用额外的\(tail\)变量维护链表尾节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Node: def __init__(self, key): self.key = key self.next = None class Queue: def __init__(self): self._head = None self._tail = None def put(self, key): if not self._head: self._head = self._tail = Node(key) else: self._tail.next = Node(key) self._tail = self._tail.next def get(self): if not self._head: raise Exception('队列为空') key = self._head.key self._head = self._head.next if not self._head: self._tail = None return key |
队列的环形数组实现
直接用数组实现队列不是个好方法，比如让数组从左边出队，右边入队，那每次出队都要让后面所有元素改变索引，出队的代价就是\(O(n)\)。如果反过来让数组从右边出队左边入队，那入队的代价就是\(O(n)\)。为了解决这种问题，需要引入环形数组的概念，就是假想把数组尾接到数组头上。然后基于环形数组实现出入队都是\(O(1)\)的队列。需要注意的是由于使用了数组，数组创建时是要指定最大容量的，所以这种队列也是需要确定最大容量的。实现思路如上图所示，先根据容量\(size\)创建容量\(size+1\)的数组\(L\)，多1位是为了之后处理边界情况。然后初始化\(rear = front = 0\)分别表示“下次入队的位置”和“下次出队的位置”。利用取余(\(\% \))运算实现“环形”移动\(rear\)和\(front\)。下面给出实现队列运算的步骤：
1) \(isFull\)：判断队列是否已满，方法是若\((rear +1) ~\%~ size = front ~\%~ size\)，则队列已满；
2) \(isEmpty\)：判断是否为空队列，方法是若\(rear ~\%~ size = front ~\%~ size\)，则队列为空；
3) \(put(x)\)：若队列未满，令\(L[rear ~\%~ size] = x\)，令\(rear\)自增；
4) \(get()\)：若队列非空，令\(x = L[front ~\%~ size]\)，令\(front\)自增，返回\(x\)；
下面是以Python的list为数组实现的环形数组队列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Queue: def __init__(self, size): if size < 1: raise Exception('队列容量至少为1') self.size = size + 1 self.front = 0 self.rear = 0 self.l = [None for i in range(self.size)] def isEmpty(self): return self.rear % self.size == self.front % self.size def isFull(self): return (self.rear + 1) % self.size == self.front % self.size def put(self, x): if self.isFull(): raise Exception('队列已满') self.l[self.rear % self.size] = x self.rear += 1 def get(self): if self.isEmpty(): raise Exception('队列为空') x = self.l[self.front % self.size] self.l[self.front % self.size] = None self.front += 1 return x |
双端队列(Deque)
双端队列(Double-Ended Queue)是能在任意时刻执行“左端入队、左端出队、右端入队、右端出队”的结构，其在算法中的应用是十分广泛的，因为在任意时刻都能既当作栈又当作队列。Python内置的collections库提供了双端队列collections.deque供程序使用，其支持上述4种运算，且代价都是\(O(1)\)，其底层是链表的实现。在算法需要使用队列/栈/双端队列时，都可以直接用这个对象。这里用双向链表自己实现双端队列，其能够保证4个操作的时间复杂度都是\(O(1)\)，具体程序如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | class Node: def __init__(self, key): self.key = key self.next = None self.prev = None class Deque: def __init__(self): self._head = None self._tail = None self.size = 0 def putRight(self, key): newNode = Node(key) if not self._head: self._head = self._tail = newNode else: self._tail.next = newNode self._tail.next.prev = self._tail self._tail = newNode self.size += 1 def putLeft(self, key): newNode = Node(key) if not self._head: self._head = self._tail = newNode else: newNode.next = self._head newNode.next.prev = newNode self._head = newNode self.size += 1 def getLeft(self): if not self._head: raise Exception('队列为空') key = self._head.key self._head = self._head.next if self._head: self._head.prev = None else: self._tail = None self.size -= 1 return key def getRight(self): if not self._tail: raise Exception('队列为空') key = self._tail.key if not self._tail.prev: self._head = self._tail = None else: self._tail.prev.next = None self._tail = self._tail.prev self.size -= 1 return key |