[转载]Python的双端队列deque

参考链接&＃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;这样就形成了首尾相连的效果。