主页 / 问题 / 1598022
Accepted
gw gw
Asked:2024-10-28 08:21:31 +0000 UTC2024-10-28 08:21:31 +0000 UTC

为什么要使用模运算来计算循环队列的尾部？

  • 772

我发现了这个实现循环队列的例子，但我不太明白 的含义 if((self.tail + 1) % self.size == self.head)，如果你可以使用队列大小：(self.tail == self.size - 1)或者也可以在增加变量的(self.tail < self.size)情况下更改它。也许有一些关于数组溢出的主题，我只是不太明白如何进行调试，因为我使用ide并且不明白如何以常规方式进行调试。elsetailAtomcmd

import random

class MyCircularQueue():
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.head = self.tail = -1

    def enqueue(self, data):
        if((self.tail + 1) % self.size == self.head):
            print("The queue is full\n")
        elif (self.head) == -1:
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else:
            self.tail = (self.tail +1) % self.size
            self.queue[self.tail] = data

    def dequeue(self):
        if(self.head == -1):
            print("The queue is empty\n")
        elif(self.head == self.tail):
            temp = self.queue[self.head]
            self.head = -1
            self.tail = -1
            return temp
        else:
            temp = self.queue[self.head]
            self.head = (self.head + 1) % self.size
            return temp

    def printqueue(self):
        if(self.head == -1):
            print("Is empty, i cant print\n")

        elif(self.tail >= self.head):
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end = " ")
            print()
        else:
            for i in range(self.head, self.size):
                print(self.queue[i], end = " ")
            for i in range(0, self.tail + 1):
                print(self.queue[i], end = " ")
            print()

que = MyCircularQueue(5)
for x in range(que.size):
    que.enqueue(random.randint(1, 10))

que.printqueue()

UPD：我将条件更改为self.tail == self.size - 1，并将增量设置为self.tail。显示队列后，发现没有添加新元素，并显示队列已满的消息。我决定更改输出，不显示元素本身，而是显示其在队列中的索引。事实证明，删除是从左到右进行的，添加是从右侧进行的。

Before Delete: 0 1 2 3 4 After Delete: 1 2 3 4 After additional number: 1 2 3 4 0

事实证明，如果您设置增量，则它tail不会重置，并且始终具有适合新条件的最后一个值。

UPD2：在本文中找到了方法实现的示例isEmpty()

python

1 个回答

  1. Best Answer

    重点是队列是循环的。如果从队列的开头开始有删除，那么索引head会移动，如果列表被填满到末尾，那么队列末尾的新元素将从列表的开头添加，队列似乎包裹在一个环中（并不总是完整的）。

    实现这种转换的最简单方法是使用模算术对列表的大小进行模运算。

    如果队列大小有限，则使用循环存储允许您使用单个不可变列表或数组，并且如果大小可以增长，则内存重新分配的次数将相对较小。

    0 1 2 3 4 . .
^
. . 2 3 4 5 6
    ^
7 . 2 3 4 5 6
    ^

    PS 在您的实现中没有任何操作来获取队列的当前大小（例如，Count）或更重要的操作 - 队列是否为空（isEmpty），但添加它并不困难。

    • 1

相关问题