python实现堆栈与队列的方法

下面是Python实现堆栈和队列的方法完整攻略，包含两条示例说明。

堆栈

什么是堆栈

堆栈是一种特殊的数据结构，其中新元素总是被添加到一端，该端被称为 “栈顶”，而现有元素只能从该端移除。由于新元素添加到栈顶，因此最后一个添加到栈内的元素第一个被移除，所以堆栈遵循了先进后出 (LIFO) 的原则。

如何实现堆栈

在 Python 中，使用列表 (list) 就可以轻易地实现堆栈。

堆栈的创建与初始化

stack = [] # 创建一个空栈

堆栈的入栈操作

使用 Python 列表的 append() 方法将新元素添加到栈顶。

stack.append(element)

堆栈的出栈操作

使用 Python 列表的 pop() 方法来移除位于栈顶的元素。

stack.pop()

判断堆栈是否为空

使用 Python 列表的特性，可以通过以下代码来判断堆栈是否为空：

if not stack:
    print("栈为空")

堆栈的示例问题

示例问题：判断一组括号表达式是否匹配。

例如：对于表达式 ()[]{}，我们可以发现每个左括号都有与之匹配的右括号，因此它是有效的。但是仅有左括号或者左右括号顺序不正确的表达式，如 [)(]，都是无效的。

使用堆栈可以轻松解决这个问题。

def is_valid(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

解释：

• 创建一个空栈和一个映射字典，字典的键为右括号，值为左括号；
• 遍历表达式中的每个字符；
• 如果当前字符是右括号，那么弹出堆栈中的栈顶元素，如果栈顶元素与该右括号所对应的左括号不匹配，则该表达式无效；
• 如果当前字符是左括号，将其入栈；
• 遍历完成后，如果堆栈中还有剩余元素，说明表达式无效，否则合法。

队列

什么是队列

队列是另一种重要的数据结构。与堆栈不同的是，队列中新元素总是加入到队列末尾，而现有元素总是被删除队列头部，同时队列遵循了先进先出 (FIFO) 的原则。

如何实现队列

在 Python 中，我们也可以使用列表来轻松实现队列。

队列的创建与初始化

queue = [] # 创建一个空队列

队列的入队操作

使用 Python 列表的 append() 方法将新元素添加到队列末尾。

queue.append(element)

队列的出队操作

使用 Python 列表的 pop() 方法来移除位于队列头部的元素。

queue.pop(0)

判断队列是否为空

与堆栈类似，使用 Python 列表的特性，可以通过以下代码来判断队列是否为空：

if not queue:
    print("队列为空")

队列的示例问题

示例问题：实现一个队列，要求该队列可以在给定时间限制内获取一个最大值。

例如：当给定一个队列 [1, 3, -1, -3, 5, 3, 6, 7] 和时间限制 k = 3 时，要求在每 3 个元素形成一个子序列的前提下，获取该子序列的最大值，并将所有最大值存储到一个列表中。

from collections import deque

def max_sliding_window(nums, k):
    n = len(nums)
    if n * k == 0:
        return []
    if k == 1:
        return nums

    def clean_deque(i):
        # 清除失效的窗口
        if deque and deque[0] == i - k:
            deque.popleft()

        # 清除小于新元素的数字
        while deque and nums[i] > nums[deque[-1]]:
            deque.pop()

    # 计算第一个窗口的最大值
    max_idx = 0
    for i in range(k):
        clean_deque(i)
        deque.append(i)
        if nums[i] > nums[max_idx]:
            max_idx = i
    output = [nums[max_idx]]

    # 遍历所有的窗口
    for i in range(k, n):
        clean_deque(i)
        deque.append(num)
        output.append(nums[deque[0]])
    return output

解释：

• 定义一个双端队列 deque 来记录当前窗口中最大数字的位置；
• 随着窗口向右移动，删除滑动窗口超过 k 的元素并清除小于新元素的数字；
• 在每个窗口移动前，将该窗口内的所有数字添加到 deque 中，并记录其中的最大值；
• 记录每个窗口的最大值，并将其添加到输出列表中。

这个算法的时间复杂度是 $O(n)$，空间复杂度是 $O(k)$。