Η Στοίβα (Stack)

Μάθημα 1: Η Στοίβα (Stack)

Διάρκεια: 45 Λεπτά
Πηγή: Συμπληρωματικό Υλικό, Κεφάλαιο Δομές Δεδομένων

Εισαγωγή

Δείτε το παρακάτω βίντεο για να καταλάβετε πώς λειτουργεί η "ανάκληση" ενεργειών (Undo) στον υπολογιστή σας.

1. Τι είναι η Στοίβα;

Η Στοίβα είναι μια γραμμική δομή δεδομένων. Φανταστείτε την σαν μια στοίβα πιάτων: Μπορούμε να προσθέσουμε ή να αφαιρέσουμε στοιχεία μόνο από την κορυφή.

  • LIFO (Last In, First Out): Το στοιχείο που μπαίνει τελευταίο, βγαίνει πρώτο.
  • Δείκτης Κορυφής (Top): Μια μεταβλητή (ακέραιος) που μας δείχνει σε ποια θέση του πίνακα βρίσκεται το τελευταίο στοιχείο.

Checkpoint #1: Κριτική Σκέψη

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

Σκέψου πριν απαντήσεις: Όταν πατάς το κουμπί "Πίσω" στον browser σου, σε ποια σελίδα σε πηγαίνει; Στην πρώτη που άνοιξες σήμερα ή στην αμέσως προηγούμενη;

Πρόκληση: Στην παρακάτω άσκηση υπάρχουν πολλαπλές σωστές απαντήσεις. Μπορείς να τις βρεις όλες χωρίς να κάνεις λάθος;

2. Οι Λειτουργίες Push & Pop

Στη Γ' Λυκείου μελετάμε την υλοποίηση στοίβας με τη χρήση μονοδιάστατου πίνακα.

⬆️ Ώθηση (Push)

Είναι η εισαγωγή στοιχείου.

  1. Ελέγχουμε αν η στοίβα είναι Γεμάτη (Υπερχείλιση).
  2. Αυξάνουμε το top κατά 1.
  3. Τοποθετούμε το στοιχείο στη θέση top.

⬇️ Απώθηση (Pop)

Είναι η εξαγωγή στοιχείου.

  1. Ελέγχουμε αν η στοίβα είναι Άδεια (Υποχείλιση).
  2. Παίρνουμε το στοιχείο από τη θέση top.
  3. Μειώνουμε το top κατά 1.

Checkpoint #2 (Προσομοίωση)

Οδηγία: στο e-me content ένα "Course Presentation" με διαφάνειες που δείχνουν την εξέλιξη του πίνακα.

Άσκηση: Έχουμε πίνακα 5 θέσεων. Push(A), Push(B), Pop(), Push(C). Ποιο στοιχείο είναι στο top;

Ο Κόσμος των Δομών Δεδομένων