![Τι εάν περιορίσατε σε 140 χαρακτήρες στην πραγματική ζωή [Video]](https://gadget-info.com/img/entertainment/316/what-if-you-were-restricted-140-characters-real-life.jpg)
Η στοίβα έχει μόνο ένα άκρο ανοιχτό για την ώθηση και την απόσπαση των στοιχείων δεδομένων από την άλλη πλευρά Η ουρά έχει και τα δύο άκρα ανοιχτά για να συμπιέζει και να αποσπάσει τα στοιχεία δεδομένων.
Η στοίβα και η ουρά είναι οι δομές δεδομένων που χρησιμοποιούνται για την αποθήκευση δεδομένων και στην πραγματικότητα βασίζονται σε κάποιο πραγματικό παγκόσμιο ισοδύναμο. Για παράδειγμα, η στοίβα είναι μια στοίβα από CD όπου μπορείτε να βγάλετε και να βάλετε CD μέσα από την κορυφή της στοίβας των CD. Ομοίως, η ουρά είναι μια ουρά για τα εισιτήρια Θεάτρου όπου το άτομο που στέκεται στην πρώτη θέση, δηλαδή το μπροστινό μέρος της ουράς, θα εξυπηρετηθεί πρώτα και το νέο άτομο που θα φτάσει θα εμφανιστεί στο πίσω μέρος της ουράς (πίσω άκρο της ουράς).
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Σωρός | Ουρά |
|---|---|---|
| Αρχή λειτουργίας | LIFO (Τελευταία στην πρώτη) | FIFO (Πρώτη σε πρώτη θέση) |
| Δομή | Το ίδιο τέλος χρησιμοποιείται για την εισαγωγή και τη διαγραφή στοιχείων. | Ένα άκρο χρησιμοποιείται για την εισαγωγή, δηλ. Το οπίσθιο άκρο και ένα άλλο άκρο χρησιμοποιείται για τη διαγραφή των στοιχείων, δηλαδή του μπροστινού άκρου. |
| Αριθμός χρησιμοποιημένων δεικτών | Ενας | Δύο (σε περίπτωση απλής ουράς) |
| Εκτελούνται οι λειτουργίες | Πιέστε και Ποπ | Περικοπή και αποκόλληση |
| Εξέταση της κενής κατάστασης | Κορυφή == -1 | Μπροστά == -1 || Μπροστά == Πίσω + 1 |
| Εξέταση της πλήρους κατάστασης | Κορυφή == Μέγιστο - 1 | Πίσω == Μέγιστο - 1 |
| Παραλλαγές | Δεν έχει παραλλαγές. | Έχει παραλλαγές όπως η κυκλική ουρά, η ουρά προτεραιότητας, η ουρά διπλής αρίθμησης. |
| Εκτέλεση | Απλούστερη | Συγκριτικά πολύπλοκο |
Ορισμός του Stack
Μια στοίβα είναι μια μη πρωτόγονη δομή γραμμικών δεδομένων. Πρόκειται για μια διατεταγμένη λίστα όπου προστίθεται το νέο στοιχείο και το υπάρχον στοιχείο διαγράφεται από ένα μόνο άκρο, το οποίο καλείται ως το κορυφαίο της στοίβας (TOS). Καθώς όλη η διαγραφή και εισαγωγή σε μια στοίβα γίνεται από την κορυφή της στοίβας, το τελευταίο στοιχείο που προστέθηκε θα είναι το πρώτο που θα αφαιρεθεί από τη στοίβα. Αυτός είναι ο λόγος για τον οποίο η στοίβα ονομάζεται λίστα τύπου Last-in-First-out (LIFO).
Σημειώστε ότι το στοιχείο που είναι συχνά προσπελάσιμο στη στοίβα είναι το κορυφαίο στοιχείο, ενώ το τελευταίο διαθέσιμο στοιχείο βρίσκεται στο κάτω μέρος της στοίβας.
Παράδειγμα
Μερικοί από εσάς μπορεί να φάτε μπισκότα (ή Poppins). Εάν υποθέσετε, μόνο μία πλευρά του καλύμματος είναι σκισμένη και τα μπισκότα εξάγονται ένα προς ένα. Αυτό είναι που λέγεται popping, και ομοίως, αν θέλετε να διατηρήσετε κάποια μπισκότα για κάποιο χρονικό διάστημα αργότερα, θα τα βάλετε πίσω στο πακέτο μέσω του ίδιου σχισμένου άκρου που ονομάζεται pushing.
Ορισμός της ουράς
Μια ουρά είναι μια γραμμική δομή δεδομένων που έρχεται στην κατηγορία του μη πρωτόγονου τύπου. Πρόκειται για μια συλλογή παρόμοιων στοιχείων. Η προσθήκη νέων στοιχείων λαμβάνει χώρα στο ένα άκρο που ονομάζεται οπίσθιο τμήμα. Ομοίως, η διαγραφή των υπαρχόντων στοιχείων πραγματοποιείται στο άλλο άκρο που ονομάζεται Front-end και είναι λογικά ένας τύπος πρώτης κατηγορίας (FIFO).
Παράδειγμα
Στην καθημερινή μας ζωή συναντάμε πολλές καταστάσεις όπου βγαίνουμε για να περιμένουμε την επιθυμητή υπηρεσία, εκεί πρέπει να βρεθούμε στην γραμμή αναμονής για να μπορέσουμε να εξυπηρετήσουμε. Αυτή η ουρά αναμονής μπορεί να θεωρηθεί ως ουρά.
Βασικές διαφορές μεταξύ στοίβας και ουράς
- Η στοίβα ακολουθεί τον μηχανισμό LIFO από την άλλη πλευρά Η ουρά ακολουθεί τον μηχανισμό FIFO για να προσθέσει και να αφαιρέσει στοιχεία.
- Σε μια στοίβα, το ίδιο τέλος χρησιμοποιείται για την εισαγωγή και τη διαγραφή των στοιχείων. Αντίθετα, στην ουρά χρησιμοποιούνται δύο διαφορετικοί άξονες για την εισαγωγή και τη διαγραφή των στοιχείων.
- Δεδομένου ότι η στοίβα έχει μόνο ένα ανοιχτό άκρο, αυτός είναι ο λόγος που χρησιμοποιείται μόνο ένας δείκτης για να αναφερθεί στην κορυφή της στοίβας. Ωστόσο, η ουρά χρησιμοποιεί δύο δείκτες για να αναφερθεί το μπροστινό και το πίσω άκρο της ουράς.
- Η στοίβα εκτελεί δύο λειτουργίες γνωστές ως push και pop, ενώ στην ουρά είναι γνωστή ως κατακράτηση και αποκοπή.
- Η εφαρμογή Stack είναι πιο εύκολη, ενώ η εφαρμογή Queue είναι δύσκολη.
- Η ουρά έχει παραλλαγές όπως την κυκλική ουρά, την ουρά προτεραιότητας, την ουρά διπλής τερματισμού, κλπ. Αντίθετα, η στοίβα δεν έχει παραλλαγές.
Εφαρμογή στοίβας
Η στοίβα μπορεί να εφαρμοστεί με δύο τρόπους:
- Η στατική εφαρμογή χρησιμοποιεί συστοιχίες για να δημιουργήσει μια στοίβα. Η στατική εφαρμογή είναι μια απλή τεχνική αλλά δεν είναι ένας ευέλικτος τρόπος δημιουργίας, καθώς η δήλωση του μεγέθους της στοίβας πρέπει να γίνει κατά τη διάρκεια του σχεδιασμού του προγράμματος, μετά από αυτό το μέγεθος δεν μπορεί να μεταβληθεί. Επιπλέον, η στατική εφαρμογή δεν είναι πολύ αποδοτική όσον αφορά τη χρήση της μνήμης. Δεδομένου ότι ένας πίνακας (για την υλοποίηση στοίβας) δηλώνεται πριν από την έναρξη της λειτουργίας (κατά το σχεδιασμό του προγράμματος). Τώρα, αν ο αριθμός των στοιχείων προς ταξινόμηση είναι πολύ μικρότερος στη στοίβα, η στατικά κατανεμημένη μνήμη θα σπαταληθεί. Από την άλλη πλευρά, αν υπάρχει περισσότερος αριθμός στοιχείων που πρέπει να αποθηκευτούν στη στοίβα τότε δεν μπορούμε να αλλάξουμε το μέγεθος του πίνακα για να αυξήσουμε την χωρητικότητά του έτσι ώστε να μπορεί να φιλοξενήσει νέα στοιχεία.
- Η δυναμική εφαρμογή ονομάζεται επίσης συνδυασμένη αναπαράσταση λίστας και χρησιμοποιεί δείκτες για την υλοποίηση του τύπου στοίβας της δομής δεδομένων.
Εκτέλεση ουράς
Η ουρά μπορεί να υλοποιηθεί με δύο τρόπους:
- Στατική εφαρμογή : Εάν μια ουρά υλοποιείται με συστοιχίες, ο ακριβής αριθμός στοιχείων που θέλουμε να αποθηκεύσουμε στην ουρά πρέπει να είναι προηγουμένως εξασφαλισμένος, διότι το μέγεθος του πίνακα πρέπει να δηλωθεί κατά το σχεδιασμό ή πριν ξεκινήσει η επεξεργασία. Στην περίπτωση αυτή, η αρχή του πίνακα θα γίνει το μπροστινό μέρος της ουράς, και η τελευταία θέση του πίνακα θα ενεργήσει ως το πίσω μέρος της ουράς. Η ακόλουθη σχέση δίνει όλα τα στοιχεία στην ουρά όταν υλοποιούνται με συστοιχίες:
εμπρός - πίσω + 1
Εάν "πίσω <μπροστά" τότε δεν θα υπάρχει στοιχείο στην ουρά ή η ουρά θα είναι πάντα κενή. - Δυναμική εφαρμογή : Η εφαρμογή ουρών με δείκτες, το κύριο μειονέκτημα είναι ότι ένας κόμβος σε μια συνδεδεμένη αναπαράσταση καταναλώνει περισσότερο χώρο μνήμης από ένα αντίστοιχο στοιχείο στην παράσταση του πίνακα. Δεδομένου ότι υπάρχουν τουλάχιστον δύο πεδία σε κάθε κόμβο για το πεδίο δεδομένων και άλλα για την αποθήκευση της διεύθυνσης του επόμενου κόμβου, ενώ στη συνδεδεμένη αναπαράσταση υπάρχει μόνο πεδίο δεδομένων. Το πλεονέκτημα της χρήσης της συνδεδεμένης αναπαράστασης γίνεται προφανές όταν απαιτείται η εισαγωγή ή η διαγραφή ενός στοιχείου στη μέση μιας ομάδας άλλων στοιχείων.
Λειτουργίες στο Stack
Οι βασικές λειτουργίες που μπορούν να λειτουργήσουν στη στοίβα είναι οι εξής:
- PUSH : όταν προστίθεται ένα νέο στοιχείο στην κορυφή της στοίβας είναι γνωστό ως λειτουργία PUSH. Το πάτημα ενός στοιχείου στη στοίβα απαιτεί την προσθήκη του στοιχείου, καθώς το νέο στοιχείο θα εισαχθεί στην κορυφή. Μετά από κάθε λειτουργία ώθησης, η κορυφή αυξάνεται κατά ένα. Αν ο πίνακας είναι γεμάτος και δεν μπορεί να προστεθεί κανένα νέο στοιχείο, ονομάζεται STACK-FULL condition ή STACK OVERFLOW. PUSH OPERATION - λειτουργία στο C:
Θεωρώντας τη στοίβα δηλώνεται ωςint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Όταν ένα στοιχείο διαγράφεται από την κορυφή της στοίβας, είναι γνωστό ως λειτουργία POP. Η στοίβα μειώνεται κατά ένα, μετά από κάθε λειτουργία pop. Εάν δεν υπάρχει κάποιο στοιχείο στη στοίβα και το pop έχει εκτελεστεί, τότε αυτό θα έχει ως αποτέλεσμα την κατάσταση STACK UNDERFLOW που σημαίνει ότι η στοίβα σας είναι κενή. POP OPERATION - λειτουργίες στο C:
Θεωρώντας τη στοίβα δηλώνεται ωςint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Λειτουργίες σε ουρά
Οι βασικές λειτουργίες που μπορούν να εκτελεστούν στην ουρά είναι:
- Enqueue : Για να εισαγάγετε ένα στοιχείο σε ουρά. Λειτουργία εκκένωσης σε C:
Η ουρά δηλώνεται ωςint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Για να διαγράψετε ένα στοιχείο από την ουρά. Λειτουργία εκκένωσης στη λειτουργία C:
Η ουρά δηλώνεται ωςint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Εφαρμογές του Stack
- Ανάλυση σε έναν μεταγλωττιστή.
- Εικονική μηχανή Java.
- Αναίρεση σε επεξεργαστή κειμένου.
- Επιστροφή στο κουμπί περιήγησης στο Web.
- Γλώσσα PostScript για εκτυπωτές.
- Εφαρμογή κλήσεων λειτουργίας σε έναν μεταγλωττιστή.
Εφαρμογές της ουράς
- Buffer δεδομένων
- Ασύγχρονη μεταφορά δεδομένων (αρχείο IO, σωλήνες, πρίζες).
- Κατανομή αιτημάτων σε έναν κοινόχρηστο πόρο (εκτυπωτής, επεξεργαστής).
- Ανάλυση κυκλοφορίας.
- Προσδιορίστε τον αριθμό των ταμείων που έχετε στο σούπερ μάρκετ.
συμπέρασμα
Το Stack and Queue είναι δομές γραμμικών δεδομένων που διαφέρουν με ορισμένους τρόπους, όπως ο μηχανισμός λειτουργίας, η δομή, η υλοποίηση, οι παραλλαγές, αλλά και οι δύο χρησιμοποιούνται για την αποθήκευση των στοιχείων στη λίστα και για την εκτέλεση εργασιών στη λίστα, όπως η προσθήκη και η διαγραφή των στοιχείων. Παρόλο που υπάρχουν μερικοί περιορισμοί της απλής ουράς που ανακτάται χρησιμοποιώντας άλλους τύπους ουράς.
