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

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Ορισμός

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

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

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

{ Αρχικοποιείται η ουρά }
procedure queueInitialize;
{ Το στοιχείο i εισάγεται στο τέλος της ουράς }
procedure queuePut(i : integer);
{ Το στοιχείο από την αρχή της ουράς αφαιρείται και επιστρέφεται }
function queueGet : integer;
{ Επιστρέφεται αληθές αν η ουρά είναι κενή }
function queueIsEmpty : boolean;

Εφαρμογές

Δείκτες

Ορισμός

Ο δείκτης (pointer) είναι ένας τύπος δεδομένων που χρησιμοποιήται για να απεικονίσει απευθείας τη μνήμη του υπολογιστή. Στην Pascal δείκτης σε κάποιο τύπο (λ.χ. Integer) ορίζεται ως εξής:
var
	p, q : ^integer;

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

Πριν χρησιμοποιηθεί ένας δείκτης πρέπει να δείξει σε καθορισμένο χώρο της μνήμης. Αυτό μπορεί να γίνει: Παράδειγμα:
	new(p);
	q = p

Χρήση

Μπορούμε να διαβάσουμε ή να αλλάξουμε τα στοιχεία στη θέση που δείχνει ο δείκτης χρησιμοποιώντας το όνομά του μαζί με το σύμβολο ^:
	p^ := 3;
	writeln(p^)

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

Ασκήσεις

Άσκηση 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
    ...
    
Περισσότερες λεπτομέρειες για τις ασκήσεις