Στοίβες

Ορισμός

• Η στοίβα (stack) είναι μια γραμμική διάταξη στοιχείων στην οποία κάθε πρόσθεση και αφαίρεση στοιχείων γίνεται μόνο στην κορυφή της.
• Στοιχεία εισάγονται με την ώθηση (push).
• Στοιχεία εξάγονται με την απώθηση (pop).
• Η μέθοδος φύλαξης που υλοποιεί η στοίβα λέγεται LIFO (Last In First Out).

Υλοποίηση στη μνήμη

• Τα στοιχεία φυλάσσονται σε διαδοχικές θέσεις.
• Ένας δείκτης ή καταχωρητής δείχνει την κορυφή της στοίβας.
• Το μέγεθος της στοίβας ορίζεται με σύμβαση.
• Πολλοί επεξεργαστές περιέχουν ειδικές εντολές για υλοποίηση στοίβας.

Υλοποίηση σε Pascal

• Η στοίβα υλοποιείται με τη μορφή πίνακα.
• Μια ξεχωριστή μεταβλητή δείχνει την κορυφή της στοίβας ή το επόμενο ελεύθερο στοιχείο.
• Απαραίτητοι οι έλεγχοι για υπερχείλιση και υποχείλιση.

Αφηρημένος τύπος

{ Αρχικοποιείται η στοίβα }

procedure stackInitialize;

{ Το στοιχείο i εισάγεται στην κορυφή της στοίβας }

procedure stackPush(i : integer);

{ Το στοιχείο από την κορυφή της στοίβας αφαιρείται και επιστρέφεται }

function stackPop : integer;

{ Επιστρέφεται αληθές αν η στοίβα είναι κενή }

function stackIsEmpty : boolean;

Εφαρμογές

• Κλήση υποπρογραμμάτων
• Χειρισμός διακοπών
• Γραφικά (τρισδιάστατη απεικόνιση)
• Λεκτική και συντακτική ανάλυση
• Αναδρομικές τεχνικές

Πολωνικός συμβολισμός

• Ο πολωνικός συμβολισμός (polish notation) προτάθηκε από τον Jan Lukasiewicz ως τρόπος συμβολισμού παραστάσεων χωρίς παρενθέσεις.
• Η τελεστές αντί να τοποθετηθούν ένθετα (infix) σε σχέση με του τελεστέους, τοποθετούνται προθεματικά (prefix)
• Ο αντίστροφος πολωνικός συμβολισμός (reverse polish notation) τοποθετεί τους τελεστές μεταθεματικά (postfix).
• Με τον τρόπο αυτό μπορεί να γίνει ο υπολογισμός αριθμητικών παραστάσεων λαμβάνοντας υπόψη την ιεραρχία των τελεστών.

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 45-55 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Dasta Structures and Algorithms, pages 53–55. Addison-Wesley, 1983.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 234–238. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 25–30. Addison-Wesley, 1990.

Ασκήσεις

Άσκηση ADS02

1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της στοίβας ακεραίων σύμφωνα με τις παρακάτω συναρτήσεις:

   { Αρχικοποιείται η στοίβα }

   procedure stackInitialize;

   { Το στοιχείο i εισάγεται στην κορυφή της στοίβας }

   procedure stackPush(i : integer);

   { Το στοιχείο από την κορυφή της στοίβας αφαιρείται και επιστρέφεται }

   function stackPop : integer;

   { Επιστρέφεται αληθές αν η στοίβα είναι κενός }

   function stackIsEmpty : bool;

2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει ακεραίους μέχρι να διαβάσει 0 και να τους τυπώνει με αντίστροφη σειρά.

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:30 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».