preface

  • Implementing Queue structures in Python can be done with the off-the-shelf library Queue, but in order to understand Queue data structures, I decided to go through the code myself.
  • Ordinary sequentially stored queues can be implemented with Lists in Python, as long as the inbound and outbound directions are controlled, and space can be dynamically allocated when the list is full. Given that there is only a limited amount of storage space, circular queues make better use of the remaining space.

1 Principle of circular queue

1.1 Take chestnuts for example

For example, take a circular queue with 5 unit Spaces:

  1. First connect the head and tail of the ordinary queue, making it a ring. To distinguish the head and tail, set two indexes, front and rear, pointing to the current head and rear, respectively. If front and rear point to the same datafront=rear, the queue is empty. Note that the data space that rear points to must be None, which means you should not fill in the data at the end of the queue.

  1. Move rear one bit after inserting data:

  1. When all data is inserted, as shown in the following figure, the end of the queue is empty:

  1. In order to be able to insert new data, you have to queue the data, make room, and then you can make rear point past. Note that the front moves backwards:

  1. Now here’s the important thing: insert data 99, and the queued data will fill the empty space, while rear loops to the first position:

  1. And the following process is similar, first to free up space, and then the queue data, to achieve the full use of space.

1.2 Discriminant conditions

If the queue is empty or full, the queue is empty.

  • Check whether the queue is empty:front = rear
  • To determine if the queue is full:(rear+1) % maxsize == front(maxsize is the queue length)

It is easy to understand whether the reading queue is empty, so I will not go into details. However, the condition for determining whether a queue is full is very tricky and needs to be discussed in two cases:

  1. When front is in front of rear:

Put a few numbers into the condition, and you can see that only if front is in the first position and rear is in the last position, then the queue is full, and when rear is in the other position, actually (rear+1) % maxsize is equivalent to rear+1, In addition, when rear is in the last position, (rear+1) % maxsize will make rear=0, which means that rear jumps to the first position

  1. When front is behind rear:

(front+1) % maxsize (front+1) % maxsize (front+1) % maxsize (front+1) % maxsize (front+1) % maxsize

  • And one last thing, the reason why rear has to point to empty is to prevent conditions, rightfront = rearInvalid. If you insert data at rear, it will cause the rear index to move back and overlap with the front index. In this case, the queue is not empty, and the criterion will be invalid.

2 Python code implementation

2.1 Creating a circular queue

Based on the analysis above, create a circular queue. The queue space is filled with None, and the two indexes are initially 0 (other numbers not larger than maxsize should also be allowed).

# Circular queue
class rqueue:
    def __init__(self, maxsize) :
        self.queue = [None]*(maxsize)
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0
Copy the code

2.2 Implementation of queue entry, queue exit and view

In light of the above analysis, it should be easy to understand that “print queue” is a function that displays the queue elements in sequence without None

# Circular queue
class rqueue:
    def __init__(self, maxsize) :
        self.queue = [None]*(maxsize)
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0

    # team
    def push(self, value) :        
        if (self.rear+1) % self.maxsize == self.front:
            print("List full")
        else:
            self.queue[self.rear] = value
            self.rear = (self.rear+1) % self.maxsize

    # the team
    def pop(self) :
        if self.front == self.rear:
            print("List is empty")
        else:
            out = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front+1) % self.maxsize
            return out

    Display queue structure
    def traverse(self) :
        return self.queue

    # Print queue
    def show(self) :
        alist = []
        if self.front == self.rear:
            return alist
        if self.front < self.rear:
            for i in range(self.front, self.rear+1) :ifself.queue[i] ! =None:
                    alist.append(self.queue[i])
        else:
            for i in list(range(self.front, self.maxsize)) + list(range(0, self.rear+1)) :ifself.queue[i] ! =None:
                    alist.append(self.queue[i])
        return alist
Copy the code

2.3 Test

  • Start by creating a circular queue of six units, and you can see that the last queue is None
Create a queue and fill it with elements
a = rqueue(6)
a.push(3)
a.push(5)
a.push(0)
a.push(1)
a.push(9)
Copy the code
View the queue structure
a.traverse()
> [3.5.0.1.9.None]
Copy the code
# Print queue
a.show()
> [3.5.0.1.9]
Copy the code
  • Take two elements out of the queue and then two elements in the queue, and you can see that the head of the queue is at 0 and the end of the queue is at 98
a.pop()
a.pop()
a.push(99)
a.push(98)
Copy the code
View the queue structure
a.traverse()
> [98.None.0.1.9.99]
Copy the code
# Print queue
a.show()
> [0.1.9.99.98]
Copy the code