Python 实现栈的几种方式及其优劣

持续创作，加速成长！这是我参加「日新计划 10 月更文挑战」的第 29 天，点击查看活动详情

1 栈的概念

栈由一系列目标目标安排的一个调集，这些目标的增加和删除操作都遵从一个“后进先出”（Last In First Out，LIFO）的准则。

在任何时刻只能向栈中插入一个目标，但只能取得或许删除只能在栈顶进行。比如由书构成的栈，仅有露出封面的书便是顶部的那本，为了拿到其他的书，只能移除压在上面的书，如图：

栈的实践应用

实践上很多应用程序都会用到栈，比如：

1. 网络阅读器将最近阅读的网址存放在一个栈中。每当用户拜访者拜访一个新网站时，这个新网站的网址就被压入栈顶。这样，每当咱们在阅读器单击“撤退”按钮时（或许按键盘快捷键 CTRL+Z ，大部分吊销快捷键），就能够弹出当时最近一次拜访的网址，以回到其先前拜访的阅读状况。

2. 文本修改器通常会提供一个“吊销”机制以吊销最近的修改操作并回来到先前状况。这个吊销操作也是经过将文本的改变状况保存在一个栈中得以完成。

3. 一些高级言语的内存管理，JVM 的栈、Python 栈还用于内存管理、嵌套言语特性的运行时环境等

4. 回溯（玩游戏，寻觅途径，穷举搜索）

5. 在算法中运用，如汉诺塔、树形遍历、直方图问题，也用于图算法，如拓扑排序

6. 语法处理：

• 参数和局部变量的空间是用仓库在内部创建的。

• 编译器对大括号匹配的语法检查

• 对递归的支持

• 在编译器中像后缀或前缀一样的表达式

2 栈的抽象数据类型

任何数据结构都离不开数据的保存和取得办法，如前所述，栈是元素的有序调集，增加和操作与移除都发生在其顶端（栈顶），那么它的抽象数据类型包括：

• Stack() :创建一个空栈，它不需求参数，且会回来一个空栈
• push(e): 将一个元素 e 增加到栈 S 的栈顶，它需求一个参数 e，且无回来值
• pop() : 将栈顶端的元素移除，它不需求参数，但会回来顶端的元素，而且修改栈的内容
• top(): 回来栈顶端的元素，可是并不移除栈顶元素；若栈为空，这个操作会操作
• is_empty(): 假如栈中不包括任何元素，则回来一个布尔值 True
• size()：回来栈中元素的数据。它不需求参数，且会回来一个整数。在 Python 中，能够用 __len__ 这个特别办法完成。

Python 栈的巨细或许是固定的，也或许有一个动态的完成，即答应巨细改变。在巨细固定栈的情况下，企图向现已满的栈增加一个元素会导致栈溢出异常。相同，企图从一个现已是空的栈中移除一个元素，进行 pop() 操作这种情况被称为下溢。

3 用 Python 的列表完成栈

在学习 Python 的时候，一定学过 Python 列表 list , 它能经过一些内置的办法完成栈的功用：

• 经过 append 办法用于增加一个元素到列表尾部，这种办法就能模仿 push() 操作
• 经过 pop() 办法用于模仿出栈操作
• 经过 L[-1] 模仿 top()操作
• 经过判断 len(L)==0 模仿 isEmpty() 操作
• 经过 len() 函数完成 size() 函数

代码如下：

class ArrayStack:
    """ 经过 Python 列表完成 LIFO 栈"""
    def __init__(self):
        self._data = []
    def size(self):
        """ return the number of elements in the stack"""
        return len(self._data)
    def is_empty(self):
        """ return True if the stack is empty"""
        return len(self._data) == 0
    def push(self, e):
        """ add element e to the top of the stack"""
        self._data.append(e)
    def pop(self):
        """ remove and return the element from the top of the stack
        """
        if self.is_empty():
            raise Exception('Stack is empty')
        return self._data.pop()
    def top(self):
        """return the top of the stack
        Raise Empty exception if the stack is empty
        """
        if self.is_empty():
            raise Exception('Stack is empty')
        return self._data[-1]  # the last item in the list
arrayStack = ArrayStack()
arrayStack.push("Python")
arrayStack.push("Learning")
arrayStack.push("Hello")
print("Stack top element: ", arrayStack.top())
print("Stack length: ", arrayStack.size())
print("Stack popped item: %s" % arrayStack.pop())
print("Stack is empty?", arrayStack.is_empty())
arrayStack.pop()
arrayStack.pop()
print("Stack is empty?", arrayStack.is_empty())
# arrayStack.pop()

运行该程序，结果：

Stack top element:  Hello
Stack length:  3
Stack popped item: Hello
Stack is empty? False
Stack is empty? True

除了将列表的队尾作为栈顶，也能够经过将列表的头部作为栈的顶端。不过在这种情况下，便无法直接运用 pop() 办法和 append()办法，可是能够经过 pop() 和 insert() 办法显式地拜访下标为 0 的元素，即列表的第一个元素，代码如下：

class ArrayStack:
    """ 经过 Python 列表完成 LIFO 栈"""
    def __init__(self):
        self._data = []
    def size(self):
        """ return the number of elements in the stack"""
        return len(self._data)
    def is_empty(self):
        """ return True if the stack is empty"""
        return len(self._data) == 0
    def push(self, e):
        """ add element e to the top of the stack"""
        self._data.insert(0, e)
    def pop(self):
        """ remove and return the element from the top of the stack
        """
        if self.is_empty():
            raise Exception('Stack is empty')
        return self._data.pop(0)
    def top(self):
        """return the top of the stack
        Raise Empty exception if the stack is empty
        """
        if self.is_empty():
            raise Exception('Stack is empty')
        return self._data[0]  # the last item in the list

尽管咱们改变了抽象数据类型的完成，却保留了其逻辑特征，这种能力体现了抽象思想。不论，尽管两种办法都完成了栈，但两者的功用办法有差异：

• append() 和 pop() 办法的时刻复杂度都是 O(1)，常数等级操作
• 第二种完成的功用则受制于栈中的元素个数，这是由于 insert(0) 和 pop(0) 的时刻复杂度都是 O(n)，元素越多就越慢。

4 用 collections.deque 完成栈

在 Python 中，collections 模块有一个双端行列数据结构 deque，这个数据结构相同完成了 append() 和 pop() 办法：

>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('Apple')
>>> myStack.append('Banana')
>>> myStack.append('Orange')
>>> 
>>> myStack
deque(['Apple', 'Banana', 'Orange'])
>>> myStack.pop()
'Orange'
>>> myStack.pop()
'Banana'
>>>
>>> len(myStack)
1
>>> myStack[0]
'Apple'
>>> myStack.pop()
'Apple'
>>>
>>> myStack.pop()
Traceback (most recent call last):
  File "<pyshell#13>", line 1, in <module>
    myStack.pop()
IndexError: pop from an empty deque
>>> 

为什么有了 list 还需求 deque？

或许你能够看到 deque 和列表 list 对元素的操作差不多，那么为什么 Python 中有列表还增加了 deque 这一个数据结构呢？

那是由于，Python 中的列表树立在连续的内存块中，意味着列表的元素是紧挨着存储的。

这对一些操作来说十分有用，比如对列表进行索引。获取 myList[3] 的速度很快，由于 Python 确切地知道在内存中寻觅它的位置。这种内存布局也答应切片在列表上很好地工作。

毗连的内存布局是 list 或许需求花费更多时刻来 .append() 一些目标。假如连续的内存块现已满了，那么它将需求取得另一个内存块，先将全体 copy 过去，这个动作或许比一般的 .append() 操作花费更多的时刻。

而双端行列 deque 是树立在一个双链表的基础上。在一个链接列表结构中，每个条目都存储在它自己的内存块中，并有一个对列表中下一个条目的引用。

双链表也是如此，仅仅每个条目都有对列表中前一个和后一个条目的引用。这使得你能够很容易地在列表的两端增加节点。

在一个链接列表结构中增加一个新的条目，只需求设置新条目的引用指向当时仓库的顶部，然后将仓库的顶部指向新条目。

但是，这种在栈上不断增加和删除条目的时刻是有价值的。获取 myDeque[3] 的速度要比列表慢，由于 Python 需求走过列表的每个节点来获取第三个元素。

走运的是，你很少想在栈上做随机索引元素或进行列表切片操作。栈上的大多数操作都是 push 或 pop。

假如你的代码不运用线程，常数时刻的 .append() 和 .pop() 操作使 deque 成为完成 Python 栈的一个更好的挑选。

5 用 queue.LifoQueue 完成栈

Python 栈在多线程程序中也很有用，咱们现已学习了 list 和 deque 两种办法。关于任何能够被多个线程拜访的数据结构，在多线程编程中，咱们不应该运用 list，由于列表不是线程安全的。deque 的 .append() 和 .pop() 办法是原子性的，意味着它们不会被不同的线程搅扰。

因此，尽管运用 deque 能够树立一个线程安全的 Python 仓库，但这样做会使你自己在将来被人误用，造成竞态条件。

好吧，假如你是多线程编程，你不能用 list 来做仓库，你或许也不想用 deque 来做仓库，那么你怎么为一个线程程序树立一个 Python 仓库？

答案就在 queue 模块中：queue.LifoQueue。还记得你是怎么学习到栈是按照后进先出（LIFO）的准则运行的吗？嗯，这便是 LifoQueue 的 “Lifo “部分所代表的含义。

尽管 list 和 deque 的接口类似，但 LifoQueue 运用 .put() 和 .get() 来从栈中增加和删除数据。

>>> from queue import LifoQueue
>>> stack = LifoQueue()
>>> stack.put('H')
>>> stack.put('E')
>>> stack.put('L')
>>> stack.put('L')
>>> stack.put('O')
>>> stack
<queue.LifoQueue object at 0x00000123159F7310>
>>> 
>>> stack.get()
'O'
>>> stack.get()
'L'
>>> stack.empty()
False
>>> stack.qsize()
3
>>> stack.get()
'L'
>>> stack.get()
'E'
>>> stack.qsize()
1
>>> stack.get()
'H'
>>> stack.get_nowait()
Traceback (most recent call last):
  File "<pyshell#31>", line 1, in <module>
    stack.get_nowait()
_queue.Empty
>>> 
>>> stack.put('Apple')
>>> stack.get_nowait()
'Apple'

与 deque 不同，LifoQueue 被规划为彻底线程安全的。它的所有办法都能够在线程环境中安全运用。它还为其操作增加了可选的超时功用，这在线程程序中经常是一个必须的功用。

但是，这种彻底的线程安满是有价值的。为了完成这种线程安全，LifoQueue 必须在每个操作上做一些额外的工作，这意味着它将花费更长的时刻。

通常情况下，这种细微的减速对你的全体程序速度并不重要，但假如你现已测量了你的功用，并发现你的仓库操作是瓶颈，那么小心肠切换到 deque 或许是值得做的。

6 挑选哪一种完成作为栈

一般来说，假如你不运用多线程，你应该运用 deque。假如你运用多线程，那么你应该运用 LifoQueue，除非你现已测量了你的功用，发现 push 和 pop 的速度的小幅提高会带来满足的差异，以保证维护风险。

你能够对列表或许很熟悉，但需求谨慎运用它，由于它有或许存在内存重新分配的问题。deque 和 list 的接口是相同的，而且 deque 没有线程不安全问题。

7 总结

本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中怎么运用它的情况。在文章的中，介绍了 Python 中完成栈的三种不同办法，知道了 deque 关于非多线程程序是一个更好的挑选，假如你要在多线程编程环境中运用栈的话，能够运用 LifoQueue。

期望本文能对你有所帮助，假如喜欢本文，能够点个关注。

这里是世界之一粟，下一篇文章见！

世界古今无有穷期，终身不过顷刻，当思奋争。

参考链接：

• 数据结构
• How to Implement a Python Stack
• Python数据结构与算法分析（第2版），3.3 栈