Python中如何实现双端队列和循环队列的比较

2023-04-11 00:00:00 队列循环如何实现

双端队列和循环队列都是队列的一种实现方式，它们在操作上有所不同。

双端队列是一种具有队列和栈的性质的数据结构，它支持在队列的两端插入和删除元素，并且可以实现栈的功能。在Python中，我们可以使用collections模块中的deque类来实现双端队列。

示例代码：

from collections import deque

# 创建双端队列
d = deque()

# 在队首添加元素
d.appendleft('pidancode.com')

# 在队尾添加元素
d.append('皮蛋编程')

# 从队首删除元素
d.popleft()

# 从队尾删除元素
d.pop()

循环队列是通过数组实现的一种先进先出的数据结构，与普通队列不同的是，循环队列的队尾指针可以“循环”回到数组的第一个位置，形成一个环状结构，从而节省数组的空间。在Python中，可以使用列表来模拟循环队列。

示例代码：

class CircularQueue:
    def __init__(self, k):
        self.k = k
        self.q = [0] * k
        self.head = 0
        self.tail = 0

    def enqueue(self, value):
        if self.isFull():
            return False
        self.q[self.tail] = value
        self.tail = (self.tail + 1) % self.k
        return True

    def dequeue(self):
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.k
        return True

    def getFront(self):
        if self.isEmpty():
            return -1
        return self.q[self.head]

    def getRear(self):
        if self.isEmpty():
            return -1
        return self.q[(self.tail - 1 + self.k) % self.k]

    def isEmpty(self):
        return self.head == self.tail

    def isFull(self):
        return (self.tail + 1) % self.k == self.head

# 测试循环队列
q = CircularQueue(5)
q.enqueue('pida')
q.enqueue('ncode')
q.enqueue('co')
q.enqueue('m')
print(q.getFront())
print(q.getRear())
q.dequeue()
q.dequeue()
q.enqueue('pi')
q.enqueue('d')
print(q.getFront())
print(q.getRear())

在测试上述代码时，我们创建了一个循环队列对象q，其初始化大小为5。然后，我们向队列中依次添加了4个元素，分别是“pida”，“ncode”，“co”和“m”。接着，我们分别测试了队列的getFront、getRear、dequeue和enqueue方法，并输出它们的返回值。

相关文章