Στοίβα και Ουρά Θεωρία Πληροφορική Γ Λυκείου ΑΕΠΠ
Η στοίβα (stack) και η ουρά (queue) είναι δύο σπουδαίες δομές δεδομένων, που χρησιμοποιούνται σε πληθώρα πρακτικών εφαρμογών. Στη ΓΛΩΣΣΑ που θα δώσετε πανελλαδικές εξετάσεις στη πληροφορική υλοποιούνται με τη βοήθεια ενός μονοδιάστατου πίνακα και θεωρούνται στατικές δομές δεδομένων.
Σε αυτή τη σελίδα θα δείτε όλη τη θεωρία που υπάρχει για τις στοίβες και τις ουρές στην ύλη των πανελληνίων εξετάσεων της πληροφορικής Γ λυκέιου στο μάθημα του ΑΕΠΠ. Τη λειτουργία κάθε δομής, τις βασικές της πράξεις και τον τρόπο που υλοποιούνται με μονοδιάστατο πίνακα, με κώδικα σε ΓΛΩΣΣΑ και σχηματικές αναπαραστάσεις της ώθησης, της απώθησης, της εισαγωγής και της εξαγωγής.
Θα μπορέσετε να βρείτε ερωτήσεις Σωστό Λάθος, πολλαπλής επιλογής, αντιστοίχισης και ερωτήσεις ανάπτυξης σε όλη την ύλη των στατικών δομών με στοίβα και ουρά. Προσοχή μιας και δεν είναι ένα κεφάλαιο που μπορεί να εξεταστεί μόνο στο Α θέμα των εξετάσεων, μπορέι και έχει εξεταστεί πολλές φορές σαν συμπλήρωση κενών στο Β Θέμα, καθώς και σαν σχηματική αναπαράσταση στοίβας ουράς στο Α θέμα.
Θεωρία Ορισμοί Στοίβας στο ΑΕΠΠ Γ Λυκείου
Στατικές και δυναμικές δομές στη πληροφορική Γ Λυκείου
Οι δομές δεδομένων διακρίνονται σε στατικές και δυναμικές. Στις στατικές δομές το ακριβές μέγεθος της απαιτούμενης κύριας μνήμης καθορίζεται κατά τη στιγμή του προγραμματισμού και όχι κατά την εκτέλεση, και τα στοιχεία τους αποθηκεύονται σε συνεχόμενες θέσεις μνήμης. Στην πράξη οι στατικές δομές υλοποιούνται με πίνακες. Οι πίνακες χρησιμεύουν για την αποθήκευση και διαχείριση της στοίβας και της ουράς.
Στοίβα Ορισμός ΑΕΠΠ
Αυτή η μέθοδος επεξεργασίας ονομάζεται Τελευταίο μέσα, πρώτο έξω ή, με την αγγλική συντομογραφία, LIFO (Last-In-First-Out). Η επεξεργασία της στοίβας γίνεται από το ένα μόνο άκρο της, την κορυφή.
Οι βασικές πράξεις της στοίβας στο ΑΕΠΠ
| Πράξη | Αγγλικός όρος | Τι κάνει | Έλεγχος |
|---|---|---|---|
| Ώθηση | push | Τοποθετεί ένα στοιχείο στην κορυφή της στοίβας. | Αν η στοίβα είναι γεμάτη, συμβαίνει υπερχείλιση (overflow). |
| Απώθηση | pop | Αφαιρεί το στοιχείο της κορυφής από τη στοίβα. | Αν η στοίβα είναι άδεια, συμβαίνει υποχείλιση (underflow). |
Η διαδικασία της ώθησης πρέπει οπωσδήποτε να ελέγχει αν η στοίβα είναι γεμάτη. Αντίστοιχα, η διαδικασία της απώθησης ελέγχει αν υπάρχει ένα τουλάχιστον στοιχείο στη στοίβα.
Υλοποίηση στοίβας με μονοδιάστατο πίνακα σχήμα και μεθοδολογία για το ΑΕΠΠ
Μια στοίβα μπορεί να υλοποιηθεί πολύ εύκολα με τη βοήθεια ενός μονοδιάστατου πίνακα. Μια βοηθητική μεταβλητή, με όνομα συνήθως top, χρησιμοποιείται για να δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή της στοίβας.
- Ώθηση: αυξάνεται η μεταβλητή top κατά ένα και στη θέση αυτή εισέρχεται το στοιχείο.
- Απώθηση: εξέρχεται πρώτα το στοιχείο που δείχνει η μεταβλητή top και στη συνέχεια η top μειώνεται κατά ένα, για να δείχνει τη νέα κορυφή.
Σχηματική αναπαράσταση της ώθησης σε στοίβα στο ΑΕΠΠ
Στα σχήματα χρησιμοποιείται πίνακας 5 θέσεων. Στο σχήμα που ακολουθεί ωθείται το στοιχείο 12 σε στοίβα που περιέχει ήδη τα στοιχεία 5 και 8.
Πριν (top = 2)
① top ← top + 1 (top = 3)
② Α[3] ← 12
➜
Μετά (top = 3)
Το νέο στοιχείο (πορτοκαλί κελί) τοποθετείται πάντοτε πάνω από την προηγούμενη κορυφή.
Σχηματική αναπαράσταση της απώθησης σε στοίβα στο ΑΕΠΠ
Στο επόμενο σχήμα απωθείται το στοιχείο της κορυφής, το 12.
Πριν (top = 3)
① στοιχείο ← Α[3] (βγαίνει το 12)
② top ← top − 1 (top = 2)
➜
Μετά (top = 2)
στοίβας
Το στοιχείο που μπήκε τελευταίο (12) βγαίνει πρώτο, δηλαδή η στοίβα λειτουργεί με τη μέθοδο LIFO. Μετά την απώθηση το στοιχείο δεν σβήνεται από τον πίνακα (γκρι κελί). Απλώς μειώνεται η top και το στοιχείο θεωρείται εκτός στοίβας. Την επόμενη ώθηση θα αντικατασταθεί από το νέο στοιχείο.
Δηλώσεις και αρχική κατάσταση της στοίβας στο ΑΕΠΠ
Στον κώδικα η στοίβα έχει χωρητικότητα 10 στοιχείων. Η στοίβα είναι κενή όταν top = 0 και γεμάτη όταν top = 10.
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[10], top, στοιχείο
ΑΡΧΗ
top <- 0 ! κενή στοίβα
...
Θεωρία ωθησης στοιχείου σε στοίβα στο ΑΕΠΠ
ΔΙΑΒΑΣΕ στοιχείο
ΑΝ top = 10 ΤΟΤΕ
ΓΡΑΨΕ 'Γεμάτη στοίβα - υπερχείλιση'
ΑΛΛΙΩΣ
top <- top + 1
Α[top] <- στοιχείο
ΤΕΛΟΣ_ΑΝ
Θεωρία απώθησης στοιχείου σε στοίβα στο ΑΕΠΠ
ΑΝ top = 0 ΤΟΤΕ
ΓΡΑΨΕ 'Άδεια στοίβα - υποχείλιση'
ΑΛΛΙΩΣ
στοιχείο <- Α[top]
top <- top - 1
ΓΡΑΨΕ στοιχείο
ΤΕΛΟΣ_ΑΝ
Θεωρία Ορισμοί Ουρά στο ΑΕΠΠ Γ Λυκείου
Οι ουρές είναι καθημερινό φαινόμενο. Ουρές δημιουργούνται όταν άνθρωποι, αυτοκίνητα, εργασίες, προγράμματα κ.λπ. περιμένουν για να εξυπηρετηθούν. Το θέμα είναι τόσο σημαντικό, ώστε ένας ιδιαίτερος κλάδος των Μαθηματικών, η Επιχειρησιακή Έρευνα, και ιδιαίτερα η θεωρία Ουρών, μελετά τη συμπεριφορά και την επίδοση των ουρών.
Οι βασικές πράξεις της Ουράς στο ΑΕΠΠ
| Πράξη | Αγγλικός όρος | Τι κάνει |
|---|---|---|
| Εισαγωγή | enqueue | Προσθέτει ένα στοιχείο στο πίσω άκρο της ουράς. |
| Εξαγωγή | dequeue | Αφαιρεί ένα στοιχείο από το εμπρός άκρο της ουράς. |
Σε αντίθεση με τη στοίβα, στην περίπτωση της ουράς απαιτούνται δύο δείκτες: ο εμπρός (front) και ο πίσω (rear) δείκτης. Μας δίνουν τη θέση του στοιχείου που σε πρώτη ευκαιρία θα εξαχθεί και τη θέση του στοιχείου που μόλις εισήλθε. Η επεξεργασία της ουράς γίνεται και από τα δύο άκρα της: στο ένα άκρο πραγματοποιείται πάντοτε η εισαγωγή και στο άλλο η εξαγωγή.
Υλοποίηση ουράς με μονοδιάστατο πίνακα και θεωρία ΑΕΠΠ
Μια ουρά μπορεί να υλοποιηθεί με τη βοήθεια ενός μονοδιάστατου πίνακα και των δύο δεικτών front και rear.
- Εισαγωγή: αυξάνεται ο δείκτης rear κατά ένα και στη θέση αυτή αποθηκεύεται το στοιχείο.
- Εξαγωγή: εξέρχεται το στοιχείο που δείχνει ο δείκτης front, ο οποίος στη συνέχεια αυξάνεται κατά ένα, για να δείχνει το επόμενο στοιχείο που πρόκειται να εξαχθεί.
Σε κάθε περίπτωση, πριν από οποιαδήποτε ενέργεια πρέπει να ελέγχεται αν υπάρχει ελεύθερος χώρος στον πίνακα για την εισαγωγή και αν υπάρχει ένα τουλάχιστον στοιχείο για την εξαγωγή.
Σχηματική αναπαράσταση της εισαγωγής σε ουρά στο ΑΕΠΠ
Στα σχήματα χρησιμοποιείται πίνακας 5 θέσεων. Στο σχήμα που ακολουθεί εισάγεται το στοιχείο 9 σε ουρά που περιέχει ήδη τα στοιχεία 7 και 3.
Πριν (front = 1, rear = 2)
① rear ← rear + 1 (rear = 3)
② Α[3] ← 9
▼
Μετά (front = 1, rear = 3)
Το νέο στοιχείο (πορτοκαλί κελί) μπαίνει πάντοτε μετά το τελευταίο στοιχείο της ουράς και ο δείκτης rear μετακινείται πάνω σε αυτό. Στην πρώτη εισαγωγή σε κενή ουρά (front = 0 και rear = 0) και οι δύο δείκτες παίρνουν την τιμή 1.
Σχηματική αναπαράσταση της εξαγωγής από ουρά στο ΑΕΠΠ
Στο επόμενο σχήμα εξάγεται το στοιχείο του εμπρός άκρου, το 7.
Πριν (front = 1, rear = 3)
① στοιχείο ← Α[1] (βγαίνει το 7)
② front ← front + 1 (front = 2)
▼
Μετά (front = 2, rear = 3)
Το στοιχείο που μπήκε πρώτο (7) βγαίνει πρώτο, δηλαδή η ουρά λειτουργεί με τη μέθοδο FIFO. Κατά την εξαγωγή αυξάνεται απλώς ο δείκτης front και δεν γίνεται καμία παρέμβαση στα περιεχόμενα του πίνακα (γκρι κελί). Όταν εξαχθεί το τελευταίο στοιχείο (front = rear), η ουρά αδειάζει και οι δύο δείκτες παίρνουν ξανά την τιμή 0.
Δηλώσεις και αρχική κατάσταση της ουράς στο ΑΕΠΠ
Στον κώδικα η ουρά έχει χωρητικότητα 10 στοιχείων. Όταν η ουρά είναι κενή, front = 0 και rear = 0.
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[10], front, rear, στοιχείο
ΑΡΧΗ
front <- 0 ! κενή ουρά
rear <- 0
...
Εισαγωγή στοιχείου σε ουρά στο ΑΕΠΠ θεωρία αλγορίθμου
ΔΙΑΒΑΣΕ στοιχείο
ΑΝ rear = 10 ΤΟΤΕ
ΓΡΑΨΕ 'Γεμάτη ουρά'
ΑΛΛΙΩΣ_ΑΝ front = 0 ΚΑΙ rear = 0 ΤΟΤΕ
front <- 1 ! πρώτη εισαγωγή σε κενή ουρά
rear <- 1
Α[rear] <- στοιχείο
ΑΛΛΙΩΣ
rear <- rear + 1
Α[rear] <- στοιχείο
ΤΕΛΟΣ_ΑΝ
Εξαγωγή στοιχείου από ουρά στο ΑΕΠΠ θεωρία αλγορίθμου
ΑΝ front = 0 ΤΟΤΕ
ΓΡΑΨΕ 'Άδεια ουρά'
ΑΛΛΙΩΣ
στοιχείο <- Α[front]
ΓΡΑΨΕ στοιχείο
ΑΝ front = rear ΤΟΤΕ
front <- 0 ! βγήκε το τελευταίο στοιχείο, η ουρά αδειάζει
rear <- 0
ΑΛΛΙΩΣ
front <- front + 1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
Σύγκριση στοίβας και ουράς θεωρία ΑΕΠΠ Γ Λυκείου
| Στοίβα | Ουρά | |
|---|---|---|
| Μέθοδος επεξεργασίας | LIFO: τελευταίο μέσα, πρώτο έξω. | FIFO: πρώτο μέσα, πρώτο έξω. |
| Άκρα επεξεργασίας | Ένα (η κορυφή). | Δύο (εισαγωγή στο πίσω άκρο, εξαγωγή από το εμπρός). |
| Δείκτες | Ένας: top. | Δύο: front και rear. |
| Πράξεις | Ώθηση (push) και απώθηση (pop). | Εισαγωγή (enqueue) και εξαγωγή (dequeue). |
| Έλεγχοι | Υπερχείλιση (γεμάτη στοίβα) και υποχείλιση (άδεια στοίβα). | Έλεγχος γεμάτης και άδειας ουράς. |
| Υλοποίηση στη ΓΛΩΣΣΑ | Στατική δομή, με μονοδιάστατο πίνακα. | |
Μέθοδοι Θεωρία Ορισμός LIFO και FIFO στο ΑΕΠΠ
Οι δύο μέθοδοι έχουν αρκετές χρήσεις σε πραγματικά προβλήματα. Μια σημαντική εφαρμογή των στοιβών είναι η αναδρομή, δηλαδή η δυνατότητα μιας διαδικασίας ή συνάρτησης να καλεί τον εαυτό της. Οι ουρές εμφανίζονται παντού όπου εργασίες ή προγράμματα περιμένουν να εξυπηρετηθούν.
Ένα παράδειγμα είναι η αποθήκη μιας επιχείρησης, όπου η εξαγωγή ειδών με τη μέθοδο FIFO ή LIFO επηρεάζει το κόστος και το κέρδος. Έστω ότι η επιχείρηση αγόρασε 4 τεμάχια προς 10 € (1/1/02) και 6 τεμάχια προς 12 € (15/1/02), δηλαδή 10 τεμάχια συνολικής αξίας 112 €, και στις 30/1/02 πούλησε 5 τεμάχια προς 100 €.
| Μέθοδος | Ποια τεμάχια θεωρείται ότι πουλήθηκαν | Κόστος | Καθαρό κέρδος |
|---|---|---|---|
| LIFO | Τα 5 από την τελευταία αγορά (12 €). | 60 € | 40 € |
| FIFO | Τα 4 από την πρώτη αγορά και 1 από τη δεύτερη. | 52 € | 48 € |
| Σταθμική μέση τιμή | Μέση τιμή 112/10 = 11,2 € ανά τεμάχιο. | 56 € | 44 € |
Στα είδη που αλλοιώνονται ή έχουν ημερομηνία λήξης (π.χ. φάρμακα) πρέπει να επιλέγεται το παλαιότερο, άρα η εξαγωγή γίνεται με τη μέθοδο FIFO.
Συχνές ερωτήσεις για τη Στοίβα και την Ουρά
Θεωρία του ΑΕΠΠ
Τι είναι η στοίβα;
Είναι μια δομή δεδομένων που λειτουργεί όπως μια στοίβα από πιάτα: τα δεδομένα της κορυφής λαμβάνονται πρώτα, ενώ αυτά του βάθους λαμβάνονται τελευταία. Η μέθοδος αυτή ονομάζεται LIFO (Last-In-First-Out).
Ποιες είναι οι κύριες λειτουργίες της στοίβας;
Η ώθηση (push), που τοποθετεί ένα στοιχείο στην κορυφή της στοίβας, και η απώθηση (pop), που αφαιρεί το στοιχείο της κορυφής. Η ώθηση ελέγχει αν η στοίβα είναι γεμάτη (υπερχείλιση) και η απώθηση αν είναι άδεια (υποχείλιση).
Πώς υλοποιείται η στοίβα με μονοδιάστατο πίνακα;
Με έναν πίνακα και μια βοηθητική μεταβλητή top, που δείχνει το στοιχείο που τοποθετήθηκε τελευταίο. Στην ώθηση αυξάνεται η top κατά ένα και στη θέση αυτή αποθηκεύεται το στοιχείο. Στην απώθηση εξάγεται το στοιχείο που δείχνει η top και μετά η top μειώνεται κατά ένα.
Τι είναι η ουρά;
Είναι μια δομή δεδομένων όπου εξυπηρετείται πρώτο το στοιχείο που μπήκε πρώτο, όπως σε μια ουρά αναμονής ανθρώπων. Η μέθοδος αυτή ονομάζεται FIFO (First-In-First-Out).
Ποιες είναι οι κύριες λειτουργίες της ουράς;
Η εισαγωγή (enqueue) ενός στοιχείου στο πίσω άκρο της ουράς και η εξαγωγή (dequeue) ενός στοιχείου από το εμπρός άκρο της ουράς.
Γιατί η ουρά χρειάζεται δύο δείκτες και η στοίβα έναν;
Η στοίβα επεξεργάζεται μόνο το ένα άκρο της, την κορυφή, οπότε αρκεί ο δείκτης top. Η ουρά επεξεργάζεται και τα δύο άκρα: ο δείκτης front δείχνει το στοιχείο που θα εξαχθεί πρώτο και ο rear το στοιχείο που μόλις εισήλθε.
Πώς υλοποιείται η ουρά με μονοδιάστατο πίνακα;
Με έναν πίνακα και δύο δείκτες, front και rear. Στην εισαγωγή αυξάνεται ο rear κατά ένα και στη θέση αυτή αποθηκεύεται το στοιχείο. Στην εξαγωγή εξάγεται το στοιχείο που δείχνει ο front, ο οποίος μετά αυξάνεται κατά ένα. Πριν από κάθε ενέργεια ελέγχεται αν η ουρά είναι γεμάτη ή άδεια.
Είναι στατικές ή δυναμικές δομές η στοίβα και η ουρά στη ΓΛΩΣΣΑ;
Στη ΓΛΩΣΣΑ η στοίβα και η ουρά θεωρούνται στατικές δομές, γιατί υλοποιούνται με μονοδιάστατους πίνακες, των οποίων το μέγεθος δηλώνεται πριν από την έναρξη του προγράμματος. Οι δυναμικές δομές (λίστες, δένδρα, γράφοι) δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης και δεν έχουν σταθερό μέγεθος.

