python数据结构与算法-05

栈

栈这个词实际上在计算机科学里使用很多，除了数据结构外，还有内存里的栈区（和堆对应），熟悉 C 系语言的话应该不会陌生。
上一章我们讲到了先进先出 queue，其实用 python 的内置类型 collections.deque 或者我们自己实现的 LinkedList 来实现它都很简单。
本章我们讲讲后进先出的栈。

生活中的数据结构：

栈。好比在桶里头放盘子，先放的盘子放在了底下，后来的盘子放在上边。你要拿的时候，也是先拿最上边的。

栈其实也很简单，因为基础操作就俩，一个 push 和一个 pop，咦，咋和队列一样的？
确实方法名字一样，但是得到的结果可是不同的。

栈 ADT

上一章我介绍了我们怎样选取恰到的数据结构来实现新的 ADT？你能想到这里我们应该使用之前提到的哪个数据结构来实现吗？
你的大脑可能开始高(gui)速(su)旋转了，上几章学过的 array, list, deque, LinkedList, CircularDoubleLinkedList, queue
等在大脑里呼啸而过，这个时候可能已经一脸愁容了，到底该选啥？

还用问嘛，当然是时间复杂度最小的啦，大部分情况下空间都是够用的。
其实你会发现栈比队列还简单，因为它只在顶上操作（想象装着盘子的桶），如果有一种数据结构能方便在尾部增减元素不就满足需求了吗。
这个时候如果你忘记了，可以翻翻前几章，看看哪个数据结构符合要求。

想一下，似乎 CircularDoubleLinkedList 循环双端队列是满足的，因为增删最后一个元素都是 O(1)。
不过看了下示例代码，似乎没有 pop() 方法，对，因为我已经把实现 deque 作为思考题了。😂
如果之前你没写出来也没关系，这里我们会再实现它。

视频里我们将借助 CircularDoubleLinkedList 实现双端队列 Deque ，并且用 Deque 实现 Stack。

Stack over flow 什么鬼？

嗯，stackoverflow 不是一个程序员问答网站吗？没错。
函数的临时变量是存储在栈区的，如果你不幸写了一个没有出口的递归函数，就会这个错。不信你试试：

def infinite_fib(n):return infinite_fib(n-1) + infinite_fib(n-2)
infinite_fib(10)

一大段输出之后就会出现异常： RecursionError: maximum recursion depth exceeded。
后边会讲到递归，递归是初学者比较难理解的概念，在树的遍历等地方还会看到它。

源码

# -*- coding: utf-8 -*-# NOTE: 这里拷贝的 double_link_list.py 里的代码from collections import dequeclass Node(object):def __init__(self, value=None, prev=None, next=None):self.value, self.prev, self.next = value, prev, nextclass CircularDoubleLinkedList(object):"""循环双端链表 ADT多了个循环其实就是把 root 的 prev 指向 tail 节点，串起来"""def __init__(self, maxsize=None):self.maxsize = maxsizenode = Node()node.next, node.prev = node, nodeself.root = nodeself.length = 0def __len__(self):return self.lengthdef headnode(self):return self.root.nextdef tailnode(self):return self.root.prevdef append(self, value):    # O(1), 你发现一般不用 for 循环的就是 O(1)，有限个步骤if self.maxsize is not None and len(self) >= self.maxsize:raise Exception('LinkedList is Full')node = Node(value=value)tailnode = self.tailnode() or self.roottailnode.next = nodenode.prev = tailnodenode.next = self.rootself.root.prev = nodeself.length += 1def appendleft(self, value):if self.maxsize is not None and len(self) >= self.maxsize:raise Exception('LinkedList is Full')node = Node(value=value)if self.root.next is self.root:   # emptynode.next = self.rootnode.prev = self.rootself.root.next = nodeself.root.prev = nodeelse:node.prev = self.rootheadnode = self.root.nextnode.next = headnodeheadnode.prev = nodeself.root.next = nodeself.length += 1def remove(self, node):      # O(1)，传入node 而不是 value 我们就能实现 O(1) 删除"""remove:param node  # 在 lru_cache 里实际上根据key 保存了整个node:"""if node is self.root:returnelse:    #node.prev.next = node.nextnode.next.prev = node.prevself.length -= 1return nodedef iter_node(self):if self.root.next is self.root:returncurnode = self.root.nextwhile curnode.next is not self.root:yield curnodecurnode = curnode.nextyield curnodedef __iter__(self):for node in self.iter_node():yield node.valuedef iter_node_reverse(self):"""相比单链表独有的反序遍历"""if self.root.prev is self.root:returncurnode = self.root.prevwhile curnode.prev is not self.root:yield curnodecurnode = curnode.prevyield curnode############################################################
# 分割线，下边是本章 内容实现
############################################################class Deque(CircularDoubleLinkedList):   # 注意这里我们用到了继承，嗯，貌似我说过不会用啥 OOP 特性的，抱歉def pop(self):"""删除尾节点"""if len(self) == 0:raise Exception('empty')tailnode = self.tailnode()value = tailnode.valueself.remove(tailnode)return valuedef popleft(self):if len(self) == 0:raise Exception('empty')headnode = self.headnode()value = headnode.valueself.remove(headnode)return valuedef test_deque():dq = Deque()dq.append(1)dq.append(2)assert list(dq) == [1, 2]dq.appendleft(0)assert list(dq) == [0, 1, 2]dq.pop()assert list(dq) == [0, 1]dq.popleft()assert list(dq) == [1]dq.pop()assert len(dq) == 0class Stack(object):def __init__(self):self.deque = Deque()   # 你可以很容易替换为 python 内置的 collections.dequedef push(self, value):self.deque.append(value)def pop(self):return self.deque.pop()class Stack2(object):def __init__(self):self._deque = deque()def push(self, value):return self._deque.append(value)def pop(self):return self._deque.pop()def empty(self):return len(self._deque) == 0def test_stack():s = Stack()s.push(0)s.push(1)s.push(2)assert s.pop() == 2assert s.pop() == 1assert s.pop() == 0import pytest    # pip install pytestwith pytest.raises(Exception) as excinfo:   # 我们来测试是否真的抛出了异常s.pop()assert 'empty' in str(excinfo.value)if __name__ == '__main__':test_stack()

数据结构头脑风暴法

当我们不知道使用什么数据结构来解决问题的时候，《程序员面试金典》这本书的第六章提到了一种方式叫做『数据结构头脑风暴法』。
这种笨方法就是快速过一遍数据结构的列表，然后逐一尝试各种数据结构看看哪个最适合。

在你实现一个更高级的数据结构的时候，如果脑子没有思路，不妨尝试下这个方法，迅速过一遍你所知道的数据结构，看看哪种最适合。(从每个操作的时间复杂度和空间复杂度分析寻找最优解)

思考题

上一章我们用数组实现了队列，其实也能用数组来实现栈，你能自己用数组来实现一个栈的 ADT 吗？
实际上借助 python 内置的 list/collections.deque 结构就很容易实现一个栈，请你尝试实现，本章我们全部使用自己编写的数据结构而没用到 python 内置的数据结构。
这里我们自己实现了 Deque，你能用 python 内置的 collections.deque 实现栈吗？有轮子能直接用的话看起来就简单多了，这里我们为了学习数据结构的实现就避免了直接使用内置结构
哪些经典算法里使用到了栈呢？