Méthode d'implémentation de file d'attente en python (exemple de code)

Ce que cet article vous apporte concerne la méthode d'implémentation des files d'attente en python (exemples de code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Pour Python, il est très simple d'implémenter une classe de file d'attente basée sur des méthodes existantes. Étant donné que la file d'attente nécessite une insertion à une extrémité et une suppression à l'autre extrémité. Évidemment, python dispose de ces deux outils. Pour supprimer la queue de la file d'attente, vous pouvez utiliser pop(0), et pour insérer la tête, vous pouvez utiliser append. C'est très simple à cet égard, mais il faut toujours trouver la solution optimale, n'est-ce pas ? Nous n'utilisons pas la méthode pop, car pour l'implémentation interne de Python, la complexité de cette méthode est O(n). Lorsque nous supprimons le premier élément de la liste, tous les éléments de la liste seront avancés. C'est pourquoi python veut maintenir l'intégrité de la liste

Nous utilisons une table de séquence circulaire pour implémenter. la file d'attente.

L'idée spécifique est la suivante :
Lorsque nous commençons à supprimer depuis le début de la liste, le pointeur de tête suit le point de départ de la zone de l'élément, c'est-à-dire que le pointeur de tête continue de changer vers le retour avec suppression, donc le front est un nœud vide, nous ne le gaspillons pas. Lorsque le pointeur de queue atteint la dernière position de la liste avec l'élément ajouté, le pointeur de queue se déplace vers le premier nœud de la liste (nœud vide). pour s'arrêter, lorsque notre pointeur de tête et notre pointeur de queue convergent, cela signifie que c'est à ce moment-là que toute la liste fixe est utilisée. Ici, nous définissons également une méthode pour étendre l'espace de stockage de la file d'attente, qui est appelée en interne lorsque la file d'attente. est plein, nous appellerons automatiquement cette méthode interne Développer l'espace de la file d'attente.

Implémentation :

Analyse, on peut savoir que

• peut définir un pointeur de tête pour spécifier l'indice de départ de la zone d'élément, self _head. ;

• Définir une variable pour stocker la longueur de la zone de l'élément, self._num

• Une variable pour stocker la longueur de la liste entière , self._len

• , et bien sûr la variable de liste où se trouve la file d'attente, self._list

Jetons un coup d'oeil après avoir défini plusieurs variables Plusieurs jugements :

• Quand self._num = self._len, cela signifie que la file d'attente est pleine à ce moment

• Quand self ._num = 0 Quand, la file d'attente est vide

Une file d'attente supporte plusieurs opérations :

1. Créer une file d'attente vide

2. Déterminer si la file d'attente est vide

3. Obtenir la valeur en haut de la file d'attente

4. Opération de retrait de la file d'attente

5. Opération de mise en file d'attente

6. Nous définissons également une méthode interne pour augmenter la longueur de la liste

Le spécifique la mise en œuvre est la suivante :

# _*_ 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

L'idée est très importante, mais comment la mettre en œuvre n'est pas si importante. Ce sera mieux si vous la mettez en œuvre d'abord et voyez ensuite mes résultats !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!