在Python3中，列表（list）是一种非常灵活的数据结构，可以用来实现多种其他数据结构，包括栈（Stack）、队列（Queue）。虽然Python的内置列表已经提供了很多强大的功能，但有时候为了实现特定的数据操作行为（如LIFO、FIFO或动态大小），我们可能会选择用列表来模拟这些数据结构。
栈（Stack）
栈是一种后进先出（LIFO, Last In First Out）的数据结构。在Python中，我们可以使用列表的append()和pop()方法来实现栈。
class Stack:def __init__(self, max_size: int):self.items = []self.max_size = max_sizeself.size = 0def length(self):return self.sizedef is_empty(self):return self.size == 0def is_full(self):return self.size == self.max_sizedef push(self, item):if self.is_full():raise Exception("stack is full")self.items.append(item)self.size += 1def pop(self):if self.is_empty():raise Exception("stack is empty")self.size -= 1return self.items.pop()def peek(self):if self.is_empty():raise Exception("stack is empty")return self.items[-1]stack = Stack(3)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.length())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
运行结果如下：
3
3
2
1
Traceback (most recent call last):File "stack_demo.py", line 42, in <module>print(stack.pop())^^^^^^^^^^^File "stack_demo.py", line 25, in popraise Exception("stack is empty")
Exception: stack is empty
队列（Queue）
队列是一种先进先出（FIFO, First In First Out）的数据结构。在Python中，同样可以使用列表来实现队列。
class Queue:def __init__(self, max_size: int):self.items = []self.max_size = max_sizeself.size = 0def length(self):return self.sizedef is_empty(self):return self.size == 0def is_full(self):return self.size == self.max_sizedef enqueue(self, item):if self.is_full():raise Exception("queue is full")self.items.append(item)self.size += 1def dequeue(self):if self.is_empty():raise Exception("stack is empty")self.size -= 1return self.items.pop(0)queue = Queue(3)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.length())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
运行结果如下：
3
1
2
3
Traceback (most recent call last):File "queue_demo.py", line 37, in <module>print(queue.dequeue())^^^^^^^^^^^^^^^File "queue_demo.py", line 25, in dequeueraise Exception("stack is empty")
Exception: stack is empty
双端队列（deque）
虽然Python的列表可以用来实现队列，但使用collections.deque（双端队列）通常更高效，因为它在两端进行插入和删除操作的时间复杂度都是O(1)。
collections.deque是Python标准库collections模块中的一个双端队列（double-ended queue）的实现。双端队列是一种具有两个端点的队列，允许在两端快速地添加（append）和弹出（pop）元素。这使得deque非常适合用作需要频繁在两端进行操作的场景，比如实现一个缓存（cache）或者一个队列（queue）和栈（stack）的混合体。
主要特点
- 快速从两端添加或删除元素：deque提供了在两端进行O(1)时间复杂度的append和pop操作，这意味着无论队列的大小如何，这些操作的速度都是恒定的。
- 线程安全：虽然deque的操作本身不是原子性的，但它在内部使用了锁，使得在多线程环境下对deque的迭代通常是安全的（尽管在迭代过程中修改deque可能会导致未定义行为）。
- 内存效率：与列表（list）相比，deque在内存使用上更加高效，特别是在元素数量非常大时。这是因为列表是基于数组的，而 deque是基于双向链表的。
基本操作
创建双端队列：
- 通过
collections.deque()来创建一个空的双端队列 - 通过
collections.deque([iterable])来创建一个预填充了元素的双端队列。
添加元素：
- append(x)：在右端添加一个元素。
- appendleft(x)：在左端添加一个元素。
移除元素：
- pop()：移除并返回右端的元素。
- popleft()：移除并返回左端的元素。
查看元素：
deque[0]：查看左端元素，不移除deque[-1]：查看右端元素，不移除
长度：可以使用len(deque)来获取deque的长度。
迭代：deque支持迭代，可以像列表一样遍历其中的元素。
使用示例
from collections import deque# 创建一个空的双端队列
dq = deque()# 在右端添加元素
dq.append(1)
dq.append(2)# 在左端添加元素
dq.appendleft(0)# 打印队列内容
print(dq) # 输出: deque([0, 1, 2])# 从右端移除元素
print(dq.pop()) # 输出: 2# 从左端移除元素
print(dq.popleft()) # 输出: 0# 打印剩余元素
print(dq) # 输出: deque([1])
