Почему для вычисления хвоста 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 шт):

Автор решения: MBo

Дело в том, что очередь циклическая. Если происходили удаления из начала очереди, то индекс head смещается, и, если список заполнен до конца, то новые элементы в конец очереди будут добавляться с начала списка, очередь как бы заворачивается в кольцо (не всегда полное).

Проще всего сделать такой переход с помощью модульной арифметики по модулю размера списка.

Использование циклического хранения позволяет использовать один неизменный список или массив, если размер очереди ограничен, а если размер может расти, то количество перераспределений памяти будет сравнительно невелико.

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

P.S. В вашей реализации нет операции получения текущего размера очереди (например, Count) или более важной - пустая ли очередь (isEmpty), но добавить её нетрудно.

→ Ссылка