Τι ονομάζεται ουρά;
Ουρά (Queue), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με
τέτοιο τρόπο, ώστε τα στοιχεία που τοποθετήθηκαν πρώτα στην ουρά να λαμβάνονται επίσης πρώτα. Η
παραπάνω μέθοδος ονομάζεται Πρώτο Μέσα, Πρώτο Έξω ή FIFO (=First In First Out).
1. Ποιες είναι οι κύριες λειτουργίες σε μια ουρά;
● Η εισαγωγή (enqueue) στοιχείου στο πίσω άκρο της ουράς.
● Η εξαγωγή (dequeue) στοιχείου από το εμπρός άκρο της ουράς.
2. Πως υλοποιείται η ουρά με χρήση μονοδιάστατου πίνακα;
● Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου. Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν.
● Η εισαγωγή ενός νέου στοιχείου γίνεται από το πίσω άκρο της ουράς και η τιμή της μεταβλητής rear αλλάζει ως εξής: rear ← rear+1
Κατά την εισαγωγή, πρώτα αυξάνουμε τον δείκτη rear κατά ένα και μετά εισάγουμε το στοιχείο στον πίνακα. Αυτό υπό την προϋπόθεση ότι υπάρχει χώρος (rear < max).
Aν το στοιχείου που βάζουμε είναι το πρώτο (rear=1) τότε θέτουμε και front ← 1
● Η εξαγωγή ενός στοιχείου γίνεται από το εμπρός άκρο της ουράς και η τιμή της μεταβλητής front αλλάζει
ως εξής: front ← front +1
Κατά την εξαγωγή ενός στοιχείου, αυξάνεται ο δείκτης front κατά ένα (δείχνει στην επόμενη θέση του
πίνακα) χωρίς στην πραγματικότητα να γίνεται καμία παρέμβαση στα περιεχόμενα του πίνακα (χωρίς να
διαγράφεται κάποιο στοιχείο). Αυτό υπό την προϋπόθεση ότι υπάρχει στοιχείο (front <= rear και front >
0).
Όταν γίνεται εξαγωγή του τελευταίου στοιχείου της ουρά (front = rear) οι δείκτες παίρνουν πάλι τις
αρχικές τιμές (0).
ΠΡΟΓΡΑΜΜΑ ΟΥΡΑ
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: A[10]
ΑΚΕΡΑΙΕΣ: f, r, απάντηση, i
ΑΡΧΗ
f <- 0
r <- 0
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώστε 1: εισαγωγή 2: εξαγωγή 9:έξοδος'
ΔΙΑΒΑΣΕ απάντηση
ΕΠΙΛΕΞΕ απάντηση
ΠΕΡΙΠΤΩΣΗ 1
ΑΝ r < 10 ΤΟΤΕ
r <- r + 1
ΓΡΑΨΕ 'Δώστε τιμή για εισαγωγή : '
ΔΙΑΒΑΣΕ A[r]
ΑΝ r = 1 ΤΟΤΕ
f <- 1
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Γεμάτη ουρά'
ΤΕΛΟΣ_ΑΝ
ΠΕΡΙΠΤΩΣΗ 2
ΑΝ f > 0 ΤΟΤΕ
ΓΡΑΨΕ 'Eξαγωγή : ', A[f]
A[f] <- ''
f <- f + 1
ΑΝ f > r ΤΟΤΕ
f <- 0
r <- 0
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Αδεια ουρά'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΙΛΟΓΩΝ
ΜΕΧΡΙΣ_ΟΤΟΥ απάντηση = 9
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ