3.1 堆栈的基础知识

3.1.1 堆栈操作及时间复杂度

堆栈中主要执行以下基本操作（如图3-1所示）。

❑push：向堆栈中添加一个元素。如果堆栈已满，则称其为溢出条件。

❑pop：从堆栈中删除一个元素。元素以压入的相反顺序弹出。如果堆栈为空，则称其为下溢条件。

❑top：返回堆栈的顶部元素。

❑isEmpty：如果堆栈为空，则返回True，否则返回False。

push、pop、isEmpty和top操作的时间复杂度均为 O （1），这些操作都不会运行任何循环。

3.1.2 3种实现方式

Python中有多种方法可以实现堆栈操作，这里使用Python库中的数据结构和模块来实现。Python中实现堆栈的方式有：①list；②collections.deque；③queue.LifoQueue。

1.基于列表的堆栈实现方式

Python的内置列表数据结构list可以用作堆栈，append()函数用于将元素添加到堆栈的顶部，pop()函数用于按LIFO顺序删除元素。

list最大的问题是随着数据结构的增长会遇到速度问题。列表中的各项在内存中彼此相邻存储，如果堆栈的大小大于当前内存块的大小，则Python需要进行内存分配，这可能导致某些append()调用比其他调用花费更长的时间。

运行结果：

2.基于deque的堆栈实现方式

可以使用collections模块中的deque类来实现堆栈。在需要从容器的两端更快地执行添加和弹出操作的情况下，与列表相比，使用deque更可取，因为与列表相比，deque的添加和弹出操作的时间复杂度为 O （1）。

deque中使用与列表相同的函数—append()和pop()对堆栈进行操作。

运行结果：

3.基于LifoQueue的堆栈实现方式

Python中的queue模块中的LifoQueue可以用来实现堆栈。此模块提供了以下函数实现堆栈操作：

❑maxsize()：堆栈中允许的最大元素个数。

❑empty()：如果堆栈为空，则返回True，否则返回False。

❑full()：如果堆栈满了，则返回True。如果堆栈使用maxsize=0（默认值）初始化，则full()永远不会返回True。

❑get()：从堆栈中删除并返回一个元素。如果堆栈为空，请等待，直到有一个元素可用。

❑get_nowait()：如果元素立即可用，则返回此元素，否则引发空队列（QueueEmpty）。

❑put（item）：将元素放入堆栈。如果堆栈已满，请等到有空闲位置后再添加。

❑put_nowait（item）：将元素放入堆栈而不会阻塞。

❑qsize()：返回堆栈中的元素个数。如果没有可用的空闲位置，请增加满队列（QueueFull）。

运行结果：

3.1.3 堆栈的应用

堆栈的应用举例如下。

❑用于符号平衡，例如https://leetcode.com/problems/valid-parentheses/。

❑用于把后缀/前缀转换为中缀。

❑实现重做—撤销功能，例如编辑器、photoshop，https://leetcode.com/problems/basic-calculator/。

❑实现Web浏览器中的前进和后退功能。

❑用于算法求解，例如河内塔、树遍历（https://leetcode.com/problems/binary-tree-postorder-traversal/）、股票跨度问题（https://www.geeksforgeeks.org/the-stock-span-problem/）、直方图问题（https://leetcode.com/problems/largest-rectangle-in-histogram/）等。

❑用于其他应用程序，例如回溯问题、骑士之旅问题、迷宫中的老鼠、N皇后问题和数独求解器。

❑用于图算法，例如拓扑排序和强连接的组件。 2k9NQzzPrxFSuwlWyxMSRug2X7EyR4uQSfHzXBpKpQ7Rf1cAg6JA+iS4yFJ1Pnm8