专栏首页疯狂软件李刚Python的双端队列deque

Python的双端队列deque

导读

Python的强大并不在于它的语法,而在于它的库,当你对各种数据结构感到苦恼时,Python提供了各种开箱即用的数据结构。

数据结构中最常讲授的数据结构有栈、队列、双端队列。

栈是一种特殊的线性表,它只允许在一端进行插入、删除操作,这一端被称为栈顶(top),另一端则被称为栈底(bottom)。

从栈顶插入一个元素被称为进栈,将一个元素插入栈顶被称为“压入栈”,对应的英文说法为push。

从栈顶删除一个元素被称为出栈,将一个元素从栈顶删除被称为“弹出栈”,对应的英文说法为pop。对于栈而言,最先入栈的元素位于栈底,只有等到上面所有元素出栈之后,栈底的元素才能出栈。因此栈是一种后进先出(LIFO)的线性表。

图1为栈的操作示意图。

图1 栈的操作

队列也是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。

对于一个队列来说,每个元素总是从队列的rear端进入队列,然后等待该元素之前的所有元素出队之后,当前元素才能出队。因此,把队列简称为先进先出(FIFO)的线性表。

队列的示意如图2所示。

图2 队列

双端队列(即此处介绍的deque)代表一种特殊的队列,它可以在两端同时进行插入、删除操作,如图3所示。

图3 双端队列示意

对于双端队列,由于它可以从两端分别进入插入、删除操作,如果程序将所有的插入、删除操作固定在一端进行,这个双端队列就变成前面介绍的栈;如果固定在一端只添加元素、在另一端只删除元素,那它就是队列,因此,deque既可当成队列使用,也可当成栈使用。

deque位于collections包下,在交互式解释器中先导入collections包,然后输入[e for e in dir(collections.deque) if not e.startswith('_')]来查看deque的全部方法,可看到如下输出。

>>> from collections import deque
>>> [e for e in dir(deque) if not e.startswith('_')]
['append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft', 'index', 'insert', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', 'rotate']

从上面方法可以看出,deque的方法基本都有两个版本,这就体现了它作为双端队列的特征。deque的左边(left)就相当于它的队列头(front)、右边(right)就相当于它的队列尾(rear)。

  • append和appendleft:在deque的右边或左边添加元素;也就是默认在队列尾添加元素。
  • pop和popleft:在deque的右边或左边弹出元素;也就是默认在队列尾弹出元素。
  • extend和extendleft:在deque的右边或左边添加多元素;也就是默认在队列尾添加多个元素。

deque中clear()方法用法清空队列,insert()方法则是线性表的方法,用于在指定位置插入元素。

假如程序要把deque当成栈使用,意味着只在一端添加、删除元素,因此调用append和pop方法即可。例如如下代码。

from collections import deque
stack = deque(('Kotlin', 'Python'))
# 元素入栈
stack.append('Erlang')
stack.append('Swift')
print('stack中的元素:' , stack)
# 元素出栈,后添加的元素先出栈
print(stack.pop())
print(stack.pop())
print(stack)

运行上面程序,可看到如下结果。

stack中的元素:deque(['Kotlin', 'Python', 'Erlang', 'Swift'])
Swift
Erlang
deque(['Kotlin', 'Python'])

从上面运行结果可以看出:程序最后入栈的元素'Swift'最先出栈,这体现了栈的LIFO的特征。

假如程序需要把deque当成队列使用,意味着一端只是用来添加元素,另一端只是用于删除元素,因此调用append、popleft方法组合即可。例如如下代码。

from collections import deque

q = deque(('Kotlin', 'Python'))
# 元素加入队列
q.append('Erlang')
q.append('Swift')
print('q中的元素:' , q)
# 元素出队列,先添加的元素先出队列
print(q.popleft())
print(q.popleft())
print(q)

运行上面程序,可看到如下结果。

q中的元素:deque(['Kotlin', 'Python', 'Erlang', 'Swift'])
Kotlin
Python
deque(['Erlang', 'Swift'])

从上面运行结果可以看出:程序先添加的元素'Kotlin'最先出队列,这体现了栈的FIFO的特征。

此外,deque还有一个rotate()方法,该方法的作用是将队列的队尾元素移动到队头来,使之首尾相连。例如如下程序。

from collections import deque

q = deque(range(5))
print('q中的元素:' , q)
# 执行旋转,使之首尾相连
q.rotate()
print('q中的元素:' , q)
# 再次执行旋转,使之首尾相连
q.rotate()
print('q中的元素:' , q)
运行上面程序,可以看到如下输出。
q中的元素:deque([0, 1, 2, 3, 4])
q中的元素:deque([4, 0, 1, 2, 3])
q中的元素:deque([3, 4, 0, 1, 2])

从上面程序运行结果来看,每次执行rotate()方法,deque的队尾元素都会被移到队头,这样就形成了首尾相连的效果。

本文分享自微信公众号 - 疯狂软件李刚(fkbooks),作者:疯狂软件李刚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python的堆操作,是不是要掌握一下

    Python的强大并不在于它的语法,而在于它的库,当你对各种数据结构感到苦恼时,Python提供了各种开箱即用的数据结构。

    疯狂软件李刚
  • MyBatis的“基于嵌套select”映射的剖析

    本文详细分析了MyBatis中“基于嵌套select”映射策略的性能缺陷、并给出了具体的实施建议,本文适合对MyBatis有一定使用经验的读者阅读,对MyBat...

    疯狂软件李刚
  • MyBatis一级缓存的脏数据——MyBatis迷信者,清醒点之二

    本文详细分析了MyBatis中“一级缓存”在实际项目中如何产生脏数据,并并给出了具体的实施建议,本文适合对MyBatis有1年以上使用经验的开发者阅读,对MyB...

    疯狂软件李刚
  • python双端队列deque

    由于deque是一种序列容器,因此同样支持list的一些操作,如用getitem()检查内容,确定长度,以及通过匹配标识从序列中间删除元素。

    用户2936342
  • 谷歌AlphaZero发表在最新一期《Science》上的几点解读

    谷歌旗下的deepmind公司又在Science上发表的论文,论文描述了AlphaZero如何快速学习每个游戏,如何从随机对弈开始训练,在没有先验知识、只知...

    用户1594945
  • 深入理解Dubbo源码(一),如何高效的阅读Dubbo框架源码

    这几天一直在探索Dubbo源码,本来也想写一系列Dubbo源码分析文章的,但觉得没必要,因为官方文档的源码导读就介绍了怎么去阅读Dubbo的源码,今年也出了本书...

    Java艺术
  • 04-RabbitMQ常用的六种模型以及在SpringBoot中的应用

    我们并不推荐RPC式的mq调用,这么做完全没有发挥mq异步削峰的作用。如果有使用RPC的需求,请移步SpringCloud或者Dubbo。

    qubianzhong
  • 版心和布局流程

    阅读报纸时容易发现,虽然报纸中的内容很多,但是经过合理地排版,版面依然清晰、易读。同样,在制作网页时,要想使页面结构清晰、有条理,也需要对网页进行“排版”。

    星辰_大海
  • 边缘计算与智能服务

    随着信息化的不断发展,人们对互联网提出了更高的生活需求,5G、人工智能、物联网等新兴技术应运而生,万物互联已经成为一种新的发展趋势。网络技术不再只停留于原来的数...

    边缘计算
  • tf.io

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    于小勇

扫码关注云+社区

领取腾讯云代金券