Implementation method of queue in python (code example)

What this article brings to you is about the implementation method of queues in Python (code examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

#For Python, it is very simple to implement a queue class based on existing methods. Since the queue requires insertion at one end and deletion at the other end. Obviously, python has these two tools. To delete the tail of the queue, you can use pop(0), and to insert the head, you can use append. It's really simple in this respect, but you always have to find the optimal solution, right? So we don’t use the pop method, because for python’s internal implementation, the complexity of this method is O(n). Why? When we delete the first element of the list, all elements of the list will be moved forward. This is why python wants to maintain the integrity of the list.

We use a circular sequence table to implement the queue.

The specific idea is as follows:
When we start deleting from the front of the list, the head pointer follows the starting point of the element area, that is, the head pointer continues to change with deletion to the back, then the front is empty Node, we do not waste it. When the tail pointer reaches the last position of the list with the added element, the tail pointer moves to the first node of the list (empty node). As for stopping, when our head pointer and tail pointer When converging, it means that this is when the entire fixed list is used up. Here we also define a method to expand the storage space of the queue, which is called internally. When the queue is full, we will automatically call this internal method. Expand queue space.

Implementation:

After analysis, we can know that

• can define a head pointer to specify the starting subscript of the element area, self. _head;

• Define a variable to store the length of the element area, self._num

• A variable to store the length of the entire list , self._len

• Of course, there is also the list variable where the queue is located, self._list

After defining several variables, let’s take a look Several judgments:

• When self._num = self._len, it means that the queue is full at this time

• When self._num = 0 When, the queue is empty

A queue supports several operations:

1. Create an empty queue

2. Judge whether the queue is empty

3. Get the value at the top of the queue

4. Dequeue operation

5. Enqueuing operation

6. We also define an internal method to increase the length of the list

The specific implementation is as follows:

# _*_ coding: utf-8 _*_

class OverFlowError(ValueError):
    pass

class Queue:
    def __init__(self, init_len=0):
        self._len = init_len
        self._list = [0] * init_len
        self._num = 0 # 计数元素
        self._head = 0 # 头指针

    def is_empty(self):
        return self._num == 0

    def peek(self):
        if self._num == 0:
            raise OverFlowError("取队列首位值，但队列为空")
        return self._list[self._head]

    def enqueue(self, elem):
        if self._num = self._len:
            self._extend()
        self._list[(self._head + self._num) % self._len] = elem
        self._num += 1

    def dequeue(self):
        if self._num == 0:
            raise OverFlowError("队列首位出队列，但队列为空")
        e = self._list[self._head]
        self._head = (self._head + 1) % self._len
        self._num -= 1
        return e

    def _extend(self):
        new_len = self._len * 2
        new_list = [0] * new_len
        i = 0
        p = self._head
        while not p == (self._head + self._num) % self._len:
            new_list[i] = self._list[p]
            i += 1
        self._len = new_len
        self._list = new_list
        self._head = 0

The idea is very important, but how to implement it is not so important. It will be better if you implement it first and then see my results!

The above is the detailed content of Implementation method of queue in python (code example). For more information, please follow other related articles on the PHP Chinese website!