当前位置: 首页 > article >正文

【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])

http://www.kler.cn/a/449789.html

相关文章:

  • 基于Spring Boot的九州美食城商户一体化系统
  • Redis篇--常见问题篇6--缓存一致性1(Mysql和Redis缓存一致,更新数据库删除缓存策略)
  • “AI 线索精益模型调用系统:开启精准营销新引擎
  • 门户系统需要压测吗?以及门户系统如何压力测试?
  • Retrofit源码分析:动态代理获取Api接口实例,解析注解生成request,线程切换
  • [Unity Shader][图形渲染] Shader数学基础11 - 复合变换详解
  • 51单片机仿真摇号抽奖机源程序 12864液晶显示
  • Flink集群批作业实践:七析BI批作业执行
  • 【源码阅读系列】(六) Android 中的进程和线程
  • kubevirt网络
  • Jmeter测试脚本编写技巧
  • 从零开始学前端之HTML(三)
  • 咸虾米壁纸微信小程序下载图片到相册saveImageToPhotosAlbum功能修改
  • PLSQL 客户端连接 Oracle 数据库配置
  • 算法day_3数组中的单一元素和二进制位颠倒
  • autMan奥特曼机器人-相关命令
  • 【漏洞复现】F5 BIG-IP Next Central Manager SQL注入漏洞(CVE-2024-26026)
  • (10)YOLOv8算法基本原理
  • EasyPlayer.js播放器在React项目中应如何使用?
  • Jenkins Api Token 访问问题
  • MySQL 数据备份与恢复详解
  • 压缩为zip和gzip工具类
  • MySQL快速扫描
  • ios按键精灵脚本开发:ios悬浮窗命令
  • PHP中替换某个包或某个类
  • Linux 软硬链接详解:深入理解与实践