Com una pila, la cua és una estructura de dades lineal que emmagatzema elements en un First In First Out ( FIFO ) manera. Amb una cua, primer s'elimina l'element afegit menys recentment. Un bon exemple de cua és qualsevol cua de consumidors per a un recurs on el consumidor que ha arribat primer és atès primer.

què és desktop ini

Les operacions associades a la cua són:

• Cua: Afegeix un element a la cua. Si la cua està plena, es diu que és una condició de desbordament - Complexitat temporal: O(1)
• D'acord amb: Elimina un element de la cua. Els elements apareixen en el mateix ordre en què s'empenyen. Si la cua està buida, es diu que és una condició de desbordament inferior - Complexitat temporal: O(1)
• Davant: Obteniu l'element frontal de la cua - Complexitat temporal: O(1)
• posterior: Obteniu l'últim element de la cua - Complexitat temporal: O(1)

Implementar una cua en Python

Hi ha diverses maneres d'implementar una cua Python. Aquest article tracta la implementació de la cua mitjançant estructures de dades i mòduls de la biblioteca Python. Python Queue es pot implementar de les maneres següents:

• llista
• col·leccions.deque
• cua.cua

Implementació mitjançant llista

List és una estructura de dades integrada de Python que es pot utilitzar com a cua. En lloc de enqueue() i d'acord amb () , afegir() i pop() s'utilitza la funció. No obstant això, les llistes són bastant lentes per a aquest propòsit perquè inserir o suprimir un element al principi requereix desplaçar tots els altres elements en un, i requereix temps O(n).
El codi simula una cua mitjançant una llista de Python. Afegeix elements 'a' , 'b' , i 'c' a la cua i després les treu de cua, donant com a resultat una cua buida al final. La sortida mostra la cua inicial, elements retirats de la cua ( 'a' , 'b' , 'c' ), i l'estat buit de la cua.

Python 3

>

>

Sortida:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements []>

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list>

Implementació mitjançant collections.deque

La cua a Python es pot implementar mitjançant la classe deque del mòdul de col·leccions. Es prefereix Deque a la llista en els casos en què necessitem operacions d'afegir i pop més ràpides des dels dos extrems del contenidor, ja que deque proporciona una complexitat de temps O(1) per a les operacions d'afegir i pop en comparació amb la llista que proporciona complexitat de temps O (n) . En lloc d'enqueue i deque, s'utilitzen les funcions append() i popleft().
El codi utilitza adeque>des delcollections>mòdul per representar una cua. S'adjunta 'a' , 'b' , i 'c' a la cua i els treu la cua amb q.popleft()> , resultant en una cua buida. Sense comentaris q.popleft()> després que la cua estigui buida, generaria unIndexError>. El codi mostra les operacions de la cua i gestiona un escenari de cua buida.

Python 3

mylivecricket

>

>

Sortida:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])>

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque>

Implementació mitjançant queue.Queue

Queue és un mòdul integrat de Python que s'utilitza per implementar una cua. queue.Queue(maxsize) inicialitza una variable a una mida màxima de maxsize. Una mida màxima de zero '0' significa una cua infinita. Aquesta cua segueix la regla FIFO.
Hi ha diverses funcions disponibles en aquest mòdul:

• mida màxima – Nombre d'elements permesos a la cua.
• buit() – Retorna True si la cua està buida, False en cas contrari.
• ple () – Retorna True si hi ha elements de mida màxima a la cua. Si la cua s'ha inicialitzat amb maxsize=0 (per defecte), aleshores full() no retorna mai True.
• aconseguir() – Eliminar i tornar un element de la cua. Si la cua està buida, espereu fins que hi hagi un element disponible.
• get_nowait() – Retorna un element si n'hi ha un disponible immediatament, en cas contrari, puja QueueEmpty.
• posar (element) – Posa un article a la cua. Si la cua està plena, espereu fins que hi hagi un espai lliure abans d'afegir l'element.
• put_nowait(element) – Posa un article a la cua sense bloquejar. Si no hi ha cap ranura lliure disponible immediatament, augmenta QueueFull.
• qsize() – Retorna el nombre d'elements de la cua.

Exemple: Aquest codi utilitza elQueue>classe de laqueue>mòdul. Comença amb una cua buida i l'omple amb ' a', 'b' , i 'c' . Després de treure la cua, la cua queda buida i s'afegeix '1'. Tot i estar buit abans, continua ple, ja que la mida màxima s'estableix en 3. El codi mostra les operacions de la cua, inclosa la comprovació de la plenitud i el buit.

Python 3

>

>

Sortida:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False>