[GO] Module d'implémentation de file d'attente et Python "deque"

Il semble préférable d'utiliser une structure de données appelée file d'attente lors de la mise en œuvre de la recherche de priorité de largeur, donc Cette fois, j'ai regardé dans la file d'attente.

Qu'est-ce qu'une file d'attente

La file d'attente, ou file d'attente, est l'une des structures de données de base d'un ordinateur. Il contient les données dans une structure de liste premier entré, premier sorti. Lors de la récupération des données de la file d'attente, les données qui ont été insérées en premier sont récupérées dans l'ordre. Mettre des données dans une file d'attente s'appelle mettre en file d'attente, et les retirer s'appelle dequeue. (De Wikipedia)

La figure montre une structure de données avec la structure suivante.

L'image est comme un cylindre. Les données peuvent être placées dans la file d'attente derrière la file d'attente (mise en file d'attente), Les données peuvent être récupérées depuis le début de la file d'attente (dequeue). En raison de la structure, les données qui peuvent être récupérées sont dans l'ordre dans lequel elles sont mises en file d'attente. La figure ci-dessous montre la mise en file d'attente et le retrait de la file d'attente.

Comment implémenter en Python

Pour implémenter une file d'attente en Python, utilisez le type ** deque ** du module ** collections **. Bien qu'il s'agisse de ce type deque, il a une structure de données qui a une fonction de pile en plus d'une file d'attente et peut être utilisé comme une pile en fonction de la façon dont il est utilisé. Cette fois, l'explication est basée sur l'hypothèse qu'elle sera utilisée comme file d'attente.

Créer une file d'attente

Importez deque pour créer un objet de file d'attente.

>>> from collections import deque
>>> 
>>> a=deque()
>>> 

Ajout d'éléments à la file d'attente

Pour ajouter un élément à deque, utilisez la fonction ** append ** (). La fonction d'ajout ajoute un élément du côté droit de la file d'attente. Ce n'est pas l'utilisation d'origine de la file d'attente, mais pour ajouter à partir de la gauche, utilisez la fonction ** appendleft ** ().

>>> a
deque([])
>>> 
>>> a.append(1)
>>> a
deque([1])
>>> 
>>> a.append(2)
>>> a
deque([1, 2])
>>> 
>>> a.appendleft(3)
>>> a
deque([3, 1, 2])
>>> 

Ajouter un autre élément de liste à la file d'attente à la fois

Si vous souhaitez ajouter des éléments d'une autre liste à la file d'attente en une seule fois, utilisez la fonction ** extend **. Si vous souhaitez ajouter à partir du côté gauche de la file d'attente, utilisez la fonction ** extendleft **. (Les éléments à gauche de la liste sont ajoutés à la file d'attente dans l'ordre.)

>>> a
deque([1])
>>> 
>>> b=[2,3,4]
>>> 
>>> a.extend(b)
>>> 
>>> a
deque([1, 2, 3, 4])
>>> 
>>> a.extendleft(b)
>>> 
>>> a
deque([4, 3, 2, 1, 2, 3, 4])
>>> 

Extraire / supprimer des éléments de la file d'attente

Utilisez la fonction ** pop ** pour récupérer des éléments de deque. La fonction pop supprime un élément du côté droit du deque et renvoie cet élément. Si vous souhaitez extraire un élément du côté gauche de deque, utilisez la fonction ** popleft **.

De plus, si vous souhaitez supprimer un élément spécifique de deque, utilisez la fonction ** remove **. Utilisez deque.remove (x) pour supprimer le premier x qui apparaît dans le deque.

>>> a
deque([3, 1, 2])
>>> 
>>> a.pop()
2
>>> a
deque([3, 1])
>>> 
>>> a.popleft()
3
>>> a
deque([1])
>>> 
>>> 
>>> a.append(2)
>>> a.append(2)
>>> a.append(3)
>>> 
>>> 
>>> a
deque([1, 2, 2, 3])
>>> 
>>> a.remove(2)
>>> a
deque([1, 2, 3])
>>> 

Supprimer tous les éléments de la file d'attente

Utilisez la fonction ** clear ** pour supprimer tous les éléments de la file d'attente.

>>> a
deque([1, 2, 3])
>>> 
>>> a.clear()
>>> 
>>> a
deque([])
>>> 

Inverser l'ordre des éléments dans la file d'attente

Utilisez la fonction ** reverse ** pour inverser l'ordre des éléments dans la file d'attente.

>>> a
deque([1, 2, 3, 4])
>>> 
>>> a.reverse()
>>> 
>>> a
deque([4, 3, 2, 1])
>>> 

Je veux l'utiliser à l'avenir.