Почему для вычисления хвоста circual queue используется модульная арифметика
Нашел данный пример реализации цикличной очереди, однако не совсем понимаю смысл от if((self.tail + 1) % self.size == self.head)
, если можно использовать размер очереди: (self.tail == self.size - 1)
или (self.tail < self.size)
и также изменить в кейсе else
на инкремент переменной tail
. Возможно есть какая-то тема с переполнением массива, просто не совсем понимаю как сделать откладку, т.к пользуюсь ide Atom
и не понимаю как в обычной cmd
это сделать.
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()
Ответы (1 шт):
Дело в том, что очередь циклическая. Если происходили удаления из начала очереди, то индекс head
смещается, и, если список заполнен до конца, то новые элементы в конец очереди будут добавляться с начала списка, очередь как бы заворачивается в кольцо (не всегда полное).
Проще всего сделать такой переход с помощью модульной арифметики по модулю размера списка.
Использование циклического хранения позволяет использовать один неизменный список или массив, если размер очереди ограничен, а если размер может расти, то количество перераспределений памяти будет сравнительно невелико.
0 1 2 3 4 . .
^
. . 2 3 4 5 6
^
7 . 2 3 4 5 6
^
P.S. В вашей реализации нет операции получения текущего размера очереди (например, Count
) или более важной - пустая ли очередь (isEmpty
), но добавить её нетрудно.