Ουρές και δείκτες

Ορισμός

• Η ουρά (queue) είναι μια γραμμική διάταξη στοιχείων στην οποία κάθε πρόσθεση στοιχείων γίνεται στο τέλος της και κάθε αφαίρεση στοιχείων γίνεται από την αρχή της.
• Η μέθοδος φύλαξης που υλοποιεί η ουρά λέγεται FIFO (First In First Out).
• Συνδιασμός ουράς και στοίβας (επιτρέπει την εισαγωγή και εξαγωγή και από τα δύο άκρα) καλείται ουρά με δύο άκρα (dequeue (double ended queue)).

Υλοποίηση στη μνήμη

• Τα στοιχεία φυλάσσονται σε διαδοχικές θέσεις.
• Ένας δείκτης ή καταχωρητής δείχνει την αρχή της ουράς.
• Ένας δείκτης ή καταχωρητής δείχνει το τέλος της ουράς.
• Το μέγεθος της ουράς ορίζεται με σύμβαση.
• Μπορούμε να ορίσουμε ότι η ουρά είναι άδεια όταν η αρχή είναι ίδια με το τέλος.
• Όταν η αρχή ή το τέλος φτάσουν το μέγεθος της ουράς πρέπει να επιστρέψουν στην αρχή της (κυκλική ουρά).

Υλοποίηση σε Pascal

• Η ουρά υλοποιείται με τη μορφή πίνακα.
• Δύο ξεχωριστές μεταβλητές δείχνουν την αρχή και το τέλος της ουράς.
• Απαραίτητοι οι έλεγχοι για υπερχείλιση και υποχείλιση.

Αφηρημένος τύπος

{ Αρχικοποιείται η ουρά }

procedure queueInitialize;

{ Το στοιχείο i εισάγεται στο τέλος της ουράς }

procedure queuePut(i : integer);

{ Το στοιχείο από την αρχή της ουράς αφαιρείται και επιστρέφεται }

function queueGet : integer;

{ Επιστρέφεται αληθές αν η ουρά είναι κενή }

function queueIsEmpty : boolean;

Εφαρμογές

• Υλοποίηση ουράς προτεραιότητας
• Επίσκεψη κλάδων δέντρου κατά βάθος
• Αναγνώριση συμβολοσειρών
• Εύρεση στοιχείων σε γράφο με ανίχνευση κατά πλάτος

Δείκτες

Ορισμός

var
	p, q : ^integer;

Αρχικοποίηση

• με τη χρήση της διαδικασίας new, ή
• με την εκχώρηση στο δείκτη της τιμής ενός άλλου δείκτη.

	new(p);
	q = p

Χρήση

	p^ := 3;
	writeln(p^)

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 56-62, 72-75 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 56–60. Addison-Wesley, 1983.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 235–241. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 30–31, 300–301, 431, 457. Addison-Wesley, 1990.

Ασκήσεις

Άσκηση ADS03

1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της ουράς ακεραίων σύμφωνα με τις παρακάτω συναρτήσεις:

   { Αρχικοποιείται η ουρά }

   procedure queueInitialize;

   { Το στοιχείο i εισάγεται στο τέλος της ουράς }

   procedure queuePut(i : integer);

   { Το στοιχείο από την αρχή της ουράς αφαιρείται και επιστρέφεται }

   function queueGet : integer;

   { Επιστρέφεται αληθές αν η ουρά είναι κενή }

   function queueIsEmpty : boolean;

2. Με βάση τον αφηρημένο αυτό τύπο και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
   1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
   2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
   Παράδειγμα:

   I
   1
   I
   2
   I
   3
   O
   1
   I
   4
   O
   2
   ...
   

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:30 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».