Python中栈、队列与优先级队列的实现方法
作者:GoT阳仔 发布时间:2023-11-03 02:16:53
前言
栈、队列和优先级队列都是非常基础的数据结构。Python作为一种“编码高效”的语言,对这些基础的数据结构都有比较好的实现。在业务需求开发过程中,不应该重复造轮子,今天就来看看些数据结构都有哪些实现。
0x00 栈(Stack)
栈是一种LIFO(后进先出)的数据结构,有入栈(push)、出栈(pop)两种操作,且只能操作栈顶元素。
在Python中有多种可以实现栈的数据结构。
1、list
list是Python内置的列表数据结构,它支持栈的特性,有入栈和出栈操作。只不过用list实现栈性能不是特别好。
因为list内部是通过一个动态扩容的数组来实现的。当增减元素时就有可能会触发扩容操作。如果在list的头部增减元素,也会移动整个列表。
如要使用list来实现一个栈的话,可以使用list的append()(入栈)、pop()(出栈)方法。
>>> s = []
>>> s.append('one')
>>> s.append('two')
>>> s.append(3)
>>> s
['one', 'two', 3]
>>> s.pop()
3
>>> s.pop()
'two'
>>> s.pop()
'one'
>>> s.pop()
IndexError: pop from empty list
2、collections.deque
deque类是一种双端队列。在Python中它就是一个双向列表,可以以常用时间在两端执行添加和删除元素的操作,非常高效,所以它既可以实现栈也可以实现队列。
如果要在Python实现一个栈,那么应该优先选择deque,而不是list。
deque的入栈和出栈方法也分别是append()和pop()。
>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')
>>> s
deque(['eat', 'sleep', 'code'])
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
>>> s.pop()
IndexError: pop from an empty deque
3、queue.LifoQueue
顾名思义,这个就是一个栈。不过它是线程安全的,如果要在并发的环境下使用,那么就可以选择使用LifoQueue。
它入栈和出栈操作是使用put()和get(),其中get()在LifoQueue为空时会阻塞。
>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')
>>> s
<queue.LifoQueue object at 0x109dcfe48>
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
>>> s.get()
# 阻塞并一直等待直到栈不为空
0x01 队列(Queue)
队列是一种FIFO(先进先出)的数据结构。它有入队(enqueue)、出队(dequeue)两种操作,而且也是常数时间的操作。
在Python中可以使用哪些数据结构来实现一个队列呢?
1、list
list可以实现一个队列,但它的入队、出队操作就不是非常高效了。因为list是一个动态列表,在队列的头部执行出队操作时,会发生整个元素的移动。
使用list来实现一个队列时,用append()执行入队操作,使用pop(0)方法在队列头部执行出队操作。由于在list的第一个元素进行操作,所以后续的元素都会向前移动一位。因此用list来实现队列是不推荐的。
>>> q = []
>>> q.append('1')
>>> q.append('2')
>>> q.append('three')
>>> q.pop(0)
'1'
>>> q.pop(0)
'2'
>>> q.pop(0)
'three'
>>> q.pop(0)
IndexError: pop from empty list
2、collections.deque
从上文我们已经知道deque是一个双向列表,它可以在列表两端以常数时间进行添加删除操作。所以用deque来实现一个队列是非常高效的。
deque入队操作使用append()方法,出队操作使用popleft()方法。
>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
>>> q.append('sleep')
>>> q.append('code')
>>> q
deque(['eat', 'sleep', 'code'])
# 使用popleft出队
>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'
>>> q.popleft()
IndexError: pop from an empty deque
3、queue.Queue
同样地,如果要在并发环境下使用队列,那么选择线程安全的queue.Queue。
与LifoQueue类似,入队和出队操作分别是put()和get()方法,get()在队列为空时会一直阻塞直到有元素入队。
>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<queue.Queue object at 0x110564780>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
# 队列为空不要执行等待
>>> q.get_nowait()
_queue.Empty
>>> q.put('111')
>>> q.get_nowait()
'111'
>>> q.get()
# 队列为空时,会一直阻塞直到队列不为空
4、multiprocessing.Queue
多进程版本的队列。如果要在多进程环境下使用队列,那么应该选择multiprocessing.Queue。
同样地,它的入队出队操作分别是put()和get()。get()方法在队列为空,会一直阻塞直到队列不为空。
>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')
>>> q
<multiprocessing.queues.Queue object at 0x110567ef0>
>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'
>>> q.get_nowait()
_queue.Empty
>>> q.get()
# 队列为空时,会一直阻塞直到队列不为空
0x02 优先级队列(PriorityQueue)
一个近乎排序的序列里可以使用优先级队列这种数据结构,它能高效获取最大或最小的元素。
在调度问题的场景中经常会用到优先级队列。它主要有获取最大值或最小值的操作和入队操作。
1、list
使用list可以实现一个优先级队列,但它并不高效。因为当要获取最值时需要排序,然后再获取最值。一旦有新的元素加入,再次获取最值时,又要重新排序。所以并推荐使用。
2、heapq
一般来说,优先级队列都是使用堆这种数据结构来实现。而heapq就是Python标准库中堆的实现。heapq默认情况下实现的是最小堆。
入队操作使用heappush(),出队操作使用heappop()。
>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, 'code'))
>>> heapq.heappush(q, (1, 'eat'))
>>> heapq.heappush(q, (3, 'sleep'))
>>> q
[(1, 'eat'), (2, 'code'), (3, 'sleep')]
>>> while q:
next_item = heapq.heappop(q)
print(next_item)
(1, 'eat')
(2, 'code')
(3, 'sleep')
3、queue.PriorityQueue
queue.PriorityQueue内部封装了heapq,不同的是它是线程安全的。在并发环境下应该选择使用PriorityQueue。
>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, 'code'))
>>> q.put((1, 'eat'))
>>> q.put((3, 'sleep'))
>>> while not q.empty():
next_item = q.get()
print(next_item)
(1, 'eat')
(2, 'code')
(3, 'sleep')
0x03 总结一下
很多基础的数据结构在Python中已经实现了的,我们不应该重复造轮子,应该选择这些数据结构来实现业务需求。
collections.deque是一种双向链表,在单线程的情况下,它可以用来实现Stack和Queue。而heapq模块可以帮我们实现高效的优先级队列。
如果要在多并发的情况下使用Stack、Queue和PriorityQueue的话,那么应该选用queue模块下类:
实现Stack的queue.LifoQueue
实现Queue的queue.Queue或multiprocessing.Queue
实现PriorityQueue的queue.PriorityQueue
以上这些类都有put()和get()方法,且get()会在栈/队列为空时阻塞。
0x04 学习资料
Python Tricks: A Buffet of Awesome Python Features
——Dan Bader
好了,以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对脚本之家的支持。
来源:https://juejin.im/post/5d1232d7f265da1bab29bcb5
猜你喜欢
- 在了解XHTML代码规范后,我们就要进行CSS布局。首先先介绍一些CSS的入门知识。如果你已经很熟悉了,可以跳过这一节。CSS是Cascad
- 前言本文主要介绍了关于Python中TCP socket的写法,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧。一、 服务器
- MaxDB和MySQL是独立的数据库管理服务器。系统间的协同性是可能的,通过相应的方式,系统能够彼此交换数据。要想在MaxDB和MySQL之
- 前言使用python直接使用pip install xx时,出现 Could not fetch URL https://pypi.pyth
- Updates(2019.8.14 19:53)吃饭前用这个方法实战了一下,吃完回来一看好像不太行:跑完一组参数之后,到跑下一组参数时好像没
- 本文实例讲述了正则表达式验证IPV4地址功能。分享给大家供大家参考,具体如下:IPV4地址由4个组数字组成,每组数字之间以.分隔,每组数字的
- 我们做WEB程序开发过程中,经常会为了表格Table中的cellSpacing,cellpadding等样式的设置发愁,经常没有办法可想了,
- PHP PDO 事务与自动提交现在通过 PDO 连接上了,在开始进行查询前,必须先理解 PDO 是如何管理事务的。事务支持四大特性(ACID
- 因为一个需求,因为自己想多了一点东西,最后发现了一个问题,一个很奇怪的问题。这个问题我想还是我自己当初想法上的出路导致的吧,但想不通为什么会
- 在JavaScript前端开发工作中,由于浏览器兼容性等问题,我们会经常用到“停止事件冒泡”和“阻止浏览器默认行为”。1..停止事件冒泡//
- MySQL安全性指南(3) 作 者: 晏子2.4 不用GRANT设置用户如果你有一个早于3.22.11的MySQL版本,你不能使用GRANT
- 如今WEB的安全问题影响着整个安全界,SQL注入,跨站脚本攻击等攻击受到了关注。 网络安全问题日益变的更加重要,国内依然有很多主机受到此类安
- 本文实例讲述了RSA实现JS前端加密与PHP后端解密功能。分享给大家供大家参考,具体如下:web前端,用户注册与登录,不能直接以明文形式提交
- Django 分页功能的实现,供大家参考,具体内容如下创建项目创建APP,添加APP这些就不在多说我们这次重点来看到视图函数下面是路由设置视
- 一、概述公司需要通过网页用户认证登录实现上网,网络设备判断当前帐号12小时没有没上网将会自动断开帐号上网,每天早上上班第一件事就是打开用户认
- pandas 中 inplace 参数在很多函数中都会有,它的作用是:是否在原对象基础上进行修改inplace = True:不创建新的对象
- 一: 删除LOG1:分离数据库 企业管理器->服务器->数据库->右键->分离数据库2:删除LOG文件3:附加数据库 企业管理器->服务器-
- 实例如下所示:from xml.etree.cElementTree import ElementTree,Elementimport xl
- MySql5.0以后均支持存储过程,最近有空,研究了一把这个。格式:以下为引用的内容:CREATE PROCEDURE
- 前言激活函数在机器学习中常常用在神经网络隐含层节点与神经网络的输出层节点上,激活函数的作用是赋予神经网络更多的非线性因素,如果不用激励函数,