Εκπαίδευση στη Δομή Δεδομένων Στοίβα

Θεωρία για τη Στοίβα

Η στοίβα (stack) είναι μια γραμμική δομή δεδομένων που ακολουθεί την αρχή LIFO (Last In, First Out). Αυτό σημαίνει ότι το τελευταίο στοιχείο που προστέθηκε είναι το πρώτο που θα αφαιρεθεί.

Υλοποίηση Στοίβας

Η υλοποίηση της στοίβας γίνεται με μονοδιάστατο πίνακα. Η κορυφή της στοίβας παρακολουθείται με έναν δείκτη top.

Βασικές Λειτουργίες

Δημιουργία στοίβας: Αρχικοποίηση μιας κενής στοίβας.
Ωθήση (Push): Προσθήκη ενός στοιχείου στην κορυφή της στοίβας, εφόσον δεν είναι γεμάτη (υπερχείλιση - overflow).
Απώθηση (Pop): Αφαίρεση του στοιχείου από την κορυφή της στοίβας, εφόσον δεν είναι άδεια (υποχείλιση - underflow).

Σφάλματα στη Στοίβα

Υπερχείλιση (Overflow): Προκύπτει όταν προσπαθούμε να προσθέσουμε ένα στοιχείο σε μια στοίβα που είναι ήδη γεμάτη.
Υποχείλιση (Underflow): Προκύπτει όταν προσπαθούμε να αφαιρέσουμε ένα στοιχείο από μια κενή στοίβα.

Παραστάσεις Στοίβας

Η στοίβα μπορεί να υλοποιηθεί με δύο κύριους τρόπους:

Με Πίνακα (Array-Based):
Χρησιμοποιείται ένας στατικός μονοδιάστατος πίνακας για την αποθήκευση των στοιχείων. Η κορυφή της στοίβας παρακολουθείται με τον δείκτη top.
Με Συνδεδεμένη Λίστα (Linked List):
Κάθε κόμβος περιέχει ένα στοιχείο και έναν δείκτη στον επόμενο κόμβο. Η κορυφή είναι ο πρώτος κόμβος.

Εφαρμογές Στοίβας

Υλοποίηση αναδρομικών αλγορίθμων.
Διαχείριση ιστορικού ενεργειών (π.χ. undo/redo σε επεξεργαστές κειμένου).
Αλγόριθμοι αναζήτησης (π.χ. Depth-First Search).
Έλεγχος ισορροπίας παρενθέσεων.

Διάγραμμα Στοίβας

Παραστάσεις μιας στοίβας με τρία στοιχεία: 7 (κορυφή), 5, 3 (βάση).

Παραδείγματα στη ΓΛΩΣΣΑ

Αλγόριθμοι Στοίβας στη ΓΛΩΣΣΑ

Παρακάτω παρουσιάζονται οι αλγόριθμοι για τις βασικές λειτουργίες μιας στοίβας χρησιμοποιώντας την ψευδογλώσσα ΓΛΩΣΣΑ.

Αλγόριθμος Ωθήση

Αλγόριθμος Ωθήση
  Δεδομένα // stack, top, size, item
    αν top < size τότε
      top ← top + 1
      stack[top] ← item
      overflow ← ψευδής
    αλλιώς
      overflow ← αληθής
    τέλος_αν
  Αποτελέσματα // top, overflow, stack
Τέλος Ωθήση

Αλγόριθμος Απώθηση

Αλγόριθμος Απώθηση
  Δεδομένα // stack, top, underflow
    αν top >= 1 τότε
      underflow ← ψευδής
      top ← top - 1
    αλλιώς
      underflow ← αληθής
    τέλος_αν
  Αποτελέσματα // top, underflow, stack
Τέλος Απώθηση

Πρόγραμμα Παράδειγμα_Στοίβας

ΠΡΟΓΡΑΜΜΑ Παράδειγμα_Στοίβας
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Στοίβα[5], Κορυφή, Επιλογή, Στοιχείο
ΑΡΧΗ
  Κορυφή ← 0

  ΓΡΑΨΕ '1: Ώθηση (Push), 2: Απώθηση (Pop), 3: Έξοδος'
  ΔΙΑΒΑΣΕ Επιλογή

  ΟΣΟ Επιλογή ≠ 3 ΕΠΑΝΑΛΑΒΕ
    ΑΝ Επιλογή = 1 ΤΟΤΕ
      ! --- ΚΩΔΙΚΑΣ ΩΘΗΣΗΣ (PUSH) ---
      ΑΝ Κορυφή < 5 ΤΟΤΕ
        ΓΡΑΨΕ 'Δώσε στοιχείο για ώθηση:'
        ΔΙΑΒΑΣΕ Στοιχείο
        Κορυφή ← Κορυφή + 1
        Στοίβα[Κορυφή] ← Στοιχείο
        ΓΡΑΨΕ 'Το στοιχείο ', Στοιχείο, ' εισήχθη επιτυχώς.'
      ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Αδυναμία εισαγωγής: Υπερχείλιση (Η στοίβα είναι γεμάτη)!'
      ΤΕΛΟΣ_ΑΝ

    ΑΛΛΙΩΣ_ΑΝ Επιλογή = 2 ΤΟΤΕ
      ! --- ΚΩΔΙΚΑΣ ΑΠΩΘΗΣΗΣ (POP) ---
      ΑΝ Κορυφή > 0 ΤΟΤΕ
        Στοιχείο ← Στοίβα[Κορυφή]
        Κορυφή ← Κορυφή - 1
        ΓΡΑΨΕ 'Εξήχθη το στοιχείο: ', Στοιχείο
      ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Αδυναμία εξαγωγής: Υποχείλιση (Η στοίβα είναι άδεια)!'
      ΤΕΛΟΣ_ΑΝ
      
    ΑΛΛΙΩΣ
      ΓΡΑΨΕ 'Λανθασμένη επιλογή. Ξαναπροσπάθησε.'
    ΤΕΛΟΣ_ΑΝ

    ΓΡΑΨΕ '1: Ώθηση (Push), 2: Απώθηση (Pop), 3: Έξοδος'
    ΔΙΑΒΑΣΕ Επιλογή
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Ασκήσεις στη ΓΛΩΣΣΑ

Άσκηση 1: Γράψτε κώδικα στη ΓΛΩΣΣΑ για να δημιουργήσετε μια στοίβα, να προσθέσετε τα στοιχεία 5, 10, 15 και να εκτυπώσετε το τελευταίο στοιχείο.

Άσκηση 2: Γράψτε κώδικα στη ΓΛΩΣΣΑ για να ελέγξετε αν μια στοίβα είναι κενή μετά την αφαίρεση όλων των στοιχείων.

Άσκηση 3: Ποιο είναι το αποτέλεσμα της ακόλουθης σειράς ενεργειών σε μια στοίβα στη ΓΛΩΣΣΑ;

ΔΗΜΙΟΥΡΓΙΑ ΣΤΟΙΒΑΣ Σ
ΩΘΗΣΕ ΣΤΟ 1
ΩΘΗΣΕ ΣΤΟ 2
ΩΘΗΣΕ ΣΤΟ 3
ΑΠΟΘΗΣΕ ΑΠΟ ΣΤΟΙΒΑ Σ ΣΤΟ κορυφή
ΩΘΗΣΕ ΣΤΟ 4
ΑΠΟΘΗΣΕ ΑΠΟ ΣΤΟΙΒΑ Σ ΣΤΟ κορυφή

Ποιο στοιχείο θα αφαιρεθεί στο επόμενο ΑΠΟΘΗΣΕ ΑΠΟ ΣΤΟΙΒΑ;

Άσκηση 4: Ένα οχηματαγωγό πλοίο, χωρητικότητας 250 αυτοκινήτων, εκτελεί το δρομολόγιο Πειραιάς – Αίγινα. Λόγω της κατασκευής του πλοίου (διαθέτει μόνο μία είσοδο-έξοδο), τα οχήματα που επιβιβάζονται πρώτα είναι αυτά που θα αποβιβαστούν τελευταία (λειτουργία Στοίβας).

Να αναπτύξετε πρόγραμμα σε ΓΛΩΣΣΑ το οποίο:

Θα αρχικοποιεί τη στοίβα των οχημάτων.
Θα εμφανίζει ένα μενού με τις εξής επιλογές:
1. Επιβίβαση οχήματος (Ώθηση)
2. Αποβίβαση όλων των οχημάτων (Μαζική Απώθηση κατά την άφιξη)
3. Έξοδος από το πρόγραμμα
Στην Επιβίβαση (1), θα ελέγχει αν το πλοίο είναι γεμάτο. Αν δεν είναι, θα διαβάζει τον αριθμό κυκλοφορίας του οχήματος και θα το τοποθετεί στη στοίβα. Διαφορετικά, θα εμφανίζει μήνυμα "Το πλοίο είναι γεμάτο".
Στην Αποβίβαση (2), θα ελέγχει αν υπάρχουν οχήματα. Αν υπάρχουν, θα τα αποβιβάζει ένα-ένα με τη σειρά της στοίβας (LIFO) εμφανίζοντας την πινακίδα τους, μέχρι το πλοίο να αδειάσει τελείως. Αν είναι ήδη άδειο, θα εμφανίζει κατάλληλο μήνυμα.

Υπόδειξη Λύσης:

Δημιουργήστε έναν μονοδιάστατο πίνακα Οχήματα[250] για την αποθήκευση των πινακίδων των οχημάτων.
Χρησιμοποιήστε έναν δείκτη Κορυφή για να παρακολουθείτε την κορυφή της στοίβας.
Για την επιβίβαση (Ώθηση), ελέγξτε αν Κορυφή < 250. Αν ναι, διαβάστε την πινακίδα και αυξήστε τον δείκτη Κορυφή.
Για την αποβίβαση (Απώθηση), ελέγξτε αν Κορυφή > 0. Αν ναι, εμφανίστε την πινακίδα του οχήματος στην κορυφή και μειώστε τον δείκτη Κορυφή.
Χρησιμοποιήστε μια βρόγχο ΟΣΟ για να συνεχίζετε την επανάληψη μέχρι ο χρήστης να επιλέξει Έξοδος.

Animation: Λειτουργίες Στοίβας

Παρακολουθήστε πώς λειτουργούν οι βασικές λειτουργίες μιας στοίβας (Ωθήση και Απώθηση) με οπτικοποίηση.

Δομή Δεδομένων: Στοίβα (Stack)