参考链接&＃xff1a; Python中的双端队列DeQue
Python的强大并不在于它的语法&＃xff0c;而在于它的库&＃xff0c;当你对各种数据结构感到苦恼时&＃xff0c;Python提供了各种开箱即用的数据结构。
数据结构中最常讲授的数据结构有栈、队列、双端队列。
栈是一种特殊的线性表&＃xff0c;它只允许在一端进行插入、删除操作&＃xff0c;这一端被称为栈顶&＃xff08;top&＃xff09;&＃xff0c;另一端则被称为栈底&＃xff08;bottom&＃xff09;。
从栈顶插入一个元素被称为进栈&＃xff0c;将一个元素插入栈顶被称为“压入栈”&＃xff0c;对应的英文说法为push。
从栈顶删除一个元素被称为出栈&＃xff0c;将一个元素从栈顶删除被称为“弹出栈”&＃xff0c;对应的英文说法为pop。对于栈而言&＃xff0c;最先入栈的元素位于栈底&＃xff0c;只有等到上面所有元素出栈之后&＃xff0c;栈底的元素才能出栈。因此栈是一种后进先出&＃xff08;LIFO&＃xff09;的线性表。
图1为栈的操作示意图。 队列也是一种特殊的线性表&＃xff0c;它只允许在表的前端&＃xff08;front&＃xff09;进行删除操作&＃xff0c;只允许在表的后端&＃xff08;rear&＃xff09;进行插入操作。进行插入操作的端称为队尾&＃xff0c;进行删除操作的端称为队头。
对于一个队列来说&＃xff0c;每个元素总是从队列的rear端进入队列&＃xff0c;然后等待该元素之前的所有元素出队之后&＃xff0c;当前元素才能出队。因此&＃xff0c;把队列简称为先进先出&＃xff08;FIFO&＃xff09;的线性表。
队列的示意如图2所示。 双端队列&＃xff08;即此处介绍的deque&＃xff09;代表一种特殊的队列&＃xff0c;它可以在两端同时进行插入、删除操作&＃xff0c;如图3所示。 对于双端队列&＃xff0c;由于它可以从两端分别进入插入、删除操作&＃xff0c;如果程序将所有的插入、删除操作固定在一端进行&＃xff0c;这个双端队列就变成前面介绍的栈&＃xff1b;如果固定在一端只添加元素、在另一端只删除元素&＃xff0c;那它就是队列&＃xff0c;因此&＃xff0c;deque既可当成队列使用&＃xff0c;也可当成栈使用。
deque位于collections包下&＃xff0c;在交互式解释器中先导入collections包&＃xff0c;然后输入[e for e in dir(collections.deque) if not e.startswith(’_’)]来查看deque的全部方法&＃xff0c;可看到如下输出。
>>> from collections import deque
>>> [e for e in dir(deque) if not e.startswith(&＃39;_&＃39;)]
[&＃39;append&＃39;, &＃39;appendleft&＃39;, &＃39;clear&＃39;, &＃39;copy&＃39;, &＃39;count&＃39;, &＃39;extend&＃39;, &＃39;extendleft&＃39;, &＃39;index&＃39;, &＃39;insert&＃39;, &＃39;maxlen&＃39;, &＃39;pop&＃39;, &＃39;popleft&＃39;, &＃39;remove&＃39;, &＃39;reverse&＃39;, &＃39;rotate&＃39;]
从上面方法可以看出&＃xff0c;deque的方法基本都有两个版本&＃xff0c;这就体现了它作为双端队列的特征。deque的左边&＃xff08;left&＃xff09;就相当于它的队列头&＃xff08;front&＃xff09;、右边&＃xff08;right&＃xff09;就相当于它的队列尾&＃xff08;rear&＃xff09;。
append和appendleft&＃xff1a;在deque的右边或左边添加元素&＃xff1b;也就是默认在队列尾添加元素。 pop和popleft&＃xff1a;在deque的右边或左边弹出元素&＃xff1b;也就是默认在队列尾弹出元素。 extend和extendleft&＃xff1a;在deque的右边或左边添加多元素&＃xff1b;也就是默认在队列尾添加多个元素。
deque中clear()方法用法清空队列&＃xff0c;insert()方法则是线性表的方法&＃xff0c;用于在指定位置插入元素。
假如程序要把deque当成栈使用&＃xff0c;意味着只在一端添加、删除元素&＃xff0c;因此调用append和pop方法即可。例如如下代码。
&＃39;&＃39;&＃39;
遇到问题没人解答&＃xff1f;小编创建了一个Python学习交流QQ群&＃xff1a;857662006
寻找有志同道合的小伙伴&＃xff0c;互帮互助,群里还有不错的视频学习教程和PDF电子书&＃xff01;
&＃39;&＃39;&＃39;
from collections import deque
stack &＃61; deque((&＃39;Kotlin&＃39;, &＃39;Python&＃39;))
# 元素入栈
stack.append(&＃39;Erlang&＃39;)
stack.append(&＃39;Swift&＃39;)
print(&＃39;stack中的元素&＃xff1a;&＃39; , stack)
# 元素出栈&＃xff0c;后添加的元素先出栈
print(stack.pop())
print(stack.pop())
print(stack)
运行上面程序&＃xff0c;可看到如下结果。
stack中的元素&＃xff1a;deque([&＃39;Kotlin&＃39;, &＃39;Python&＃39;, &＃39;Erlang&＃39;, &＃39;Swift&＃39;])
Swift
Erlang
deque([&＃39;Kotlin&＃39;, &＃39;Python&＃39;])
从上面运行结果可以看出&＃xff1a;程序最后入栈的元素’Swift’最先出栈&＃xff0c;这体现了栈的LIFO的特征。
假如程序需要把deque当成队列使用&＃xff0c;意味着一端只是用来添加元素&＃xff0c;另一端只是用于删除元素&＃xff0c;因此调用append、popleft方法组合即可。例如如下代码。
&＃39;&＃39;&＃39;
遇到问题没人解答&＃xff1f;小编创建了一个Python学习交流QQ群&＃xff1a;857662006
寻找有志同道合的小伙伴&＃xff0c;互帮互助,群里还有不错的视频学习教程和PDF电子书&＃xff01;
&＃39;&＃39;&＃39;
from collections import deque
q &＃61; deque((&＃39;Kotlin&＃39;, &＃39;Python&＃39;))
# 元素加入队列
q.append(&＃39;Erlang&＃39;)
q.append(&＃39;Swift&＃39;)
print(&＃39;q中的元素&＃xff1a;&＃39; , q)
# 元素出队列&＃xff0c;先添加的元素先出队列
print(q.popleft())
print(q.popleft())
print(q)
运行上面程序&＃xff0c;可看到如下结果。
q中的元素&＃xff1a;deque([&＃39;Kotlin&＃39;, &＃39;Python&＃39;, &＃39;Erlang&＃39;, &＃39;Swift&＃39;])
Kotlin
Python
deque([&＃39;Erlang&＃39;, &＃39;Swift&＃39;])
从上面运行结果可以看出&＃xff1a;程序先添加的元素’Kotlin’最先出队列&＃xff0c;这体现了栈的FIFO的特征。
此外&＃xff0c;deque还有一个rotate()方法&＃xff0c;该方法的作用是将队列的队尾元素移动到队头来&＃xff0c;使之首尾相连。例如如下程序。
&＃39;&＃39;&＃39;
遇到问题没人解答&＃xff1f;小编创建了一个Python学习交流QQ群&＃xff1a;857662006
寻找有志同道合的小伙伴&＃xff0c;互帮互助,群里还有不错的视频学习教程和PDF电子书&＃xff01;
&＃39;&＃39;&＃39;
from collections import deque
q &＃61; deque(range(5))
print(&＃39;q中的元素&＃xff1a;&＃39; , q)
# 执行旋转&＃xff0c;使之首尾相连
q.rotate()
print(&＃39;q中的元素&＃xff1a;&＃39; , q)
# 再次执行旋转&＃xff0c;使之首尾相连
q.rotate()
print(&＃39;q中的元素&＃xff1a;&＃39; , q)
-------------------------------------------
运行上面程序&＃xff0c;可以看到如下输出。
q中的元素&＃xff1a;deque([0, 1, 2, 3, 4])
q中的元素&＃xff1a;deque([4, 0, 1, 2, 3])
q中的元素&＃xff1a;deque([3, 4, 0, 1, 2])
从上面程序运行结果来看&＃xff0c;每次执行rotate()方法&＃xff0c;deque的队尾元素都会被移到队头&＃xff0c;这样就形成了首尾相连的效果。
京公网安备 11010802041100号