Εισαγωγή
Η Στοίβα είναι η δεύτερη κατά σειρά δομή δεδομένων και είναι στατική δηλ δεν μπορύμε να αυξομοιώσουμε το πλήθος των κόμβων της.
Τι είναι η στοίβα;
Στοίβα (stack), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος της στοίβας λαμβάνονται τελευταία.
Η παραπάνω μέθοδος ονομάζεται Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (=Last In First Out)
Ποιές οι κύριες λειτουργίες μιας στοίβας;
Οι κύριες λειτουργίες σε μια στοίβα είναι δύο:
- Η ώθηση (push) δηλαδή η τοποθέτηση ενός στοιχείου στην κορυφή της στοίβας.
- Η απώθηση (pop) δηλαδή η αφαίρεση ενός στοιχείου από τη στοίβα.
Τι ονομάζουμε υπερχείλιση και τι υποχείλιση;
Υπερχείλιση ονομάζουμε την κατάσταση στην οποία βρισκόμαστε όταν σε μία γεμάτη στοίβα επιχειρούμε να κάνουμε ώθηση δηλαδή να προσθέσουμε ένα νέο στοιχείο σε αυτή.
Υποχείλιση ονομάζουμε την κατάσταση στην οποία βρισκόμαστε όταν σε μία άδεια στοίβα επιχειρούμε να κάνουμε απώθηση δηλαδή να αφαιρέσουμε ένα στοιχείο από αυτή.
Σε ένα πρόγραμμα δεν πρέπει ποτέ να εμφανιστεί υπερχείλιση ή υποχείλιση. Πριν κάνουμε ώθηση θα πρέπει να ελέγχουμε ότι η στοίβα δεν είναι γεμάτη. Αντίστοιχα πριν κάνουμε απώθηση θα πρέπει να ελέγχουμε ότι η στοίβα δεν είναι άδεια.
Πως υλοποιείται μία στοίβα;
Έστω ότι θέλουμε να χρησιμοποιήσουμε μία στoίβα σε ένα από τα προγράμματα μας. Πώς δηλώνεται μία στoίβα; Πως γίνεται η ώθηση και η απώθηση; Οι συγγραφείς του βιβλίου θέλοντας να διατηρήσουν την απλότητα της ΓΛΩΣΣΑΣ μας προτρέπουν να υλοποιούμε τις στοίβες με τη χρήση πινάκων. Εκτός από τον πίνακα θα χρειαστούμε και μία ακέραια μεταβλητή η τιμή της οποίας δείχνει την θέση του τελευταίου στοιχείου της στοίβας. Οι περισσότεροι προγραμματιστές ονομάζουν την μεταβλητή αυτή top.
Ώθηση - Απώθηση
Έστω οτι έχουμε μια στοίβα με το όνομα ΜΑΘΗΤΕΣ και στην οποία σκοπεύουμε να εισάγουμε το πολύ 10 ονόματα. Ο κώδικας τόσο για την ώθηση όσο και για την απώθηση φαίνεται παρακάτω.
Ώθηση
ΓΡΑΨΕ "Πληκτρολογήστε το όνομα που θέλετε να εισάγετε στην στοίβα."
ΔΙΑΒΑΣΕ ον
ΑΝ top=10 ΤΟΤΕ
ΓΡΑΨΕ "Λυπάμαι αλλά η στοίβα είναι γεμάτη (υπερχείλιση)"
ΑΛΛΙΩΣ
top <- top + 1
ΜΑΘΗΤΕΣ[top] <- ον
ΤΕΛΟΣ_ΑΝ
Απώθηση
ΑΝ top = 0 ΤΟΤΕ
ΓΡΑΨΕ "Λυπάμαι αλλά η στοίβα είναι άδεια (υποχείλιση)"
ΑΛΛΙΩΣ
ΓΡΑΨΕ ΜΑΘΗΤΕΣ[top]
top <- top - 1
ΤΕΛΟΣ_ΑΝ
Διαδραστική Στοίβα
Ερωτήσεις ανάπτυξης απο Πανελλαδικές εξετάσεις
- Να περιγράψετε τις κύριες λειτουργίες σε μια στοίβα και να αναφέρετε τι πρέπει να ελέγχει κάθε λειτουργία, προκειμένου να μην παρουσιάζεται πρόβλημα στη λειτουργία της στοίβας. (E2010-A5)
- Στον παρακάτω πίνακα η Στήλη Α περιέχει δομές δεδομένων και η Στήλη Β περιέχει λειτουργίες. Να γράψετε στο τετράδιό σας τους αριθμούς της Στήλης Α και δίπλα τα γράμματα της Στήλης Β που αντιστοιχούν σωστά. Ας σημειωθεί ότι σε κάποιες δομές δεδομένων μπορεί να αντιστοιχούν περισσότερες από μία λειτουργίες.
Στήλη Α Στήλη Β 1. Ουρά α. Απόθηση 2. Στοίβα β. Εξαγωγή γ. Ώθηση δ. Εισαγωγή (2002-Θ1Β)
- Η «στοίβα» είναι μια δομή δεδομένων.
- Να περιγράψετε τη «στοίβα» με ένα παράδειγμα από την καθημερινή ζωή.
- Να περιγράψετε τις κύριες λειτουργίες της «στοίβας». (B2003-Θ1Α)
- Να περιγράψετε την υλοποίηση στοίβας με τη βοήθεια μονοδιάστατου πίνακα. (Ε2008-Θ1Γ)
- Πώς ονομάζονται οι δύο κύριες λειτουργίες που εκτελούνται σε μία ΣΤΟΙΒΑ δεδομένων; Τι λειτουργία επιτελούν και τι πρέπει να ελέγχεται πριν την εκτέλεσή τους; (2012-A5, Β2012-A5)
- Σε μια κενή στοίβα πρόκειται να εισαχθούν τα στοιχεία M, Δ, K, με αυτή τη σειρά. Δίνονται οι ακόλουθες σειρές διαδοχικών πράξεων (να θεωρήσετε ότι η λειτουργία της ώθησης παρουσιάζεται με το γράμμα ω και η λειτουργία της απόθησης παρουσιάζεται με το γράμμα α):
- ω, ω, ω, α, α, α
- ω, α, ω, α, ω, α
- ω, ω, α, α, ω, α
- ω, ω, α, ω, α, α
- ω, α, ω, ω, α, α
Για καθεμία από τις παραπάνω σειρές πράξεων να γράψετε στο τετράδιό σας τον αριθμό της (1 έως 5) και, δίπλα, μόνο τα στοιχεία που θα αποσυρθούν με τη σειρά απόσυρσής τους. (E2016-A5)
- x
- x