Ουρές

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

Ορισμός

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

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

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

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

Υλοποίηση με πίνακα

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

Παράδειγμα 1

struct s_int_queue {
	int values[20];			/* Array of values */
	int head;			/* Head of queue (values[head]) */
	int tail;			/* Tail of queue (values[tail]) */
};

Παράδειγμα 2

struct s_int_queue {
	int *values;			/* Allocated array of values */
	int values_size;		/* Number of values allocated */
	int head;			/* Head of queue (values[head]) */
	int tail;			/* Tail of queue (values[tail]) */
};

Παράδειγμα 3

struct s_int_queue {
	int *values_start;		/* Start of allocated array of values */
	int *values_end;		/* End of allocated array of values */
	int *head;			/* Head of queue  */
	int *tail;			/* Tail of queue  */
};

Υλοποίηση με συνδεδεμένη λίστα

Η ουρά μπορεί να υλοποιηθεί με τη μιας συνδεδεμένης λίστας
Δύο ξεχωριστές μεταβλητές δείχνουν τα στοιχεία της λίστας που αποτελούν την αρχή και το τέλος της ουράς. Η αρχή της ουράς (queue head) (το σημείο από το οποίο αφαιρούνται τα στοιχεία) είναι η αρχή της λίστας, το τέλος της ουράς (queue tail) είναι το τέλος της λίστας.
Οι δείκτες στην αρχή το τέλος της λίστας μπορούν να ομαδοποιηθούν σε μια εγγραφή.

Παράδειγμα

struct s_int_list {
	int val;
	struct s_int_list *next;
};

struct s_int_queue {
	struct s_int_list *head;
	struct s_int_list *tail;
};

/* Add an element to the queue */
void
int_queue_put(struct s_int_queue *q, int v)
{
	struct s_int_list *p;

	p = (struct s_int_list *)malloc(sizeof(struct s_int_list));
	p->next = NULL;
	p->val = v;
	if (q->tail != NULL)
		q->tail->next = p;	/* Add element to queue tail */
	else
		q->head = p;		/* Special case for empty queue */
	q->tail = p;
}

/* Remove and return an element from a non-empty queue */
int
int_queue_get(struct s_int_queue *q)
{
	int v;
	struct s_int_list *tmp;

	assert(q->head != NULL);

	v = q->head->val;
	if (q->head->next == NULL)
		q->tail = NULL;		/* Special case for empty queue */
	tmp = q->head->next;
	free(q->head);
	q->head = tmp;
	return (v);
}

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

Ορισμός του τύπου της ουράς λίστας ακεραίων: typedef struct s_int_queue *int_queue;
Επιστρέφει μια άδεια ουρά: int_queue new_int_queue(void);
Το στοιχείο i εισάγεται στο τέλος της ουράς: void put_int_queue(int_queue q, int i);
Το στοιχείο από την αρχή της μη κενής ουράς αφαιρείται και επιστρέφεται: int get_int_queue(int_queue q);
Επιστρέφεται αληθές αν η ουρά είναι κενή: int isempty_int_queue(int_queue q);
Διαγράφει την ουρά: void delete_int_queue(int_queue q);

Εφαρμογές

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

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

Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 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.

Ασκήσεις

Άσκηση 4

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

Επιστρέφει μια άδεια ουρά
int_queue new_int_queue(void);
Το στοιχείο i εισάγεται στο τέλος της ουράς
void put_int_queue(int_queue q, int i);
Το στοιχείο από την αρχή της μη κενής ουράς αφαιρείται και επιστρέφεται
int get_int_queue(int_queue q);
Επιστρέφεται αληθές αν η ουρά είναι κενή
int isempty_int_queue(int_queue q);
Με βάση τον αφηρημένο αυτό τύπο και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
Παράδειγμα:
```
I
1
I
2
I
3
O
1
I
4
O
2
...
```

Περιεχόμενα