Οι δομές δεδομένων διαδραματίζουν βασικό ρόλο στον κόσμο του προγραμματισμού. Μας βοηθούν να οργανώσουμε τα δεδομένα μας με τρόπο που να μπορούν να χρησιμοποιηθούν αποτελεσματικά. Η ουρά είναι μια από τις απλούστερες δομές δεδομένων που υπάρχουν.
Σε αυτό το άρθρο, θα μάθουμε για την ουρά και την εφαρμογή της στην Python.
Πίνακας περιεχομένων
Τι είναι η ουρά;
Η ουρά είναι μια γραμμική δομή δεδομένων που ακολουθεί την αρχή First In/First Out (FIFO). Είναι αντίθετο με τη δομή δεδομένων Stack.
Μπορούμε να συγκρίνουμε την ουρά με μια πραγματική ουρά στο γκισέ εισιτηρίων του κινηματογράφου. Ας δούμε την απεικόνιση μιας ουράς ως εξής.
Αν παρατηρήσετε την ουρά στο γκισέ, το δεύτερο άτομο μπορεί να πάει στον πάγκο μόνο αφού το πρώτο άτομο ολοκληρώσει την εργασία του. Εδώ έρχεται το πρώτο άτομο στον πάγκο και μετά το δεύτερο άτομο. Έτσι, εδώ οι άνθρωποι ακολουθούν την αρχή FIFO (First In/First Out). Όποιος έρθει πρώτος θα ολοκληρώσει πρώτος το έργο. Μπορούμε να δούμε παρόμοιο είδος ουρών στην καθημερινή μας ζωή.
Η δομή δεδομένων Queue ακολουθεί επίσης την ίδια αρχή. Τώρα, ξέρετε τι είναι οι ουρές και η αρχή τους. Ας δούμε τις λειτουργίες που μπορούν να εκτελεστούν σε μια δομή δεδομένων ουράς.
Λειτουργίες στην ουρά
Παρόμοια με τη στοίβα, θα βρούμε δύο κύριες λειτουργίες σε μια δομή δεδομένων ουράς.
ουρά (δεδομένα)
Προσθέτει νέα δεδομένα στην ουρά στο τέλος. Η πλευρά ονομάζεται πίσω.
dequeue()
Αφαιρεί δεδομένα από το μπροστινό μέρος της ουράς. Η πλευρά ονομάζεται μπροστινή.
Ας δούμε τις απεικονίσεις των λειτουργιών ουράς για καλύτερη κατανόηση. Μια εικόνα λέει χίλιες λέξεις.
Μπορούμε να γράψουμε κάποιες βοηθητικές συναρτήσεις για να λάβουμε περισσότερες πληροφορίες σχετικά με την ουρά. Δεν υπάρχει όριο στον αριθμό των βοηθητικών λειτουργιών που θα έχετε. Ας μείνουμε στα πιο σημαντικά που αναφέρθηκαν κάποτε παρακάτω προς το παρόν.
όπισθεν()
Επιστρέφει το πρώτο στοιχείο από το τέλος της ουράς.
εμπρός()
Επιστρέφει το πρώτο στοιχείο από την αρχή της ουράς.
είναι άδειο()
Επιστρέφει είτε η ουρά είναι άδεια είτε όχι.
Δεν είναι βαρετό για εσάς; Εννοώ τα εννοιολογικά θέματα.
Για μενα ναι!
Όμως, δεν μπορούμε να κάνουμε τίποτα χωρίς να γνωρίζουμε τις έννοιες. Πρέπει να το γνωρίζουμε πλήρως πριν από την εφαρμογή. Μην ανησυχείτε, ήρθε η ώρα να λερώσουμε τα χέρια μας με κάποιο κωδικό.
Υποθέτω ότι έχετε εγκαταστήσει την python στον υπολογιστή σας, εάν όχι, μπορείτε επίσης να δοκιμάσετε τον διαδικτυακό μεταγλωττιστή.
Υλοποίηση ουράς
Η υλοποίηση μιας ουράς δεν θα διαρκέσει περισσότερα από 15 λεπτά για έναν προγραμματιστή. Μόλις μάθεις, θα το πεις. Ίσως μπορείτε να το εφαρμόσετε μέσα σε λίγα λεπτά μετά από αυτό το σεμινάριο.
Υπάρχουν πολλοί τρόποι υλοποίησης της ουράς στην Python. Ας δούμε διαφορετικές υλοποιήσεις ουράς βήμα προς βήμα.
#1. Λίστα
Η λίστα είναι ένας ενσωματωμένος τύπος δεδομένων στην Python. Θα χρησιμοποιήσουμε τον τύπο δεδομένων λίστας για να εφαρμόσουμε μια ουρά σε μια τάξη. Θα σας καθοδηγήσουμε σε διάφορα βήματα για να εφαρμόσετε τη δομή δεδομένων ουράς από την αρχή χωρίς καμία ενότητα. Ας πηδήξουμε σε αυτό.
Βήμα 1:
Γράψτε μια τάξη που ονομάζεται Ουρά.
class Queue: pass
Βήμα 2:
Πρέπει να υπάρχει κάποια μεταβλητή για να αποθηκεύονται τα δεδομένα της ουράς στην τάξη. Ας το ονομάσουμε στοιχεία. Και είναι μια λίστα φυσικά.
class Queue: def __init__(self): self.elements = []
Βήμα 3:
Για να εισαγάγουμε δεδομένα στην ουρά, χρειαζόμαστε μια μέθοδο στην κλάση. Η μέθοδος ονομάζεται enqueue όπως έχουμε ήδη συζητήσει στην προηγούμενη ενότητα του σεμιναρίου.
Η μέθοδος παίρνει κάποια δεδομένα και τα προσθέτει στην ουρά (στοιχεία). Μπορούμε να χρησιμοποιήσουμε τη μέθοδο προσάρτησης του τύπου δεδομένων λίστας για να προσθέσουμε δεδομένα στο τέλος της ουράς.
class Queue: # ... def enqueue(self, data): self.elements.append(data) return data
Βήμα 4:
Η ουρά πρέπει να έχει έξοδο. Και αυτό λέγεται dequeue. Νομίζω ότι έχετε ήδη μαντέψει ότι θα χρησιμοποιήσουμε τη μέθοδο pop του τύπου δεδομένων λίστας. Αν μαντέψατε ή όχι, μπράβο!
Η μέθοδος pop του τύπου δεδομένων λίστας διαγράφει ένα στοιχείο από τη λίστα του δεδομένου ευρετηρίου. Εάν δεν δώσαμε κανένα ευρετήριο, τότε διαγράφει το τελευταίο στοιχείο της λίστας.
Εδώ, πρέπει να διαγράψουμε το πρώτο στοιχείο της λίστας. Επομένως, πρέπει να περάσουμε το δείκτη 0 στη μέθοδο pop.
class Queue: # ... def dequeue(self): return self.elements.pop(0)
Αυτό είναι αρκετό για μια ουρά. Όμως, χρειαζόμαστε τις βοηθητικές συναρτήσεις για να ελέγξουμε εάν οι λειτουργίες ουράς λειτουργούν σωστά ή όχι. Ας γράψουμε και τις βοηθητικές συναρτήσεις.
Βήμα 5:
Η μέθοδος rear() χρησιμοποιείται για τη λήψη του τελευταίου στοιχείου της ουράς. Η αρνητική ευρετηρίαση στον τύπο δεδομένων λίστας μας βοηθά να λάβουμε το τελευταίο στοιχείο της ουράς.
class Queue: # ... def rear(self): return self.elements[-1]
Βήμα 6:
Η μέθοδος front() χρησιμοποιείται για τη λήψη του πρώτου στοιχείου της ουράς. Μπορούμε να πάρουμε το πρώτο στοιχείο της ουράς χρησιμοποιώντας το ευρετήριο λίστας.
class Queue: # ... def front(self): return self.elements[0]
Βήμα 7:
Η μέθοδος is_empty() χρησιμοποιείται για να ελέγξει εάν η ουρά είναι κενή ή όχι. Μπορούμε να ελέγξουμε για το μήκος της λίστας.
class Queue: # ... def is_empty(self): return len(self.elements) == 0
Φτου! ολοκλήρωσε το τμήμα υλοποίησης της δομής δεδομένων ουράς. Πρέπει να δημιουργήσουμε ένα αντικείμενο για χρήση της κλάσης Queue.
Ας το κάνουμε.
class Queue: # ... if __name__ == '__main__': queue = Queue()
Τώρα, έχουμε ένα αντικείμενο Queue. Ας το δοκιμάσουμε με κάποιες σειρές λειτουργιών.
- Ελέγξτε εάν η ουρά είναι κενή ή όχι χρησιμοποιώντας τη μέθοδο is_empty. Θα πρέπει να επιστρέψει True.
- Προσθέστε τους αριθμούς 1, 2, 3, 4, 5 στην ουρά χρησιμοποιώντας τη μέθοδο αναμονής.
- Η μέθοδος is_empty θα πρέπει να επιστρέψει False. Ελεγξέ το.
- Εκτυπώστε το μπροστινό και το πίσω στοιχείο χρησιμοποιώντας τις μεθόδους εμπρός και πίσω αντίστοιχα.
- Αφαιρέστε το στοιχείο από την ουρά χρησιμοποιώντας τη μέθοδο dequeue.
- Ελέγξτε το μπροστινό στοιχείο. Θα πρέπει να επιστρέψει το στοιχείο 2.
- Τώρα, αφαιρέστε όλα τα στοιχεία από την ουρά.
- Η μέθοδος is_empty θα πρέπει να επιστρέψει True. Ελεγξέ το.
Νομίζω ότι αυτό είναι αρκετό για να δοκιμάσουμε την εφαρμογή της ουράς μας. Γράψτε τον κωδικό για κάθε βήμα που αναφέρεται παραπάνω για να ελέγξετε την ουρά.
Έγραψες τον κωδικό;
Όχι, μην ανησυχείς.
Ελέγξτε τον παρακάτω κωδικό.
class Queue: def __init__(self): self.elements = [] def enqueue(self, data): self.elements.append(data) return data def dequeue(self): return self.elements.pop(0) def rear(self): return self.elements[-1] def front(self): return self.elements[0] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': queue = Queue() ## checking is_empty method -> True print(queue.is_empty()) ## adding the elements queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.enqueue(4) queue.enqueue(5) ## again checking is_empty method -> False print(queue.is_empty()) ## printing the front and rear elements using front and rear methods respectively -> 1, 5 print(queue.front(), end=' ') print(queue.rear()) ## removing the element -> 1 queue.dequeue() ## checking the front and rear elements using front and rear methods respectively -> 2 5 print(queue.front(), end=' ') print(queue.rear()) ## removing all the elements queue.dequeue() queue.dequeue() queue.dequeue() queue.dequeue() ## checking the is_empty method for the last time -> True print(queue.is_empty())
Νομίζω ότι τρέχεις το παραπάνω πρόγραμμα. Μπορείτε να πάρετε μια έξοδο παρόμοια με το παρακάτω αποτέλεσμα.
True False 1 5 2 5 True
Μπορούμε να χρησιμοποιήσουμε απευθείας τον τύπο δεδομένων λίστας ως δομή δεδομένων ουράς. Η παραπάνω υλοποίηση της ουράς σάς βοηθά να κατανοήσετε καλύτερα την υλοποίηση της ουράς σε άλλες γλώσσες προγραμματισμού.
Μπορείτε επίσης να χρησιμοποιήσετε την παραπάνω κλάση υλοποίηση μιας ουράς σε ένα διαφορετικό πρόγραμμα ενός έργου δημιουργώντας απλώς το αντικείμενο όπως κάναμε νωρίτερα.
Έχουμε εφαρμόσει την ουρά από την αρχή χρησιμοποιώντας τον τύπο δεδομένων λίστας. Υπάρχουν ενσωματωμένες μονάδες για την ουρά; Ναι! έχουμε ενσωματωμένες υλοποιήσεις ουράς. Ας τους δούμε.
#2. ντεκ από συλλογές
Υλοποιείται ως διπλή ουρά. Δεδομένου ότι υποστηρίζει την προσθήκη και αφαίρεση στοιχείων και από τα δύο άκρα, μπορούμε να το χρησιμοποιήσουμε ως στοίβα και ουρά. Ας δούμε την υλοποίηση της ουράς χρησιμοποιώντας το dequeue.
Υλοποιείται χρησιμοποιώντας άλλες δομές δεδομένων που ονομάζονται λίστα διπλής σύνδεσης. Έτσι η απόδοση της εισαγωγής και διαγραφής στοιχείων είναι συνεπής. Η πρόσβαση σε στοιχεία από τη μεσαία συνδεδεμένη λίστα χρειάστηκε O(n) χρόνο. Μπορούμε να το χρησιμοποιήσουμε ως ουρά καθώς δεν υπάρχει ανάγκη πρόσβασης στα μεσαία στοιχεία από την ουρά.
Ας ελέγξουμε τις διαφορετικές μεθόδους που μας προσφέρει το dequeue.
- append(data) – χρησιμοποιείται για την προσθήκη των δεδομένων στην ουρά
- popleft() – χρησιμοποιείται για την αφαίρεση του πρώτου στοιχείου από την ουρά
Δεν υπάρχουν εναλλακτικές μέθοδοι για το μπροστινό, το πίσω μέρος και το is_empty. Μπορούμε να εκτυπώσουμε ολόκληρη την ουρά στη θέση των μπροστινών και πίσω μεθόδων. Στη συνέχεια, μπορούμε να χρησιμοποιήσουμε τη μέθοδο len για να ελέγξουμε αν η ουρά είναι άδεια ή όχι.
Ακολουθήσαμε μια σειρά βημάτων για να δοκιμάσουμε την υλοποίηση της ουράς στο προηγούμενο. Ας ακολουθήσουμε την ίδια σειρά βημάτων και εδώ.
from collections import deque ## creating deque object queue = deque() ## checking whether queue is empty or not -> True print(len(queue) == 0) ## pushing the elements queue.append(1) queue.append(2) queue.append(3) queue.append(4) queue.append(5) ## again checking whether queue is empty or not -> False print(len(queue) == 0) ## printing the queue print(queue) ## removing the element -> 1 queue.popleft() ## printing the queue print(queue) ## removing all the elements queue.popleft() queue.popleft() queue.popleft() queue.popleft() ## checking the whether queue is empty or not for the last time -> True print(len(queue) == 0)
Θα λάβετε ένα αποτέλεσμα παρόμοιο με το παρακάτω αποτέλεσμα.
True False deque([1, 2, 3, 4, 5]) deque([2, 3, 4, 5]) True
#3. Ουρά από ουρά
Η Python έχει μια ενσωματωμένη μονάδα που ονομάζεται ουρά που εξυπηρετεί μια κλάση που ονομάζεται Queue για την υλοποίηση της ουράς. Είναι παρόμοιο με αυτό που έχουμε εφαρμόσει στο παρελθόν.
Αρχικά, ας ελέγξουμε διαφορετικές μεθόδους της κλάσης Queue.
- put(data) – προσθέτει ή ωθεί τα δεδομένα στην ουρά
- get() – αφαιρεί το πρώτο στοιχείο από την ουρά και το επιστρέφει
- vala() – επιστρέφει αν η στοίβα είναι άδεια ή όχι
- qsize() – επιστρέφει το μήκος της ουράς.
Ας υλοποιήσουμε την ουρά με τις παραπάνω μεθόδους.
from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())
Ελέγξτε την έξοδο του παραπάνω κώδικα.
True False 1 2 3 Size 2 4 5 True
Υπάρχουν κάποιες άλλες μέθοδοι στην κλάση Queue. Μπορείτε να τα εξερευνήσετε χρησιμοποιώντας την ενσωματωμένη λειτουργία dir.
συμπέρασμα
Ελπίζω να έχετε μάθει για τη δομή δεδομένων ουράς και την εφαρμογή της. Αυτό είναι για την ουρά. Μπορείτε να χρησιμοποιήσετε την ουρά σε διαφορετικά σημεία όπου χρειάζεται επεξεργασία με σειρά FIFO (Πρώτη είσοδος/Πρώτη έξοδος). Χρησιμοποιήστε την ουρά για την επίλυση προβλημάτων όποτε έχετε την ευκαιρία να το χρησιμοποιήσετε.
Ενδιαφέρεστε να κατακτήσετε την Python; Ελέγξτε αυτούς τους πόρους εκμάθησης.
Καλή κωδικοποίηση 🙂 👨💻