Che cos'è la struttura dei dati delle code in Python?



Questo articolo ti fornirà una conoscenza dettagliata e completa di Queue Data Structures in Python con molti esempi.

Come hai già studiato sull'importanza delle strutture dati nell'articolo precedente, tuffiamoci direttamente nell'argomento dell'articolo, ovvero la struttura dei dati della coda. Discuterò i seguenti argomenti:

Necessità della struttura dei dati della coda

Supponi di voler vedere un film un giorno. Nel multiplex, i biglietti venivano emessi in base all'ordine di arrivo e le persone erano in piedi l'una dietro l'altra in attesa del proprio turno. Allora, cosa farai ?? Devi essere andato sul retro e stare dietro l'ultima persona in attesa del biglietto.





queue-data-structure

Qui, le persone sono in piedi una dietro l'altra e vengono servite in base a First-In-First-Out (FIFO) meccanismo. Tale disposizione è nota come a Coda.



Esempi di coda nella vita quotidiana

Consideriamo alcuni esempi in cui vediamo il tipo di coda che funziona nella vita quotidiana:

  • Sistema di risposta telefonica La persona che chiama per prima sul tuo gadget viene assistita per prima.
  • Macchina controllo bagagli - Controlla il Bagaglio che è stato tenuto per primo sul nastro trasportatore.
  • Veicoli sul ponte pedaggio - I veicoli che arrivano presto partono per primi.
  • Call Center - i sistemi telefonici utilizzeranno le code, per tenere in ordine le persone che le chiamano, finché un rappresentante dell'assistenza non sarà libero.

Tutti questi esempi seguono First-In-Last-Out strategia.

Creazione di una struttura dati della coda

A parte le operazioni complementari, posso dire che le principali Operazioni possibili sulla Coda sono:



uno. Accodare o aggiungi un elemento alla fine della coda.

2. Ritira la coda o rimuovere un elemento dalla parte anteriore della coda

Ora, iniziamo creando la coda della classe in Python:

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elementi = [Nessuno] * self .__ max_size self .__ rear = -1 self .__ front = 0
  • max_size è il numero massimo di elementi previsti nella coda.
  • Gli elementi della coda vengono memorizzati nell'elenco Python
  • rear indica la posizione di indice dell'ultimo elemento nella coda.
  • Il retro è inizialmente considerato -1 perché la coda è vuota
  • Front indica la posizione del primo elemento nella coda.
  • Il fronte è inizialmente considerato 0 perché punterà sempre al primo elemento della coda

Accodare

Ora, quando provi ad accodare elementi alla coda, devi ricordare i seguenti punti:

  • Indipendentemente dal fatto che sia rimasto spazio nella coda o meno, ovvero se il retro è uguale a max_size -1
  • La parte posteriore punterà all'ultimo elemento inserito in coda.

Allora, quale sarà l'algoritmo ??

#returns max_size of queue def get_max_size (self): return self .__ max_size #returns bool value se la coda è piena o meno, True se piena e False altrimenti def is_full (self): return self .__ rear == self .__ max_size-1 # inserisce / accoda i dati nella coda se non è completa def enqueue (self, data): if (self.is_full ()): print ('Queue is full. No enqueue possible') else: self .__ rear + = 1 self. __elements [self .__ rear] = data # mostra tutto il contenuto della coda def display (self): for i in range (0, self .__ rear + 1): print (self .__ elements [i]) #Puoi usare il sotto __str __ () per stampare gli elementi dell'oggetto DS durante il debug def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg

Ora, quando esegui quanto segue:

queue1 = Queue (5)

# Accoda tutti gli elementi richiesti.

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

queue1.display ()

queue1.enqueue ('F')

stampa (coda1)

Produzione:

PER

B

C

D

E

La coda è piena. Nessun accodamento possibile

Dati in coda (dalla parte anteriore a quella posteriore): A B C D E

De-Queue

Ora, poiché hai inserito / accodato gli elementi nella coda, vuoi rimuoverli / eliminarli dalla coda, quindi devi fare attenzione a quanto segue:

  • Ci sono elementi nella coda, ad esempio rear non dovrebbe essere uguale a -1.
  • In secondo luogo, è necessario ricordare che poiché gli elementi vengono eliminati dalla parte anteriore, dopo l'eliminazione del fronte dovrebbe essere incrementato per puntare in avanti.
  • La parte anteriore non deve indicare la fine della coda, ovvero uguale a max_size.

Allora, quale sarà l'algoritmo ??

#funzione per controllare se la coda è vuota o no def is_empty (self): if (self .__ rear == - 1 o self .__ front == self .__ max_size): return True else: return False #funzione per rimuovere un elemento e tornare it def dequeue (self): if (self.is_empty ()): print ('la coda è già vuota') else: data = self .__ elementi [self .__ front] self .__ front + = 1 return data # function per visualizzare gli elementi da dalla parte anteriore a quella posteriore se la coda non è vuota def display (self): if (non self.is_empty ()): for i in range (self .__ front, self .__ rear + 1): print (self .__ elements [i]) else : print ('coda vuota')

Ora quando esegui quanto segue:

queue1 = Queue (5)

# Accoda tutti gli elementi richiesti

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

stampa (coda1)

#Dequeue tutti gli elementi richiesti

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

print ('Dequeued:', queue1.dequeue ())

#Mostra tutti gli elementi nella coda.

queue1.display ()

Produzione:

Dati in coda (dalla parte anteriore a quella posteriore): A B C D E

ruby on rails mercato del lavoro

Rimosso dalla coda: A

Rimosso dalla coda: B

Rimosso dalla coda: C

Rimosso dalla coda: D.

Rimosso dalla coda: E.

la coda è già vuota

Rimosso: nessuno

coda vuota

Applicazioni di Queue

A partire da ora, hai già compreso le basi della coda. Ora, per approfondire, esamineremo alcune delle sue applicazioni.

  • Esempio 1:

Coda di stampa in Windows utilizza una coda per memorizzare tutti i lavori di stampa attivi e in sospeso. Quando vogliamo stampare documenti, emettiamo comandi di stampa uno dopo l'altro. In base ai comandi di stampa, i documenti verranno allineati nella coda di stampa. Quando la stampante è pronta, il documento verrà inviato per primo in primo luogo per essere stampato.

Supponiamo di aver emesso comandi di stampa per 3 documenti nell'ordine doc1, seguito da doc2 e doc3.
La coda di stampa verrà popolata come mostrato di seguito:

doc-n, dove il doc è il documento inviato per la stampa en, è il numero di pagine nel documento. Ad esempio, doc2-10 significa che doc2 deve essere stampato e ha 10 pagine. Ecco un codice che simula l'operazione della coda di stampa. Esamina il codice e osserva come viene utilizzata la coda in questa implementazione.

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elementi = [Nessuno] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ rear): return True return False def enqueue (self, data): if (self.is_full ()): print ('Queue is full !!!') else: self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('La coda è vuota! !! ') else: data = self .__ elementi [self .__ front] self .__ front + = 1 return data def display (self): for index in range (self .__ front, self .__ rear + 1): print (self .__ elements [index]) def get_max_size (self): return self .__ max_size # Puoi usare il seguente __str __ () per stampare gli elementi dell'oggetto DS mentre #debugging def __str __ (self): msg = [] index = self .__ front while (indice<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()

Produzione:

doc1-5 inviato per la stampa

doc2-3 inviato per la stampa

doc3-6 inviato per la stampa

doc1-5 stampato

Restante no. di pagine nella stampante: 7

doc2-3 stampato

Restante no. di pagine nella stampante: 4

Impossibile stampare doc3. Pagine nella stampante insufficienti

  • Esempio 2:

Proviamo a capire un altro esempio che utilizza la struttura dei dati della coda. Puoi provare a capire il codice e dire cosa fa la seguente funzione?

  1. def fun (n):
  2. aqueue = Queue (100)
  3. per num nell'intervallo (1, n + 1):
  4. accodare (num)
  5. risultato = 1
  6. while (not (aqueue.is_empty ())):
  7. num = AQUUE.DEQUEUE ()
  8. risultato * = num
  9. stampa (risultato)

Quando la funzione fun () viene invocata passando n,

  • le righe da 2 a 4 mettono in coda gli elementi da 1 a n
  • le righe da 5 a 8 trovano il prodotto di questi elementi rimuovendoli dalla coda uno per uno

Con questo, arriviamo alla fine di questo articolo sulla struttura dei dati delle code. Se hai compreso e eseguito correttamente i codici da solo, non sei più un principiante di Queue Data Structure.

Hai domande per noi? Si prega di menzionarlo nella sezione commenti di questo articolo e ti risponderemo il prima possibile.

Per ottenere una conoscenza approfondita di Python e delle sue varie applicazioni, puoi iscriverti a live con supporto 24 ore su 24, 7 giorni su 7 e accesso a vita.