Μάθημα : ΠΛΗΡΟΦΟΡΙΚΗ ΑΕΠΠ Γ ΛΥΚΕΙΟΥ 2021-2022

Κωδικός : 0651001225

0651001225  -  ΕΥΑΓΓΕΛΙΑ ΚΟΥΝΑΒΗ

Ενότητες - Δομές δεδομένων ΣΤΟΙΒΑ

Δομές δεδομένων ΣΤΟΙΒΑ

σελ 13

http://iep.edu.gr/images/IEP/Modules/Sj_K2_Extra_Slider/Fakeloi_Ylikou/Pliroforiki-sympliromatiko-ekpaideytiko-yliko.pdf

 

Όροι:

Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (=Last In First Out).

Οι κύριες λειτουργίες σε μια στοίβα είναι δύο:
    1. Η ώθηση (push) στοιχείου στην κορυφή της στοίβας.
       Στη διαδικασία της ώθησης ελέγχουμε αν η στοίβα είναι γεμάτη.
       Στην περίπτωση που προσπαθήσουμε να «προσθέσουμε» ένα στοιχείο σε μια ήδη γεμάτη
       στοίβα, έχουμε υπερχείλιση (overflow) της στοίβας.
   2. Η απώθηση (pop) στοιχείου από τη στοίβα.
       Στη διαδικασία της απώθησης ελέγχουμε αν υπάρχει ένα τουλάχιστον στοιχείο στη στοίβα.
       Στην περίπτωση που προσπαθήσουμε να «αφαιρέσουμε» ένα στοιχείο από μία κενή στοίβα, έχουμε                   υποχείλιση (underflow) της στοίβας.

 

Υλοποίηση στοίβας με χρήση μονοδιάστατου πίνακα

   • Χρησιμοποιούμε μια βοηθητική μεταβλητή (top), που δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην        κορυφή της στοίβας.
   • Η ώθηση ενός νέου στοιχείου στη στοίβα (εισαγωγή στοιχείου στον
      πίνακα) γίνεται πάντα στην κορυφή της. Συγκεκριμένα, η μεταβλητή top
      αυξάνεται κατά ένα:
              top <-- top+1
      και στη συνέχεια γίνεται η ώθηση του στοιχείου.
   • Η απώθηση ενός στοιχείου από τη στοίβα (εξαγωγή από τον πίνακα)
      γίνεται πάντα από την κορυφή της στοίβας. Συγκεκριμένα, εξάγεται το
     στοιχείο που δείχνει η μεταβλητή top και στη συνέχεια η μεταβλητή top
     μειώνεται κατά ένα:
              top <-- top-1στοιβα

Η στοίβα είναι κενή όταν top = 0

Όταν προσπαθώ να αφαιρέσω στοιχείο από τη στοιβα που είναι κενή έχω υποχείλιση της στοίβας (underflow)

 

Η στοίβα είναι γεμάτη όταν top = v

Όταν προσπαθώ να προσθέσω στοιχείο στη στοίβα που είναι γεμάτη έχω υπερχείλιση της στοίβας (overflow)