Εκπαίδευση στη Δομή Δεδομένων Ουρά

Θεωρία για την Ουρά

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

Υλοποίηση Ουράς

Η υλοποίηση της ουράς γίνεται με μονοδιάστατο πίνακα. Η αρχή και το τέλος της ουράς παρακολουθούνται με τους δείκτες front και rear.

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

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

Σφάλματα στην Ουρά

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

Παραστάσεις Ουράς

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

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

Εφαρμογές Ουράς

Διαχείριση ουράς αναμονής (π.χ. σε τυπογραφεία, εκτυπωτές).
Διαχείριση εργασιών σε λειτουργικά συστήματα.
Αλγόριθμοι αναζήτησης (π.χ. Breadth-First Search).
Διαχείριση πελατών σε σύστημα εξυπηρέτησης.

Διάγραμμα Ουράς

Παραστάσεις μιας ουράς με τρία στοιχεία: 3 (αρχή), 5, 7 (τέλος).

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

Αλγόριθμοι Ουράς στη ΓΛΩΣΣΑ

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

Αλγόριθμος Εισαγωγή (Enqueue)

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

Αλγόριθμος Αφαίρεση (Dequeue)

Αλγόριθμος Αφαίρεση
  Δεδομένα // queue, front, rear, underflow
    αν front <= rear τότε
      underflow ← ψευδής
      item ← queue[front]
      front ← front + 1
    αλλιώς
      underflow ← αληθής
    τέλος_αν
  Αποτελέσματα // front, rear, underflow, queue, item
Τέλος Αφαίρεση

Πρόγραμμα Παράδειγμα_Ουράς

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

  ΓΡΑΨΕ '1: Εισαγωγή (Enqueue), 2: Αφαίρεση (Dequeue), 3: Έξοδος'
  ΔΙΑΒΑΣΕ Επιλογή

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

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

    ΓΡΑΨΕ '1: Εισαγωγή (Enqueue), 2: Αφαίρεση (Dequeue), 3: Έξοδος'
    ΔΙΑΒΑΣΕ Επιλογή
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

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

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

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

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

ΔΗΜΙΟΥΡΓΙΑ ΟΥΡΑΣ Ο
ΕΙΣΑΓΩΓΗ 1
ΕΙΣΑΓΩΓΗ 2
ΕΙΣΑΓΩΓΗ 3
ΑΦΑΙΡΕΣΗ ΣΤΟΙΧΕΙΟΥ
ΕΙΣΑΓΩΓΗ 4
ΑΦΑΙΡΕΣΗ ΣΤΟΙΧΕΙΟΥ

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

Άσκηση 4: Ένα σύστημα εξυπηρέτησης πελατών σε μια τράπεζα λειτουργεί με βάση την αρχή FIFO. Κάθε πελάτης που φτάνει λαμβάνει έναν αριθμό προτεραιότητας και εξυπηρετείται με τη σειρά άφιξής του.

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

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

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

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

Animation: Λειτουργίες Ουράς

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

Δομή Δεδομένων: Ουρά (Queue)