Implementation of Data Structure Cyclic Queue Operation Method in Python

Today we come to the Circular Queue section 1. In the previous article, I introduced the implementation of queues with the list that comes with python, which is the simplest implementation method.

However, as we all know, deleting the first element in the list is not the same as deleting the last one. If you delete the first element in the list, all the elements after it will be moved. So when the list is extremely long, the cost is obvious. The circular queues we introduced in this article can avoid this problem, as can the linked list method we mentioned in the previous article.

Next, let's introduce circular queues.

Follow the bad queue

Circular queue is to connect ordinary queues head and tail to form a ring, and set head and tail pointers respectively to indicate the head and tail of the queue. Whenever we insert an element, the tail pointer moves back one bit. Of course, here the maximum length of our queue is defined in advance. When we pop up an element, the head pointer moves back one bit.

In this way, there is no delete operation in the list, only modify operation, thus avoiding the problem of high cost caused by deleting previous nodes.

Ok, without saying much, let's use code to realize 1

class Loopqueue:
 def __init__(self, length):
  self.head = 0
  self.tail = 0
  self.maxSize = length
  self.cnt = 0
  self.__list = [None]*length

Here again, we define a queue class. When instantiating a circular queue, we require to specify the size of the queue. In addition to the first and last pointers and the maximum length of the queue, we also declare an attribute cnt representing the current length of the queue.

Next, we add one operation to the queue:

Empty judgment

def isEmpty(self):
  return self.cnt == 0

Sentence to fulfillment

def isFull(self):
  return self.cnt == self.maxSize

Add Element

def push(self, data):
  if self.isFull():
   return False
  if self.isEmpty():
   self.__list[0] = data
   self.head = 0
   self.tail = 0
   self.cnt = 1
   return True
  self.tail = (self.tail+1)%self.maxSize
  self.cnt += 1
  self.__list[self.tail] = data
  return True

Eject element

def pop(self):
  if self.isEmpty():
   return False
  data = self.__list[self.head]
  self.head = (self.head+1)%self.maxSize
  self.cnt -= 1
  return data

Empty the queue

def clear(self):
  self.head = 0
  self.tail = 0
  self.cnt = 0
  return True

Define len and print functions

def __len__(self):
  return self.cnt

 def __str__(self):
  s = ''
  for i in range(self.cnt):
   index = (i + self.head) % self.maxSize
   s += str(self.__list[index])+' '
  return s

OK, our circular queue class is defined. If you read the article about queues, you will find that the operation of circular queue is logically similar to that of ordinary queue.

Summarize