Python双端队列deque的实现

Python双端队列deque的实现

双端队列deque即"double-ended queue"，是一种具有队列和栈的性质的数据结构。deque可以从队列的两端插入和删除元素。Python官方提供了collections模块中的deque数据类型，可以实现双端队列的操作。本文将详细讲解如何使用Python中的deque来实现双端队列的操作。

创建deque

首先，需要导入collections模块，然后创建一个空的deque对象。

import collections

deque_example = collections.deque()

添加元素

从右边添加

可以使用deque对象的append()方法，将元素添加到双端队列的右边。

import collections

deque_example = collections.deque()

deque_example.append(10)
deque_example.append(20)

print(deque_example)
# 输出: deque([10, 20])

从左边添加

使用deque对象的appendleft()方法，将元素添加到双端队列的左边。

import collections

deque_example = collections.deque()

deque_example.appendleft(10)
deque_example.appendleft(20)

print(deque_example)
# 输出: deque([20, 10])

删除元素

从右边删除

可以使用deque对象的pop()方法，将双端队列的右侧元素删除并返回。

import collections

deque_example = collections.deque([10, 20, 30])

deque_example.pop()

print(deque_example)
# 输出: deque([10, 20])

从左边删除

使用deque对象的popleft()方法，将双端队列的左侧元素删除并返回。

import collections

deque_example = collections.deque([10, 20, 30])

deque_example.popleft()

print(deque_example)
# 输出: deque([20, 30])

查看队列元素

可以直接打印deque对象，也可以使用迭代器（iterator）的方式来访问双端队列中的元素。

import collections

deque_example = collections.deque([10, 20, 30])

# 直接打印双端队列对象
print(deque_example)
# 输出: deque([10, 20, 30])

# 使用迭代器来访问双端队列中的元素
for i in deque_example:
    print(i)
# 输出:
# 10
# 20
# 30

示例1

下面是一个简单的双端队列实现的示例，能够将整数列表按顺序压入双端队列并从中间弹出。

import collections

deq = collections.deque()
data = [10, 20, 30, 40, 50]

for i in data:
    deq.append(i)

while len(deq) != 0:
    print(deq.popleft())
    if len(deq) != 0:
        print(deq.pop())

输出：

10
50
20
40
30

说明：

在上例中，我们首先创建了一个空的双端队列deq，并且创建了一个整形列表data。接下来我们将data中的所有元素按顺序压入双端队列deq中。

接下来，我们使用while循环来将队列中的元素依次取出，并交替从左边和右边弹出，直到双端队列deq为空。

示例2

下面是一个基于双端队列实现的循环队列Deque队列示例，能够支持添加数据、弹出数据、队列旋转等操作。

import collections

maximum_size = 5
deque_example = collections.deque(maxlen=maximum_size)

for _ in range(maximum_size):
    deque_example.append(101)

print(deque_example)

deque_example.appendleft(102)
print(deque_example)

deque_example.rotate(2)
print(deque_example)

deque_example.rotate(-1)
print(deque_example)

输出：

deque([101, 101, 101, 101, 101], maxlen=5)
deque([102, 101, 101, 101, 101], maxlen=5)
deque([101, 101, 102, 101, 101], maxlen=5)
deque([101, 102, 101, 101, 101], maxlen=5)

说明：

在上例中，我们创建了一个最大长度为5的双端队列deque_example。通过使用for循环将5个元素插入到队列中。接下来，我们使用appendleft(102)函数在左边插入整数102。然后，我们使用rotate(2)函数将队列向右旋转两个元素。最后，我们使用rotate(-1)函数将队列向左旋转一个元素。

通过此例，我们可以看到deque队列的跨结构灵活性，即可以作为队列而使用，也可以作为栈而使用。在此基础上旋转移位等操作也能方便地进行。