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
- Esempi di coda nella vita quotidiana
- Creazione di una struttura dati della coda
- Accodare
- Ritira la coda
- Applicazioni di Queue
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.
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?
- def fun (n):
- aqueue = Queue (100)
- per num nell'intervallo (1, n + 1):
- accodare (num)
- risultato = 1
- while (not (aqueue.is_empty ())):
- num = AQUUE.DEQUEUE ()
- risultato * = num
- 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.