CODEWITHSUNDEEP
pythondata-structuresmodulo
Yohan
Yohan

Reputation: 409

What does the modulo operator do in this code?

class MyQueue:
​
    def __init__(self, size):
        self.q = [None] * size  # list to store queue elements
        self.capacity = size  # maximum capacity of the queue
        self.front = 0  # front points to the front element in the queue
        self.rear = -1  # rear points to the last element in the queue
        self.count = 0  # current size of the queue
​
    def pop(self):
        if self.is_empty():
            print("Queue Underflow!! Terminating process.")
            exit(1)
​
        print("Removing element…", self.q[self.front])
​
        self.front = (self.front + 1) % self.capacity
        self.count = self.count - 1
​
    def append(self, value):
        if self.is_full():
            print("Queue is full! Terminating process.")
            exit(1)
​
        print("Inserting element…", value)
​
        self.rear = (self.rear + 1) % self.capacity
        self.q[self.rear] = value
        self.count = self.count + 1
​
    def peek(self):
        if self.is_empty():
            print("Queue is empty!! Terminating process.")
            exit(1)
​
        return self.q[self.front]
​
    def size(self):
        return self.count
​
    def is_empty(self):
        return self.size() == 0
​
    def is_full(self):
        return self.size() == self.capacity
​

So I am currently learning Python and came across this example of a Stack data structure implemented using a class and some functions.

The problem I have is that I do not understand what the modulo operator is being used for here. As far as I can tell, Modulo is used to calculate te remainder, so in this example why do we need it for a queue?

Shouldn't it just be we want to add something to the front - so we take one away from the current front counter and add it there?

Upvotes: 0

Views: 141

Answers (1)

relent95
relent95

Reputation: 4731

It's also called a deque(double ended queue) or circular queue. The terms front and rear in that code are inadequate. head and tail are more adequate. When the queue is empty, the head is equal to the tail. When you push into the queue, the tail is increased usually. When you pop from the queue, the head is increased usually. When the head or tail reaches the end of the buffer, it is rewound to the start of the buffer. When the queue is full, the tail is just behind the head usually.

In a circular queue, you don't need to shift elements while popping elements like a stack.(If you implement a naive queue with a list, list.pop(0) results in shifting elements and that's O(N).)

Using a modulo operator for calculating a head or tail index is a trick to rewind an index.

tail = (tail + 1) % N
# The above one line is equivalent to the following.
tail = tail + 1
if tail >= N:
    tail = 0

It's implemented as the collections.deque in the standard library.

Upvotes: 1

Related Questions