Γραμμικές Δομές Δεδομένων στη ΓΛΩΣΣΑ

Εισαγωγή στις Γραμμικές Δομές Δεδομένων

Οι γραμμικές δομές δεδομένων είναι δομές στις οποίες τα στοιχεία είναι διατεταγμένα σε μια γραμμική ακολουθία. Κάθε στοιχείο (εκτός από το πρώτο και το τελευταίο) έχει ένα προηγούμενο και ένα επόμενο στοιχείο. Οι βασικότερες γραμμικές δομές δεδομένων είναι:

  • Πίνακας (Array): Στατική δομή με άμεση πρόσβαση σε οποιοδήποτε στοιχείο.
  • Στοίβα (Stack): Δομή που ακολουθεί την αρχή LIFO (Last-In, First-Out).
  • Ουρά (Queue): Δομή που ακολουθεί την αρχή FIFO (First-In, First-Out).
  • Συνδεδεμένη Λίστα (Linked List): Δυναμική δομή με κόμβους που περιέχουν δεδομένα και δείκτες.

Κάθε μια από αυτές τις δομές έχει τα δικά της πλεονεκτήματα και μειονεκτήματα, και χρησιμοποιείται ανάλογα με τις ανάγκες του προβλήματος.

Πίνακας (Array)

Χαρακτηριστικά

  • Στατική δομή: Το μέγεθος του πίνακα δηλώνεται στην αρχή και δεν αλλάζει κατά την εκτέλεση του προγράμματος.
  • Άμεση πρόσβαση: Μπορούμε να έχουμε άμεση πρόσβαση σε οποιοδήποτε στοιχείο μέσω του δείκτη του (π.χ. A[5]).
  • Μνήμη: Τα στοιχεία αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
  • Δήλωση στη ΓΛΩΣΣΑ: ΠΙΝΑΚΑΣ Α[10] (δημιουργεί έναν πίνακα με 10 στοιχεία).

Παραδείγματα Χρήσης

  • Αποθήκευση μιας σειράς αριθμών (π.χ. βαθμοί μαθητών).
  • Αποθήκευση ονομάτων σε μια λίστα.
  • Πίνακες για μαθηματικές πράξεις (π.χ. πολλαπλασιασμός πινάκων).

Πλεονεκτήματα και Μειονεκτήματα

  • Πλεονεκτήματα:
    • Γρήγορη πρόσβαση σε οποιοδήποτε στοιχείο.
    • Απλή υλοποίηση και χρήση.
  • Μειονεκτήματα:
    • Στατικό μέγεθος (δεν μπορεί να αυξηθεί ή να μειωθεί δυναμικά).
    • Δυσκολία στην εισαγωγή/αφαίρεση στοιχείων στη μέση του πίνακα.

Παράδειγμα Κώδικα στη ΓΛΩΣΣΑ

ΠΡΟΓΡΑΜΜΑ Πίνακας_Παραδειγμα
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α[10], i
ΑΡΧΗ
  ! Αρχικοποίηση του πίνακα
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    Α[i] ← i * 2
    ΓΡΑΨΕ 'A[', i, '] = ', Α[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Στοίβα (Stack)

Φιλοσοφία

Η στοίβα ακολουθεί την αρχή LIFO (Last-In, First-Out). Το τελευταίο στοιχείο που εισάγεται είναι το πρώτο που εξέρχεται.

Παράδειγμα: Μια στοίβα από πιάτα ή το οχηματαγωγό πλοίο που είδαμε πριν.

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

  • Ωθήση (Push): Εισαγωγή στοιχείου στην κορυφή (top).
  • Απώθηση (Pop): Εξαγωγή στοιχείου από την κορυφή (top).

Σφάλματα

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

Παράδειγμα Κώδικα στη ΓΛΩΣΣΑ

ΠΡΟΓΡΑΜΜΑ Στοίβα_Παραδειγμα
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Στοίβα[10], Κορυφή, Επιλογή, Στοιχείο
ΑΡΧΗ
  Κορυφή ← 0
  ΓΡΑΨΕ '1: Ωθήση, 2: Απώθηση, 3: Έξοδος'
  ΔΙΑΒΑΣΕ Επιλογή
  ΟΣΟ Επιλογή ≠ 3 ΕΠΑΝΑΛΑΒΕ
    ΑΝ Επιλογή = 1 ΤΟΤΕ
      ΑΝ Κορυφή < 10 ΤΟΤΕ
        ΓΡΑΨΕ 'Δώσε στοιχείο: '
        ΔΙΑΒΑΣΕ Στοιχείο
        Κορυφή ← Κορυφή + 1
        Στοίβα[Κορυφή] ← Στοιχείο
      ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Υπερχείλιση!'
      ΤΕΛΟΣ_ΑΝ
    ΑΛΛΙΩΣ_ΑΝ Επιλογή = 2 ΤΟΤΕ
      ΑΝ Κορυφή > 0 ΤΟΤΕ
        ΓΡΑΨΕ 'Εξήχθη: ', Στοίβα[Κορυφή]
        Κορυφή ← Κορυφή - 1
      ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Υποχείλιση!'
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
    ΓΡΑΨΕ '1: Ωθήση, 2: Απώθηση, 3: Έξοδος'
    ΔΙΑΒΑΣΕ Επιλογή
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Ουρά (Queue)

Φιλοσοφία

Η ουρά ακολουθεί την αρχή FIFO (First-In, First-Out). Το πρώτο στοιχείο που εισάγεται είναι το πρώτο που εξέρχεται.

Παράδειγμα: Η ουρά σε ένα ταμείο σούπερ μάρκετ.

Δείκτες

Η ουρά χρησιμοποιεί δύο δείκτες:

  • Rear (πίσω): Για την εισαγωγή νέων στοιχείων.
  • Front (εμπρός): Για την εξαγωγή στοιχείων.

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

  • Εισαγωγή (Enqueue): Προσθήκη στοιχείου στο τέλος της ουράς.
  • Αφαίρεση (Dequeue): Αφαίρεση στοιχείου από την αρχή της ουράς.

Σφάλματα

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

Παράδειγμα Κώδικα στη ΓΛΩΣΣΑ

ΠΡΟΓΡΑΜΜΑ Ουρά_Παραδειγμα
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ουρά[10], Front, Rear, Επιλογή, Στοιχείο
ΑΡΧΗ
  Front ← 1
  Rear ← 0
  ΓΡΑΨΕ '1: Εισαγωγή, 2: Αφαίρεση, 3: Έξοδος'
  ΔΙΑΒΑΣΕ Επιλογή
  ΟΣΟ Επιλογή ≠ 3 ΕΠΑΝΑΛΑΒΕ
    ΑΝ Επιλογή = 1 ΤΟΤΕ
      ΑΝ Rear < 10 ΤΟΤΕ
        ΓΡΑΨΕ 'Δώσε στοιχείο: '
        ΔΙΑΒΑΣΕ Στοιχείο
        Rear ← Rear + 1
        Ουρά[Rear] ← Στοιχείο
      ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Υπερχείλιση!'
      ΤΕΛΟΣ_ΑΝ
    ΑΛΛΙΩΣ_ΑΝ Επιλογή = 2 ΤΟΤΕ
      ΑΝ Front <= Rear ΤΟΤΕ
        ΓΡΑΨΕ 'Εξήχθη: ', Ουρά[Front]
        Front ← Front + 1
      ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Υποχείλιση!'
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
    ΓΡΑΨΕ '1: Εισαγωγή, 2: Αφαίρεση, 3: Έξοδος'
    ΔΙΑΒΑΣΕ Επιλογή
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Συνδεδεμένη Λίστα (Linked List)

Χαρακτηριστικά

  • Δυναμική δομή: Το μέγεθος της συνδεδεμένης λίστας αυξομειώνεται κατά την εκτέλεση του προγράμματος.
  • Δομή: Κάθε στοιχείο ονομάζεται κόμβος και αποτελείται από δύο μέρη:
    • Τα δεδομένα του.
    • Έναν δείκτη (δείκτης επόμενου) που "δείχνει" πού βρίσκεται ο επόμενος κόμβος στη μνήμη.
  • Μνήμη: Τα στοιχεία δεν βρίσκονται σε συνεχόμενες θέσεις, αλλά διάσπαρτα στη μνήμη.

Παραδείγματα Χρήσης

  • Δυναμική διαχείριση μνήμης (π.χ. λίστες με μεταβλητό μέγεθος).
  • Υλοποίηση άλλων δομών δεδομένων (π.χ. στοίβα, ουρά).
  • Αποθήκευση μεγάλων δεδομένων όπου το μέγεθος δεν είναι γνωστό εκ των προτέρων.

Πλεονεκτήματα και Μειονεκτήματα

  • Πλεονεκτήματα:
    • Δυναμικό μέγεθος (μπορεί να αυξηθεί ή να μειωθεί κατά την εκτέλεση).
    • Εύκολη εισαγωγή/αφαίρεση στοιχείων στη μέση της λίστας.
  • Μειονεκτήματα:
    • Δεν υπάρχει άμεση πρόσβαση στα στοιχεία (πρέπει να διασχίσουμε τη λίστα).
    • Απαίτηση για επιπλέον μνήμη για τους δείκτες.

Σύγκριση Γραμμικών Δομών Δεδομένων

Παρακάτω παρουσιάζεται μια σύγκριση των βασικών γραμμικών δομών δεδομένων:

Χαρακτηριστικό Πίνακας (Array) Στοίβα (Stack) Ουρά (Queue) Συνδεδεμένη Λίστα (Linked List)
Δυναμικό Μέγεθος ❌ Όχι ❌ Όχι ❌ Όχι ✅ Ναι
Πρόσβαση ✅ Άμεση (O(1)) ❌ Μόνο στην κορυφή ❌ Μόνο στην αρχή και το τέλος ❌ Διαδοχική (O(n))
Εισαγωγή/Αφαίρεση στην Αρχή ❌ Δυσκολία (O(n)) ❌ Όχι εφαρμόσιμο ✅ Ναι (Dequeue) ✅ Ναι (O(1))
Εισαγωγή/Αφαίρεση στο Τέλος ✅ Ναι (O(1)) ✅ Ναι (Push/Pop) ✅ Ναι (Enqueue) ✅ Ναι (O(1))
Μνήμη ✅ Συνεχόμενη ✅ Συνεχόμενη ✅ Συνεχόμενη ❌ Διάσπαρτη
Χρήσεις Αποθήκευση στατικών δεδομένων Αναδρομή, Undo/Redo Ουρές αναμονής, BFS Δυναμικές λίστες, DFS

Ποια Δομή να Επιλέξω;

  • Πίνακας: Όταν χρειάζεσαι γρήγορη πρόσβαση σε οποιοδήποτε στοιχείο και το μέγεθος είναι σταθερό.
  • Στοίβα: Όταν χρειάζεσαι να ακολουθήσεις την αρχή LIFO (π.χ. αναδρομή, undo/redo).
  • Ουρά: Όταν χρειάζεσαι να ακολουθήσεις την αρχή FIFO (π.χ. ουρές αναμονής).
  • Συνδεδεμένη Λίστα: Όταν χρειάζεσαι δυναμικό μέγεθος και συχνές εισαγωγές/αφαιρέσεις στη μέση.