Τι είναι η δομή δεδομένων ουράς στο Python;

Καθώς έχετε ήδη μελετήσει σχετικά με τη σημασία των Δομών δεδομένων στο προηγούμενο άρθρο, Ας δούμε αμέσως το θέμα του άρθρου, δηλαδή τη Δομή δεδομένων ουράς. Θα συζητήσω τα ακόλουθα θέματα:

• Ανάγκη για δομή δεδομένων ουράς
• Παραδείγματα καθημερινής ζωής ουράς
• Δημιουργία δομής δεδομένων ουράς
• Εν-ουρά
• De-ουρά
• Εφαρμογές ουράς

Ανάγκη για δομή δεδομένων ουράς

Ας υποθέσουμε ότι θέλετε μια ταινία μια μέρα. Στο multiplex, τα εισιτήρια εκδόθηκαν με βάση το First-Come-First-Serve και οι άνθρωποι στέκονταν πίσω ο ένας τον άλλον περιμένοντας τη σειρά τους. Τι θα κάνεις λοιπόν?? Πρέπει να έχετε πάει πίσω και να σταθείτε πίσω από το τελευταίο άτομο που περιμένει το εισιτήριο.

Εδώ, οι άνθρωποι στέκονται το ένα πίσω από το άλλο και εξυπηρετούνται βάσει του First-In-First-Out (FIFO) μηχανισμός. Μια τέτοια ρύθμιση είναι γνωστή ως Ουρά.

Παραδείγματα καθημερινής ζωής ουράς

Ας δούμε μερικά παραδείγματα όπου βλέπουμε τον τύπο ουράς που λειτουργεί στην καθημερινή ζωή:

• Σύστημα τηλεφωνητή- Το άτομο που καλεί πρώτα στο gadget σας παρευρίσκεται πρώτο.
• Μηχανή ελέγχου αποσκευών - Ελέγχει τις αποσκευές που φυλάχτηκαν πρώτα στον ιμάντα μεταφοράς.
• Οχήματα στη γέφυρα διοδίων - Τα οχήματα που φτάνουν νωρίς φεύγουν πρώτα.
• Τηλεφωνικό κέντρο - τα τηλεφωνικά συστήματα θα χρησιμοποιούν τις ουρές, για να κρατούν τα άτομα που τους καλούν σε σειρά, έως ότου ένας αντιπρόσωπος σέρβις είναι δωρεάν

Ακολουθούν όλα αυτά τα παραδείγματα Πρώτο-τελευταίο-έξω στρατηγική.

Δημιουργία δομής δεδομένων ουράς

Εκτός από τις συμπληρωματικές λειτουργίες, μπορώ να πω ότι οι κύριες δυνατές λειτουργίες στην ουρά είναι:

ένας. Εν-ουρά ή προσθέστε ένα στοιχείο στο τέλος της ουράς.

2. De-ουρά ή αφαιρέστε ένα στοιχείο από το μπροστινό μέρος της ουράς

Τώρα, ας ξεκινήσουμε δημιουργώντας ουρά τάξης στο Python:

ουρά τάξης: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ πίσω = -1 self .__ front = 0

• μέγιστο μέγεθος είναι ο μέγιστος αριθμός στοιχείων που αναμένονται στην ουρά.
• Τα στοιχεία της ουράς αποθηκεύονται στη λίστα των python
• πίσω δείχνει τη θέση ευρετηρίου του τελευταίου στοιχείου στην ουρά.
• Το πίσω μέρος αρχικά θεωρείται -1 επειδή η ουρά είναι κενή
• Το μπροστινό μέρος δείχνει τη θέση του πρώτου στοιχείου στην ουρά.
• Το μέτωπο θεωρείται αρχικά 0 επειδή θα δείχνει πάντα στο πρώτο στοιχείο της ουράς

Enqueue

Τώρα, όταν προσπαθείτε να τοποθετήσετε στοιχεία στην ουρά, πρέπει να θυμάστε τα ακόλουθα σημεία:

• Είτε απομένει κενό στην ουρά είτε όχι, αν το πίσω μέρος ισούται με το μέγιστο μέγεθος -1
• Το πίσω μέρος θα δείχνει το τελευταίο στοιχείο που έχει εισαχθεί στην ουρά.

Λοιπόν, ποιος θα είναι ο αλγόριθμος ;;

#returns max_size of queue def get_max_size (self): return self .__ max_size #returns bool value αν η ουρά είναι πλήρης ή όχι, True αν είναι πλήρης και False διαφορετικά def is_full (self): return self .__ πίσω == self .__ max_size-1 # εισάγει / δεδομένα enqueue στην ουρά εάν δεν είναι πλήρης def enqueue (self, data): if (self.is_full ()): print ('Queue is full. No enqueue δυνατός') άλλο: self .__ πίσω + = 1 self. __στοιχεία [αυτο .__ πίσω] = δεδομένα # εμφάνιση όλου του περιεχομένου της οθόνης ουράς def (αυτο): για i στην περιοχή (0, αυτο .__ πίσω + 1): εκτύπωση (αυτο .__ στοιχεία [i]) #Μπορείτε να χρησιμοποιήσετε το παρακάτω __str __ () για να εκτυπώσετε τα στοιχεία του αντικειμένου DS κατά τον εντοπισμό σφαλμάτων 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

Τώρα, όταν εκτελείτε τα ακόλουθα:

queue1 = Ουρά (5)

# Ενεργοποιήστε όλα τα απαιτούμενα στοιχεία.

queue1.enqueue ('A')

queue1.enqueue ('Β')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

queue1.display ()

εργαλεία που χρησιμοποιούνται σε μεγάλη ανάλυση δεδομένων

queue1.enqueue ('F')

εκτύπωση (ουρά1)

Παραγωγή:

ΠΡΟΣ ΤΟ

σι

ντο

ρε

ΕΙΝΑΙ

Η ουρά είναι γεμάτη. Δεν υπάρχει δυνατότητα enqueue

Δεδομένα ουράς (εμπρός προς τα πίσω): A B C D E

De-ουρά

Τώρα, καθώς έχετε εισάγει / τοποθετήσει τα στοιχεία στην ουρά, θέλετε να τα dequeue / διαγράψετε από μπροστά, οπότε πρέπει να προσέξετε να ακολουθήσετε:

• Υπάρχουν στοιχεία στην ουρά, δηλαδή το πίσω μέρος δεν πρέπει να είναι ίσο με -1.
• Δεύτερον, πρέπει να θυμάστε ότι καθώς τα στοιχεία διαγράφονται από το μπροστινό μέρος, οπότε, μετά τη διαγραφή του μπροστινού μέρους θα πρέπει να αυξηθεί στο σημείο του επόμενου.
• Το μπροστινό μέρος δεν πρέπει να δείχνει το τέλος της ουράς, δηλαδή ίσο με το μέγιστο μέγεθος.

Λοιπόν, ποιος θα είναι ο αλγόριθμος ;;

#function για να ελέγξετε αν η ουρά είναι κενή ή όχι def is_empty (self): if (self .__ πίσω == - 1 ή self .__ front == self .__ max_size): return True other: return False #function για να deque ένα στοιχείο και επιστροφή def dequeue (self): if (self.is_empty ()): print ('η ουρά είναι ήδη άδεια') άλλο: data = self .__ στοιχεία [self .__ front] self .__ front + = 1 return data #function για εμφάνιση στοιχείων από εμπρός προς τα πίσω εάν η ουρά δεν είναι κενή οθόνη def (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ πίσω + 1): print (self .__ στοιχεία [i]) other : εκτύπωση ('κενή ουρά')

Τώρα όταν εκτελείτε τα ακόλουθα:

queue1 = Ουρά (5)

# Ενεργοποιήστε όλα τα απαιτούμενα στοιχεία

queue1.enqueue ('A')

queue1.enqueue ('Β')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

εκτύπωση (ουρά1)

#Deueue όλα τα απαιτούμενα στοιχεία

εκτύπωση ('Dequeued:', queue1.dequeue ())

εκτύπωση ('Dequeued:', queue1.dequeue ())

εκτύπωση ('Dequeued:', queue1.dequeue ())

εκτύπωση ('Dequeued:', queue1.dequeue ())

μετατροπή τύπου c ++

εκτύπωση ('Dequeued:', queue1.dequeue ())

εκτύπωση ('Dequeued:', queue1.dequeue ())

# Εμφάνιση όλων των στοιχείων στην ουρά.

queue1.display ()

Παραγωγή:

Δεδομένα ουράς (εμπρός προς τα πίσω): A B C D E

Dequeued: Α

Dequeued: Β

Dequeued: Γ

Dequeued: Δ

Dequeued: Ε

η ουρά είναι ήδη άδεια

Dequeued: Κανένα

κενή ουρά

Εφαρμογές ουράς

Από τώρα, έχετε ήδη καταλάβει τα βασικά της ουράς. Τώρα για να βουτήξουμε βαθύτερα θα εξετάσουμε μερικές από τις εφαρμογές της.

• Παράδειγμα 1:

Εκτύπωση ουράς στα Windows χρησιμοποιεί μια ουρά για να αποθηκεύσει όλες τις ενεργές και εκκρεμείς εργασίες εκτύπωσης. Όταν θέλουμε να εκτυπώσουμε έγγραφα, εκδίδουμε εντολές εκτύπωσης το ένα μετά το άλλο. Με βάση τις εντολές εκτύπωσης, τα έγγραφα θα παραταχθούν στην ουρά εκτύπωσης. Όταν ο εκτυπωτής είναι έτοιμος, το έγγραφο θα σταλεί πρώτα με πρώτη σειρά για να εκτυπωθεί.

Ας υποθέσουμε ότι έχετε εκδώσει εντολές εκτύπωσης για 3 έγγραφα με τη σειρά doc1, ακολουθούμενη από doc2 και doc3.
Η ουρά εκτύπωσης θα συμπληρωθεί όπως φαίνεται παρακάτω:

doc-n, όπου το έγγραφο είναι το έγγραφο που αποστέλλεται για εκτύπωση και n, είναι ο αριθμός των σελίδων στο έγγραφο. Για παράδειγμα, το doc2-10 σημαίνει ότι το doc2 πρέπει να εκτυπωθεί και έχει 10 σελίδες. Εδώ είναι ένας κωδικός που προσομοιώνει τη λειτουργία ουράς εκτύπωσης. Ανατρέξτε στον κώδικα και παρατηρήστε πώς χρησιμοποιείται η ουρά σε αυτήν την εφαρμογή.

ουρά τάξης: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ πίσω = -1 self .__ front = 0 def is_full (self): if (self .__ πίσω = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ πίσω): return True return False def enqueue (self, data): if (self.is_full ()): print ('Queue is full !!!') other: self .__ πίσω + = 1 self .__ στοιχεία [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('Η ουρά είναι άδεια! !! ') other: data = self .__ στοιχεία [self .__ front] self .__ front + = 1 return data def display (self): for index in range (self .__ front, self .__ rear + 1): print (self .__ στοιχεία) [index]) def get_max_size (self): return self .__ max_size # Μπορείτε να χρησιμοποιήσετε το παρακάτω __str __ () για να εκτυπώσετε τα στοιχεία του αντικειμένου DS ενώ #debugging def __str __ (self): msg = [] index = self .__ μπροστά ενώ (δείκτης<=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()

Παραγωγή:

το έγγραφο 1-5 εστάλη για εκτύπωση

το doc2-3 στάλθηκε για εκτύπωση

το έγγραφο 3-6 εστάλη για εκτύπωση

έντυπο doc1-5

Υπόλοιπο αρ. σελίδων στον εκτυπωτή: 7

τυπωμένο doc2-3

Υπόλοιπο αρ. σελίδων στον εκτυπωτή: 4

Δεν ήταν δυνατή η εκτύπωση του εγγράφου3. Δεν υπάρχουν αρκετές σελίδες στον εκτυπωτή

• Παράδειγμα 2:

Ας προσπαθήσουμε να κατανοήσουμε ένα άλλο παράδειγμα που χρησιμοποιεί τη δομή δεδομένων ουράς. Μπορείτε να προσπαθήσετε να κατανοήσετε τον κωδικό και να πείτε τι κάνει η ακόλουθη λειτουργία;

1. def fun (n):
2. aqueue = Ουρά (100)
3. για τον αριθμό στην περιοχή (1, n + 1):
4. enqueue (αριθμός)
5. αποτέλεσμα = 1
6. ενώ (όχι (aqueue.is_empty ())):
7. αριθμός = AQUUE.DEQUEUE ()
8. αποτέλεσμα * = αριθ
9. εκτύπωση (αποτέλεσμα)

Όταν η συνάρτηση fun () ενεργοποιείται περνώντας το n,

• οι γραμμές 2 έως 4 αλληλογραφούν τα στοιχεία από 1 έως n
• Οι γραμμές 5 έως 8 βρίσκουν το προϊόν αυτών των στοιχείων αποσυνδέοντάς το ένα προς ένα

Με αυτό, καταλήγουμε σε αυτό το άρθρο της Δομής δεδομένων ουράς. Αν καταλάβατε με επιτυχία τους κώδικες από εσάς, δεν είστε πλέον αρχάριος στη Δομή δεδομένων ουράς.

Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του άρθρου και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.

Για να μάθετε σε βάθος την Python μαζί με τις διάφορες εφαρμογές της, μπορείτε να εγγραφείτε ζωντανά με υποστήριξη 24/7 και πρόσβαση σε όλη τη διάρκεια ζωής.