【python】数据结构之栈与队列

在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_size
        self.size = 0

    def length(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.max_size

    def push(self, item):
        if self.is_full():
            raise Exception("stack is full")
        self.items.append(item)
        self.size += 1

    def pop(self):
        if self.is_empty():
            raise Exception("stack is empty")
        self.size -= 1
        return 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 pop
    raise 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_size
        self.size = 0

    def length(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.max_size

    def enqueue(self, item):
        if self.is_full():
            raise Exception("queue is full")
        self.items.append(item)
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("stack is empty")
        self.size -= 1
        return 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 dequeue
    raise 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])