Python deque详解|极客教程

Python deque详解

在Python中，deque（双端队列）是一个高效的数据结构，它可以在队列的两端插入和删除元素，而且时间复杂度都是O(1)。deque是collections模块中的一个类，需要先导入collections模块才能使用deque。

deque的基本操作

创建deque对象

我们可以使用collections模块中的deque类来创建一个deque对象。下面是一个简单的示例：

from collections import deque

# 创建一个空的deque对象
d = deque()

在deque两端插入元素

我们可以使用append()和appendleft()方法在deque的右端和左端插入元素。下面是一个示例：

# 在右端插入元素
d.append(1)
d.append(2)
print(d)  # 输出: deque([1, 2])

# 在左端插入元素
d.appendleft(0)
print(d)  # 输出: deque([0, 1, 2])

在deque两端删除元素

我们可以使用pop()和popleft()方法从deque的右端和左端删除元素。下面是一个示例：

# 从右端删除元素
x = d.pop()
print(x)  # 输出: 2
print(d)  # 输出: deque([0, 1])

# 从左端删除元素
y = d.popleft()
print(y)  # 输出: 0
print(d)  # 输出: deque([1])

获取deque的长度

我们可以使用len()函数来获取deque中元素的个数。下面是一个示例：

length = len(d)
print(length)  # 输出: 1

deque的应用场景

deque在很多场景下都非常有用。下面我们来看一些常见的应用场景。

实现一个固定长度的队列

有时候我们需要一个长度固定的队列，当队列满了之后再插入元素则会把最早的元素删除掉。我们可以使用deque来实现这样一个固定长度的队列。

from collections import deque

class FixedQueue:
    def __init__(self, max_length):
        self.max_length = max_length
        self.queue = deque(maxlen=max_length)

    def push(self, value):
        self.queue.append(value)

    def pop(self):
        return self.queue.popleft()

q = FixedQueue(3)
q.push(1)
q.push(2)
q.push(3)
print(q.queue)  # 输出: deque([1, 2, 3])

q.push(4)
print(q.queue)  # 输出: deque([2, 3, 4])

实现一个循环队列

循环队列是一种常见的队列数据结构，可以在队列满的时候实现数据循环利用。我们可以使用deque来实现一个循环队列。

from collections import deque

class CircularQueue:
    def __init__(self, max_length):
        self.max_length = max_length
        self.queue = deque(maxlen=max_length)

    def push(self, value):
        self.queue.append(value)

    def pop(self):
        return self.queue.popleft()

    def rotate(self, n):
        self.queue.rotate(n)

q = CircularQueue(3)
q.push(1)
q.push(2)
q.push(3)
print(q.queue)  # 输出: deque([1, 2, 3])

q.rotate(1)
print(q.queue)  # 输出: deque([3, 1, 2])