Περιεχόμενο

• Συγκριτικό διάγραμμα
• Ορισμός του Stack
• Παράδειγμα
• Ορισμός της ουράς
• Παράδειγμα
• Εφαρμογή στοίβας
• Εκτέλεση ουράς
• Λειτουργίες στο Stack
• Λειτουργίες σε ουρά
• Εφαρμογές του Stack
• Εφαρμογές της ουράς
• συμπέρασμα

Η στοίβα και η ουρά είναι οι μη πρωτότυπες δομές δεδομένων. Οι κύριες διαφορές μεταξύ της στοίβας και της ουράς είναι ότι η στοίβα χρησιμοποιεί τη μέθοδο LIFO (τελευταία σε πρώτη έξοδο) για την πρόσβαση και την προσθήκη δεδομένων, ενώ η ουρά χρησιμοποιεί τη μέθοδο FIFO (πρώτη σε πρώτη έξοδο) για την πρόσβαση και την προσθήκη στοιχείων δεδομένων.

Η στοίβα έχει μόνο ένα άκρο ανοιχτό για την ώθηση και την απόσπαση των στοιχείων δεδομένων από την άλλη πλευρά Η ουρά έχει και τα δύο άκρα ανοιχτά για να συμπιέζει και να αποσπάσει τα στοιχεία δεδομένων.

Η στοίβα και η ουρά είναι οι δομές δεδομένων που χρησιμοποιούνται για την αποθήκευση δεδομένων και στην πραγματικότητα βασίζονται σε κάποιο πραγματικό παγκόσμιο ισοδύναμο. Για παράδειγμα, η στοίβα είναι μια στοίβα από CD όπου μπορείτε να βγάλετε και να βάλετε CD μέσα από την κορυφή της στοίβας των CD. Ομοίως, η ουρά είναι μια ουρά για τα εισιτήρια Θεάτρου όπου το άτομο που στέκεται στην πρώτη θέση, δηλ. Το μπροστινό μέρος της ουράς θα εξυπηρετηθεί πρώτα και το νέο πρόσωπο που θα φτάσει θα εμφανιστεί στο πίσω μέρος της ουράς (πίσω άκρο της ουράς).

1. Συγκριτικό διάγραμμα
2. Ορισμός
3. Βασικές διαφορές
4. Εκτέλεση
5. Λειτουργίες
6. Εφαρμογές
7. συμπέρασμα

Συγκριτικό διάγραμμα

Βάση σύγκρισης	Σωρός	Ουρά
Αρχή λειτουργίας	LIFO (Τελευταία στην πρώτη)	FIFO (Πρώτη σε πρώτη θέση)
Δομή	Το ίδιο τέλος χρησιμοποιείται για την εισαγωγή και τη διαγραφή στοιχείων.	Ένα άκρο χρησιμοποιείται για την εισαγωγή, δηλ. Το οπίσθιο άκρο και ένα άλλο άκρο χρησιμοποιείται για διαγραφή στοιχείων, δηλ. Εμπρόσθιου άκρου.
Αριθμός χρησιμοποιημένων δεικτών	Ενας	Δύο (σε περίπτωση απλής ουράς)
Εκτελούνται οι λειτουργίες	Πιέστε και Ποπ	Περικοπή και αποκόλληση
Εξέταση της κενής κατάστασης	Κορυφή == -1	Μπροστά == -1 || Μπροστά == Πίσω + 1
Εξέταση της πλήρους κατάστασης	Κορυφή == Μέγιστο - 1	Πίσω == Μέγιστο - 1
Παραλλαγές	Δεν έχει παραλλαγές.	Έχει παραλλαγές όπως η κυκλική ουρά, η ουρά προτεραιότητας, η ουρά διπλής αρίθμησης.
Εκτέλεση	Απλούστερη	Συγκριτικά πολύπλοκο

Ορισμός του Stack

Μια στοίβα είναι μια μη πρωτόγονη δομή γραμμικών δεδομένων. Πρόκειται για μια διατεταγμένη λίστα όπου προστίθεται το νέο στοιχείο και το υπάρχον στοιχείο διαγράφεται από ένα μόνο άκρο, το οποίο καλείται ως το κορυφαίο της στοίβας (TOS). Καθώς όλη η διαγραφή και εισαγωγή σε μια στοίβα γίνεται από την κορυφή της στοίβας, το τελευταίο στοιχείο που προστέθηκε θα είναι το πρώτο που θα αφαιρεθεί από τη στοίβα. Αυτός είναι ο λόγος για τον οποίο η στοίβα ονομάζεται λίστα τύπου Last-in-First-out (LIFO).

Σημειώστε ότι το στοιχείο που είναι συχνά προσπελάσιμο στη στοίβα είναι το κορυφαίο στοιχείο, ενώ το τελευταίο διαθέσιμο στοιχείο βρίσκεται στο κάτω μέρος της στοίβας.

Παράδειγμα

Μερικοί από εσάς μπορεί να φάτε μπισκότα (ή Poppins). Εάν υποθέσετε, μόνο μία πλευρά του καλύμματος είναι σκισμένη και τα μπισκότα εξάγονται ένα προς ένα. Αυτό είναι που λέγεται popping, και ομοίως, αν θέλετε να διατηρήσετε κάποια μπισκότα για κάποιο χρονικό διάστημα αργότερα, θα τα βάλετε πίσω στο πακέτο μέσω του ίδιου σχισμένου άκρου που ονομάζεται pushing.

Ορισμός της ουράς

Μια ουρά είναι μια γραμμική δομή δεδομένων που έρχεται στην κατηγορία του μη πρωτόγονου τύπου. Πρόκειται για μια συλλογή παρόμοιων στοιχείων. Η προσθήκη νέων στοιχείων λαμβάνει χώρα στο ένα άκρο που ονομάζεται οπίσθιο τμήμα. Ομοίως, η διαγραφή των υπαρχόντων στοιχείων πραγματοποιείται στο άλλο άκρο που ονομάζεται Front-end και είναι λογικά ένας τύπος πρώτης κατηγορίας (FIFO).

Παράδειγμα

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

1. Η στοίβα ακολουθεί τον μηχανισμό LIFO από την άλλη πλευρά Η ουρά ακολουθεί τον μηχανισμό FIFO για να προσθέσει και να αφαιρέσει στοιχεία.
2. Σε μια στοίβα, το ίδιο τέλος χρησιμοποιείται για την εισαγωγή και τη διαγραφή των στοιχείων. Αντίθετα, στην ουρά χρησιμοποιούνται δύο διαφορετικοί άξονες για την εισαγωγή και τη διαγραφή των στοιχείων.
3. Δεδομένου ότι η στοίβα έχει μόνο ένα ανοιχτό άκρο, αυτός είναι ο λόγος που χρησιμοποιείται μόνο ένας δείκτης για να αναφερθεί στην κορυφή της στοίβας. Ωστόσο, η ουρά χρησιμοποιεί δύο δείκτες για να αναφερθεί το μπροστινό και το πίσω άκρο της ουράς.
4. Η στοίβα εκτελεί δύο λειτουργίες γνωστές ως push και pop, ενώ στην ουρά είναι γνωστή ως κατακράτηση και αποκοπή.
5. Η εφαρμογή Stack είναι πιο εύκολη, ενώ η εφαρμογή Queue είναι δύσκολη.
6. Η ουρά έχει παραλλαγές όπως την κυκλική ουρά, την ουρά προτεραιότητας, την ουρά διπλής τερματισμού, κλπ. Αντίθετα, η στοίβα δεν έχει παραλλαγές.

Εφαρμογή στοίβας

Η στοίβα μπορεί να εφαρμοστεί με δύο τρόπους:

1. Στατική εφαρμογή χρησιμοποιεί συστοιχίες για να δημιουργήσει μια στοίβα. Η στατική εφαρμογή είναι μια απλή τεχνική αλλά δεν είναι ένας ευέλικτος τρόπος δημιουργίας, καθώς η δήλωση του μεγέθους της στοίβας πρέπει να γίνει κατά τη διάρκεια του σχεδιασμού του προγράμματος, μετά από αυτό το μέγεθος δεν μπορεί να μεταβληθεί. Επιπλέον, η στατική εφαρμογή δεν είναι πολύ αποδοτική όσον αφορά τη χρήση της μνήμης. Δεδομένου ότι ένας πίνακας (για την υλοποίηση στοίβας) δηλώνεται πριν από την έναρξη της λειτουργίας (κατά το σχεδιασμό του προγράμματος). Τώρα, αν ο αριθμός των στοιχείων προς ταξινόμηση είναι πολύ μικρότερος στη στοίβα, η στατικά κατανεμημένη μνήμη θα σπαταληθεί. Από την άλλη πλευρά, αν υπάρχει περισσότερος αριθμός στοιχείων που πρέπει να αποθηκευτούν στη στοίβα τότε δεν μπορούμε να αλλάξουμε το μέγεθος του πίνακα για να αυξήσουμε την χωρητικότητά του έτσι ώστε να μπορεί να φιλοξενήσει νέα στοιχεία.
2. Δυναμική υλοποίηση ονομάζεται επίσης συνδεδεμένη αναπαράσταση λίστας και χρησιμοποιεί δείκτες για την υλοποίηση του τύπου στοίβας της δομής δεδομένων.

Εκτέλεση ουράς

Η ουρά μπορεί να υλοποιηθεί με δύο τρόπους:

1. Στατική εφαρμογή: Εάν μια ουρά υλοποιείται με συστοιχίες, ο ακριβής αριθμός των στοιχείων που θέλουμε να αποθηκεύσουμε στην ουρά πρέπει να διασφαλιστεί προηγουμένως, επειδή το μέγεθος του πίνακα πρέπει να δηλωθεί κατά το σχεδιασμό ή πριν αρχίσει η επεξεργασία. Στην περίπτωση αυτή, η αρχή του πίνακα θα γίνει το μπροστινό μέρος της ουράς, και η τελευταία θέση του πίνακα θα ενεργήσει ως το πίσω μέρος της ουράς. Η ακόλουθη σχέση δίνει όλα τα στοιχεία στην ουρά όταν υλοποιούνται με συστοιχίες:
   εμπρός - πίσω + 1
   Εάν "πίσω <μπροστά" τότε δεν θα υπάρχει στοιχείο στην ουρά ή η ουρά θα είναι πάντα κενή.
2. Δυναμική υλοποίηση: Εφαρμογή ουρών με δείκτες, το κύριο μειονέκτημα είναι ότι ένας κόμβος σε μια συνδεδεμένη αναπαράσταση καταναλώνει περισσότερο χώρο μνήμης από ένα αντίστοιχο στοιχείο στην παράσταση του πίνακα. Δεδομένου ότι υπάρχουν τουλάχιστον δύο πεδία σε κάθε κόμβο για το πεδίο δεδομένων και άλλα για την αποθήκευση της διεύθυνσης του επόμενου κόμβου, ενώ στη συνδεδεμένη αναπαράσταση υπάρχει μόνο πεδίο δεδομένων. Το πλεονέκτημα της χρήσης της συνδεδεμένης αναπαράστασης γίνεται προφανές όταν απαιτείται η εισαγωγή ή η διαγραφή ενός στοιχείου στη μέση μιας ομάδας άλλων στοιχείων.

Λειτουργίες στο Stack

Οι βασικές λειτουργίες που μπορούν να λειτουργήσουν στη στοίβα είναι οι εξής:

1. ΣΠΡΩΞΤΕ: όταν προστίθεται ένα νέο στοιχείο στην κορυφή της στοίβας είναι γνωστό ως λειτουργία PUSH. Το πάτημα ενός στοιχείου στη στοίβα απαιτεί την προσθήκη του στοιχείου, καθώς το νέο στοιχείο θα εισαχθεί στην κορυφή. Μετά από κάθε λειτουργία ώθησης, η κορυφή αυξάνεται κατά ένα. Αν ο πίνακας είναι γεμάτος και δεν μπορεί να προστεθεί κανένα νέο στοιχείο, ονομάζεται STACK-FULL condition ή STACK OVERFLOW. PUSH OPERATION - λειτουργία στο C:
   Θεωρώντας τη στοίβα δηλώνεται ως
   int στοίβα, κορυφή = -1;
άκυρη ώθηση ()
{
int στοιχείο?
αν (πάνω από 4)
{
f ("Εισάγετε τον αριθμό").
σάρωση ("% d", & στοιχείο);
αρχή = κορυφή + 1;
stack = στοιχείο;
}
αλλού
{
f ("Η στοίβα είναι γεμάτη").
}
}
2. ΚΡΟΤΟΣ: Όταν ένα στοιχείο διαγράφεται από την κορυφή της στοίβας, είναι γνωστό ως λειτουργία POP. Η στοίβα μειώνεται κατά ένα, μετά από κάθε λειτουργία pop. Εάν δεν υπάρχει κάποιο στοιχείο στη στοίβα και το pop έχει εκτελεστεί, τότε αυτό θα έχει ως αποτέλεσμα την κατάσταση STACK UNDERFLOW που σημαίνει ότι η στοίβα σας είναι κενή. POP OPERATION - λειτουργίες στο C:
   Θεωρώντας τη στοίβα δηλώνεται ως
   int στοίβα, κορυφή = -1;
void pop ()
{
int στοιχείο?
αν (άνω> = 4)
{
στοιχείο = στοίβα;
αρχή = κορυφή - 1;
f ("Ο αριθμός που έχει διαγραφεί είναι =% d", στοιχείο).
}
αλλού
{
f ("Η στοίβα είναι κενή").
}
}

Λειτουργίες σε ουρά

Οι βασικές λειτουργίες που μπορούν να εκτελεστούν στην ουρά είναι:

1. Περπατήστε: Για να εισαγάγετε ένα στοιχείο σε ουρά.Γραμμή λειτουργίας εκκένωση σε C:
   Η ουρά δηλώνεται ως
   int ουρά, Front = -1 και rear = -1.
void add ()
{
int στοιχείο?
αν (πίσω <4)
{
f ("Εισάγετε τον αριθμό").
σάρωση ("% d", & στοιχείο);
αν (εμπρός == -1)
{
εμπρός = 0;
πίσω = 0;
}
αλλού
{
πίσω = πίσω + 1;
}
ουρά = στοιχείο;
}
αλλού
{
f ("Η ουρά είναι γεμάτη").
}
}

2. Αποκόψτε: Για να διαγράψετε ένα στοιχείο από την ουρά. Λειτουργία εκκένωσης σε C:
   Η ουρά δηλώνεται ως
   int ουρά, Front = -1 και rear = -1.
void delete ()
{
int στοιχείο?
εάν (μπροστά! = -1)
{
στοιχείο = ουρά.
αν (εμπρός == πίσω)
{
μπροστά = -1.
πίσω = -1.
}
αλλού
{
μπροστά = εμπρός + 1;
f ("Ο αριθμός που έχει διαγραφεί είναι =% d", στοιχείο).
}
}
αλλού
{
f ("Η ουρά είναι κενή").
}
}

Εφαρμογές του Stack

• Ανάλυση σε έναν μεταγλωττιστή.
• Εικονική μηχανή Java.
• Αναίρεση σε επεξεργαστή κειμένου.
• Επιστροφή στο κουμπί περιήγησης στο Web.
• Γλώσσα PostScript για ers.
• Εφαρμογή κλήσεων λειτουργίας σε έναν μεταγλωττιστή.

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

• Buffer δεδομένων
• Ασύγχρονη μεταφορά δεδομένων (αρχείο IO, σωλήνες, πρίζες).
• Υποβολή αιτήσεων σε έναν κοινόχρηστο πόρο (er, επεξεργαστής).
• Ανάλυση κυκλοφορίας.
• Προσδιορίστε τον αριθμό των ταμείων που έχετε στο σούπερ μάρκετ.

συμπέρασμα

Το Stack and Queue είναι δομές γραμμικών δεδομένων που διαφέρουν με ορισμένους τρόπους, όπως ο μηχανισμός λειτουργίας, η δομή, η υλοποίηση, οι παραλλαγές, αλλά και οι δύο χρησιμοποιούνται για την αποθήκευση των στοιχείων στη λίστα και για την εκτέλεση εργασιών στη λίστα, όπως η προσθήκη και η διαγραφή των στοιχείων. Παρόλο που υπάρχουν μερικοί περιορισμοί της απλής ουράς που ανακτάται χρησιμοποιώντας άλλους τύπους ουράς.