Python数据结构之栈、队列及双端队列

在 Python 中，栈、队列及双端队列是常用的数据结构。它们的实现都可以基于列表、元组、链表或其他数据类型。下面分别来讲解这三种数据结构的原理、实现和应用。

栈（Stack）

栈是一种仅能在一端进行插入和删除操作的特殊线性表，即后进先出（Last-In-First-Out，LIFO）的数据结构。在 Python 中，我们可以使用列表或双端队列来实现栈。

栈的实现

以下示例展示了如何使用列表来实现栈：

stack = []  # 初始化一个空栈
stack.append("apple")  # 入栈
stack.append("banana")
stack.append("cherry")
print(stack)  # 输出：['apple', 'banana', 'cherry']
top = stack[-1]  # 访问栈顶元素
print(top)  # 输出：'cherry'
stack.pop()  # 出栈
print(stack)  # 输出：['apple', 'banana']

栈的应用

• 实现函数调用的可撤销和恢复（undo、redo）操作。
• 括号匹配等程序员常见问题。
• 逆序输出字符串等问题。

队列（Queue）

队列是一种只允许在一端插入数据、在另一端删除数据的线性数据结构，即先进先出（First-In-First-Out，FIFO）的数据结构。在 Python 中，队列可以由列表、元组、堆以及 Python 自带的 queue 模块实现。

队列的实现

以下示例展示了如何使用列表来实现队列：

queue = []  # 初始化一个空队列
queue.append("apple")  # 入队
queue.append("banana")
queue.append("cherry")
print(queue)  # 输出：['apple', 'banana', 'cherry']
front = queue[0]  # 访问队头元素
print(front)  # 输出：'apple'
queue.pop(0)  # 出队
print(queue)  # 输出：['banana', 'cherry']

队列的应用

• 任务调度等等多种场景中都能使用队列。

双端队列（Deque）

双端队列是一种有头有尾、支持两端插入和删除操作的线性数据结构。在 Python 中，双端队列可以由列表或 Python 自带的 collections 模块的 deque 实现。

双端队列的实现

以下示例展示了如何使用 collections 模块的 deque 来实现双端队列：

from collections import deque

deque = deque()  # 初始化一个空双端队列
deque.append("apple")  # 在队尾插入数据
deque.appendleft("banana")  # 在队头插入数据
print(deque)  # 输出：deque(['banana', 'apple'])
front = deque[0]  # 访问队头元素
print(front)  # 输出：'banana'
rear = deque[-1]  # 访问队尾元素
print(rear)  # 输出：'apple'
deque.pop()  # 从队尾删除元素
deque.popleft()  # 从队头删除元素
print(deque)  # 输出：deque([])

双端队列的应用

• 最近相关性缓存（Least Recently Used，LRU）缓存算法。
• 游戏开发等多种场景中都能使用双端队列。

结语

以上就是 Python 中栈、队列及双端队列的基础知识和实现。根据实际需求，我们可以选择不同的数据结构来实现相应的功能。