.
Η ουρά (queue) στην πληροφορική είναι μια δομή δεδομένων με τη μορφή παρατεταμένης συλλογής. Η βασική λειτουργικότητα είναι η εισαγωγή στοιχείων στην πίσω θέση και η εξαγωγή-διαγραφή στοιχείων από την μπροστινή θέση. Με αυτόν τον τρόπο, η ουρά είναι μια FIFO (First-In-First-Out, Πρώτο-Μέσα-Πρώτο-Έξω) δομή δεδομένων. Σε μια FIFO δομή δεδομένων, το πρώτο στοιχείο που εισάγεται στην ουρά θα είναι το πρώτο που θα αφαιρεθεί-εξυπηρετηθεί.
Οι ουρές χρησιμοποιούνται στον προγραμματισμό υπολογιστών ως δομές δεδομένων. Είναι ο αφηρημένος τύπος δεδομένων μιας ουράς αναμονής στην καθημερινή ζωή (π.χ. μια ουρά εξυπηρέτησης πελατών σε ένα ταμείο). Στις αντικειμενοστραφείς γλώσσες προγραμματισμού υλοποιούνται ως κλάσεις-αντικείμενα. Συνήθεις χρήσεις των ουρών είναι σε κυκλικές προσωρινές μνήμες και στις διασυνδεδεμένες λίστες. Ένα άλλο παράδειγμα χρήσης των ουρών είναι στην λειτουργία της προσωρινής μνήμης (buffer).
Αναπαράσταση της ουράς
Στην ουρά εξυπηρετείται αυτός που μπήκε πρώτος (αρχή της ουράς).
Η ιδιότητα μέσω της οποίας καθορίζεται μια δομή δεδομένων ως ουρά είναι το γεγονός ότι αυτή επιτρέπει πρόσβαση μόνο στην αρχή και στο τέλος της ουράς. Επιπροσθέτως, τα στοιχεία μπορούν να διαγραφούν μόνο από μπροστά και μπορούν να εισαχθούν μόνο πίσω. Έτσι, μια παρομοίωση που ταιριάζει, και συχνά χρησιμοποιείται για να δώσει μια αναπαράσταση της ουράς, είναι οι ουρές των ταμείων πληρωμής. Άλλα παραδείγματα καθημερινών ουρών είναι άνθρωποι που ανεβαίνουν από κυλιόμενες σκάλες, κομμάτια μηχανών τοποθετημένα σε αλυσίδα συναρμολόγησης ή αυτοκίνητα στη σειρά σε ένα βενζινάδικο.
Σε κάθε περίπτωση, το πρόσωπο ή το αντικείμενο στην αρχή της ουράς είναι το πρώτο που θα φύγει, ενώ στο τέλος της ουράς είναι αυτό που θα φύγει τελευταίο. Κάθε φορά που το πρόσωπο ή το αντικείμενο τελειώνει την δουλειά του, εκείνο φεύγει από την ουρά από μπροστά. Αυτό αναπαριστά τη διαδικασία "dequeue" (εξαγωγή). Κάθε φορά που ένα πρόσωπο ή ένα αντικείμενο μπαίνουν στην ουρά αναμονής, εισέρχονται από το τέλος της ουράς και αυτό αναπαριστά τη διαδικασία "enqueue" (εισαγωγή). Η συνάρτηση "size" επιστρέφει το μήκος της γραμμής και η συνάρτηση "empty" θα επέστρεφε true μόνο αν δεν υπήρχε κανείς στη γραμμή.
Υλοποίηση της ουράς
Θεωρητικά, ένα χαρακτηριστικό της ουράς είναι ότι δεν έχει συγκεκριμένο μέγεθος. Ασχέτως από το πόσα στοιχεία περιέχονται ήδη, ένα νέο στοιχείο μπορεί πάντα να εισαχθεί. Στην περίπτωση που η ουρά είναι άδεια δεν μπορεί να γίνει εξαγωγή "dequeue" στοιχείου πριν εισαχθεί κάποιο νέο.
Μια πρακτική υλοποίηση ουράς γίνεται συνήθως με δείκτες στην οποία το όριο μεγέθους περιορίζεται από την διαθέσιμη μνήμη που έχει ο υπολογιστής. Ένας άλλος τρόπος υλοποίησης της ουράς είναι σε μια δομή δεδομένων σε σταθερό μέγεθος εκχωρημένης μνήμης. Ο όρος υπερχείλιση μιας ουράς συμβαίνει κατά την προσπάθεια να εισαχθεί ένα στοιχείο σε μια γεμάτη ουρά, ενώ η υποχείλιση συμβαίνει κατά την προσπάθεια διαγραφής-εξαγωγής ενός στοιχείου από μια άδεια ουρά.
Παραδείγματα ουρών
C
Το παρακάτω παράδειγμα προγραμματισμού στην γλώσσα C χρησιμοποιεί μια δυναμική λίστα και δυναμική εκχώρηση μνήμης:
#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <time.h>
struct queue_node {
struct queue_node *next;
int data;
};
struct queue {
struct queue_node *first;
struct queue_node *last;
};
int enqueue(struct queue *q, const int value) {
struct queue_node *node = (struct queue_node *)malloc(sizeof(struct queue_node));
if (node == NULL) {
errno = ENOMEM;
return 1;
}
node->data = value;
if (q->first == NULL)
q->first = q->last = node;
else {
q->last->next = node;
q->last = node;
}
node->next = NULL;
return 0;
}
int dequeue(struct queue *q, int *value) {
if (!q->first) {
*value = 0;
return 1;
}
*value = q->first->data;
struct queue_node *tmp = q->first;
if (q->first == q->last)
q->first = q->last = NULL;
else
q->first = q->first->next;
free(tmp);
return 0;
}
void init_queue(struct queue *q) {
q->first = q->last = NULL;
}
int queue_empty_p(const struct queue *q) {
return q->first == NULL;
}
int main(void) {
struct queue Q;
init_queue(&Q);
srand(time(NULL));
unsigned int k = 0;
while (k < 100) {
enqueue(&Q, (rand() % 100) + 1); /* Fill with random numbers from 1 to 100 */
++k;
}
k = 1;
while (!queue_empty_p(&Q)) {
int data;
dequeue(&Q, &data);
printf("(%d) %d\n", k, data);
++k;
}
putchar('\n');
system("pause");
return 0;
}
C++
Ουρές δεδομένων μπορούν να δημιουργηθούν με την χρήση του κοντέινερ queue της πρότυπης βιβλιοθήκης C++.
Στο παρακάτω παράδειγμα στην C++ έχουμε την υλοποίηση μιας κυκλικής ουράς χρησιμοποιώντας ένα πίνακα σταθερού μεγέθους και μεταβλητές οι οποίες είναι ορατές παντού (global variables). Δεν χρειάζεται δυναμική εκχώρηση μνήμης η οποία θα επηρέαζε την απόδοση του προγράμματος. Αλλάζοντας την θέση της κεφαλής και της ουράς, δεν χρειάζεται να αλλάξουμε τη θέση των υπόλοιπων μελών μέσα στην μνήμη. Είναι το φυσικό παράδειγμα μιας ουράς ανθρώπων στην οποία ο πρώτος μετακινείται στο τέλος της ουράς χωρίς να χρειάζεται κανείς άλλος στην ουρά να αλλάξει θέση.
#include <iostream>
#include "math.h"
#include <time.h>
#define QMAX 10
using namespace std;
struct Node {
int value;
Node* next;
};
Node* Q[QMAX];
int head=0;
int tail=0;
// επιστρέφει 1 σε περίπτωση επιτυχίας, αλλιώς 0
int enqueue(Node* p) {
if(head!=(tail+1)%QMAX) {
Q[tail]=p;
tail= (tail+1)%QMAX;
return 1;
}
else {
return 0;
}
}
// επιστρέφει 1 σε περίπτωση επιτυχίας, αλλιώς 0
int dequeue(Node** p) {
if(tail == head) {
return 0;
}
*p = Q[head];
Q[head] =NULL;
head++;
head %=QMAX;
return 1;
}
void printqueue() {
int index = head;
int queuelength = (tail+QMAX-head) % QMAX;
for(int index=head; index < head+ queuelength; index ++) {
cout << Q[(index+QMAX) % QMAX]->value << "-";
}
cout << endl;
}
void PrintArray() {
for(int i=0; i< 10; i++) {
if(Q[i]!=NULL) {
cout<< Q[i]->value << "-";
}
else {
cout << "00" << "-";
}
}
cout << endl;
}
// δημιουργία τυχαίου αριθμού από το 1-100
int generateRandNum() {
/* τυχαία αρχικοποίηση ρίζας: */
srand ( time(NULL) );
/* τυχαίος αριθμός σε κάθε μέλος: */
return rand() % 100 + 1;
}
int main(int argc, char* argv[]) {
int i=1;
while(i<=20) {
int rand = generateRandNum();
if(rand<=60) {
Node* n = (Node*)malloc(sizeof(Node));
n->value=generateRandNum();
n->next=NULL;
enqueue(n);
}
else {
Node* p;
if(dequeue(&p)!=0) {
free(p);
}
}
//printqueue();
PrintArray();
i++;
}
return 0;
}
Η έξοδος του παραπάνω προγράμματος είναι της μορφής:
68-00-00-00-00-00-00-00-00-00-
68-1-00-00-00-00-00-00-00-00-
00-1-00-00-00-00-00-00-00-00-
00-1-79-00-00-00-00-00-00-00-
00-1-79-63-00-00-00-00-00-00-
00-00-79-63-00-00-00-00-00-00-
00-00-79-63-46-00-00-00-00-00-
00-00-00-63-46-00-00-00-00-00-
00-00-00-63-46-62-00-00-00-00-
00-00-00-00-46-62-00-00-00-00-
00-00-00-00-00-62-00-00-00-00-
00-00-00-00-00-62-28-00-00-00-
00-00-00-00-00-62-28-92-00-00-
00-00-00-00-00-62-28-92-3-00-
00-00-00-00-00-62-28-92-3-93-
00-00-00-00-00-00-28-92-3-93-
17-00-00-00-00-00-28-92-3-93-
17-96-00-00-00-00-28-92-3-93-
17-96-27-00-00-00-28-92-3-93-
17-96-27-00-00-00-00-92-3-93-
Press any key to continue . . .
Pascal
Βασισμένο σ' ένα παράδειγμα από το βιβλίο R.S. Algorithms (Αλγόριθμοι).
program queue;
procedure queinit; // Αρχικοποιεί την ουρά
begin
New(tail);
New(head);
head^.key := 1;
tail := head;
end;
procedure put(u: integer); // Βάζει τον αριθμό u στην ουρά
var
t: link;
begin
New(t);
t^.key := u;
tail^.next := t;
tail := t;
end;
begin
queinit;
u := 1;
put(u); // Βάζει το 1 στην ουρά
u := 2;
put(u); // Βάζει το 2 στην ουρά
u := 3;
put(u); // Βάζει το 3 στην ουρά
end.
Python
Στην γλώσσα προγραμματισμού Python ένα αντικείμενο list μπορεί να χρησιμοποιηθεί ως ουρά δεδομένων. Η χρήση του list ως ουρά είναι επικριθεί λόγω της πολυπλοκότητας στην λειτουργίας εξαγωγής στοιχείων μέσω της pop λειτουργίας. Το αντικείμενο deque είναι διαθέσιμο και θεωρείται πιο βολικό για λειτουργίες εξαγωγής στοιχείων από οποιαδήποτε πλευρά της λίστας με σταθερή πολυπλοκότητα. Ο παρακάτω κώδικας δείχνει μια απλή υλοποίηση ουράς στην Python:
class Queue:
def __init__(self, items = None):
if items is None:
items = []
self.__queue = items
def isEmpty(self):
return len(self.__queue) == 0
def enqueue(self, obj):
self.__queue.append(obj)
def dequeue(self):
return self.__queue.pop(0)
def peek(self):
return self.__queue[0]
C#
using System;
using System.Collections.Generic;
namespace QueueExample
{
public sealed class Queue<T> : IEnumerable<T>
{
private class Node
{
public Node Previous;
public T Value;
}
Node first;
Node last;
int count = 0;
public int Count { get { return count; } }
public void Enqueue(T item)
{
Node node = new Node { Value = item };
if (first == null)
last = node;
else
first.Previous = node;
first = node;
count++;
}
public T Dequeue()
{
if (count == 0)
throw new InvalidOperationException("Queue is empty.");
Node node = last;
Node previous = last.Previous;
last = previous;
if (previous == null)
first = null;
count--;
return node.Value;
}
#region IEnumerable<T> Members
public IEnumerator<T> GetEnumerator()
{
Node current = last;
for (int i = 0; i < count; i++)
{
current = current.Previous;
yield return current.Value;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
}
}
Java
public class Queue<T> {
private Node<T> nodeHead = null;
private Node<T> nodeEnd = null;
private long size = 0L;
public void enqueue(T x) {
Node<T> newNode = new Node<T>(x, null);
if (nodeHead == null) {
nodeHead = newNode;
} else {
nodeEnd.next = newNode;
}
nodeEnd = newNode;
size++;
}
public T dequeue() throws IllegalStateException {
if (nodeHead == null) {
throw new IllegalStateException();
}
T head = nodeHead.element;
nodeHead = nodeHead.next;
size--;
return head;
}
public long size() {
return size;
}
private class Node<T> {
Node<T> next;
T element;
public Node(T element, Node<T> next) {
this.element = element;
this.next = next;
}
}
}
Javascript
function Queue(){
this.data = [];
this.head = 0;
this.count = 0;
this.size = function(){
return this.count < 0 ? 0 : this.count;
}
this.queue = function(obj){
this.data[this.count++] = obj;
}
this.dequeue = function(){
//Amortizes the shrink frequency of the queue
if(--this.count < this.data.length*0.9){
this.data = this.data.slice(this.head);
this.head = 0;
}
return this.data[this.head++];
}
this.peek = function(){
return this.data[this.head];
}
this.isEmpty = function(){
return this.count <= 0;
}
}
Πηγές
Ντόναλντ Κνουθ. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp.200–204.
William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 8: Queues and Priority Queues, pp.386–390.
Adam Drozdek. Data Structures and Algorithms in C++, Third Edition. Thomson Course Technology, 2005. ISBN 0-534-49182-0. Chapter 4: Stacks and Queues, pp.137–169.
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Queue (data structure) της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
