Coda (informatica)

Strutture dati lineari

• Array
• Deque
• Heap
• Lista concatenata
• Coda
• Stack

In informatica per coda si intende una struttura dati di tipo FIFO, First In First Out (il primo in ingresso è il primo ad uscire).

Un esempio pratico sono le code che si fanno per ottenere un servizio, come pagare al supermercato o farsi tagliare i capelli dal parrucchiere: idealmente si viene serviti nello stesso ordine con cui ci si è presentati.

Questo è esattamente il funzionamento di una coda.

Questo tipo di struttura dati è molto utilizzata in informatica, ad esempio nella gestione delle operazioni da eseguire da parte di un sistema operativo, ed è fondamentale nelle telecomunicazioni, in particolare nelle reti a commutazione di pacchetto, dove descrive la gestione dei pacchetti in attesa di essere trasmessi su un collegamento.

Le proprietà statistiche delle code sono studiate nella teoria delle code.

Operazione su una coda

Rappresentazione di una coda

Accodamento di un elemento

Detta anche operazione di enqueue, serve a mettere un elemento in coda.

Estrazione di un elemento

Detta anche operazione di dequeue, serve a rimuovere un elemento dalla testa della coda.

Tipi di implementazione

Per implementare una coda viene utilizzato normalmente una lista concatenata.

Ogni elemento della lista è un elemento della coda e dato che la coda è una struttura dati FIFO, First In First Out, l'inserimento in lista potrebbe tranquillamente avvenire in tail(coda) per l'operazione enqueue, e la rimozione dell'elemento potrebbe avvenire in head(testa) per l'operazione di dequeue. La lista infatti contiene due puntatori uno per la testa(il primo elemento della lista)e uno per la coda(ultimo elemento della lista). Quando la lista ha un solo elemento testa e coda coincidono. Un altro tipo di implementazione per una struttura dati coda è l'implementazione mediante array circolare(circolare grazie all'utilizzo della aritmetica modulare).

Implementazione coda in java tramite lista concatenata

Ecco una semplice implementazione della coda con una lista concatenata:

class Node<E>{//classe nodo generico della lista
        private E element;
        private Node next;
 
        public Node(E element){
                this(element, null);
        }
 
        public Node(E element, Node next){
                this.element=element;
                this.next=next;
        }
 
        public void setNext(Node next){
                this.next= next;
        }
 
        public E getElement(){
                return element;
        }
 
        public Node getNext(){
                return next;
        }
 
        public String toString(){
                return (String) element;
        }
}
class LinkedList<E>{
        private Node head, tail;//nodi sentinella una per la testa e l'altro per la coda
        protected int size;
 
        public LinkedList(){//costruttore
                head=tail=null;
                size=0;
        }
        public void addToTail(E element){// aggiungo in coda
                Node node = new Node(element);
                if(tail==null)
                {
                        head=tail=node;
                }
                else
                {
                        tail.setNext(node);
                        tail=node;
                }
                size++;
        }
        public E removeToHead(){
                E element=null;
                if (size==0)System.out.println("errore coda vuota"); //stampo errore;
                else{
                        element=(E)head.getElement();
                        head=head.getNext();
                        size--;
                        return element;
                }
                return element;
        }
        public String toString(){
                StringBuilder str= new StringBuilder();
                if(size!=0){
                        Node tmp= head;
                        while(tmp!=null){
                                str.append(tmp.toString());
                                tmp=tmp.getNext();
                        }
                }
                return str.toString();
        }
}
public class Queue<E>{
        private LinkedList<E> lista;
 
        public Queue(){
                lista= new LinkedList<E>();
        }
        public int size(){
                return lista.size;
        }
        public void enqueue(E element){
                lista.addToTail(element);
        }
        public E dequeue(){
                return lista.removeToHead();
        }
        public String toString(){
                return lista.toString();
        }
}

Implementazione Coda in java con array circolare

Ecco una semplice implementazione in java di una coda con array circolare. Si utilizza una array e due indici uno per la testa e uno per la coda e si aumentano con l'operatore modulo così l'array è come se fosse una cerchio di elementi.

//      HEAD <--O  <--O  <--O  <--O  <--O TAIL
//      Enqueue (Inserimento in coda)
//      Dequeue (Estrazione dalla testa)
//      head = tail --> Coda vuota
public class ArrayQueue<E>
{
        private int head, tail;
        private int size, n;
        private static final int CAPACITY = 1000;
        private E[] q;
        public ArrayQueue(){
                this(CAPACITY);
        }
 
        public ArrayQueue(int capacity)
        {
                head=tail=0;
                size=0;
                n=capacity;
                q = (E[]) new Object[capacity];
        }
 
        public void enqueue(E element)
        {
                if(size==n){
                        System.out.println("errore coda piena");
                        return;
                }
                q[tail] = element;
                tail = (tail+1) % n;//Permette di gestire l'array in modo circolare
                size++;
        }
 
        public E dequeue()
        {
                if(size==0){
                        System.out.println("errore coda piena");
                        return null;
                }
                E tmp = q[head];
                q[head]=null;
                head = (head+1) % n;//Permette di gestire l'array in modo circolare
                size--;
                return tmp;
        }
 
        public boolean isEmpty()
        {
                return size==0;
        }
        public String toString()
        {
                StringBuilder str = new StringBuilder("");
                int cont=0;
                for(E element : q)
                {
                        if(element != null)
                        {
                                str.append(element); cont++;
                                        if(cont<size)
                                                str.append("\n");
                        }
                }
 
                return str.toString();
        }
}

Altri progetti

• Commons

• Commons contiene file multimediali su Coda (informatica)

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica