Coda (informatica)

Rappresentazione di una coda

In informatica, una coda (in inglese queue) è una struttura dati costituita come una raccolta di entità tenute in una sequenza che può essere modificata aggiungendo entità a un estremo e rimuovendole dall'altro estremo della sequenza. Per questo motivo è una struttura di tipo FIFO (first in first out).

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 FIFO.

Questo tipo di struttura dati è molto utilizzata in informatica, ad esempio nella gestione delle operazioni da eseguire da parte di un sistema operativo (scheduler), 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 da un server verso un client. Le proprietà matematico-statistiche delle code sono studiate nella teoria delle code.

Descrizione

Operazione su 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 di un elemento avviene sulla coda della lista (ossia dopo ultimo elemento) per l'operazione enqueue, mentre la rimozione di un elemento avviene sulla testa (il primo elemento) per l'operazione di dequeue. Per realizzare questo comportamento, la lista contiene due puntatori, uno per la testa (head) e uno per la coda (tail). Quando la lista ha un solo elemento testa e coda coincidono.

Un altro tipo di implementazione della struttura dati coda sfrutta un array circolare. L'array circolare viene indicizzato attraverso un indice di inizio e un indice di fine, oppure attraverso un indice di inizio e lo scostamento (offset) della fine rispetto all'inizio, che vengono aggiornati attraverso l'aritmetica modulare per realizzare una struttura circolare nella quale l'ultimo elemento è contiguo al primo.

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;
	}
	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 un array e due indici, uno per la testa e uno per la coda in modo da poter tenere conto del primo e ultimo elemento inserito. Quando un indice raggiunge la fine dell'array esso viene riportato alla posizione [0] in modo da creare una struttura circolare.

//	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;//(si sfrutta il modulo per gestire gli indici in maniera circolare--sdf)
		size++;
	}
	
	public E dequeue()
	{
		if(size==0){
			System.out.println("errore coda vuota");
			return null;
		}
		E tmp = q[head];
		q[head]=null;
		head = (head+1) % n;//(si sfrutta il modulo per gestire gli indici in maniera circolare--sdf)
		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();
	}
}

Voci correlate

• Teoria delle code

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «coda»
• Wikimedia Commons contiene immagini o altri file sulla coda

Collegamenti esterni

• (EN) Eric W. Weisstein, Queue, su MathWorld, Wolfram Research.
• (EN) Denis Howe, queue, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL