ADT Coda.

Introduzione

La Coda è un caso speciale di lista lineare, in cui le operazioni di inserimento e cancellazione avvengono ai due estremi della lista, la testa(top) e il fondo(bottom). Per questo spesso si indica la pila con il termine LIFO (Forst In First Out). Intuitivamente la coda è un gruppo di persone in attesa ad uno sportello. I nuovi arrivi si accodano mentre le persone vengono servite dalla testa.

Operazioni

• creazione: Crea una coda vuota.
  Ricordando che la pila è un caso particolare di lista lineare.

  
  	typedef Lista Coda;
  	
  	Coda codaCrea( void ) {
  		return listaCrea();
  	}
  
  

• front: restituisce l'elemento in cima alla coda.

  
  	Elemento codaFront( Coda c ) {
  		return listaRetrieve(listaFirst( c ), c);
  	}
  
  

• enqueue: inserisce un nuovo elemento in fondo alla coda.

  
  	Coda codaEnqueue( Elemento e, Coda c ) {
  		return listaInsert(c, e, listaEnd(c) );
  	}
  
  

• dequeue: elimina l'elemento in testa alla coda.

  
  	Coda codaDequeue( Coda c) {
  		return listaDelete(listaFirst( c ), c);
  	}
  
  

• empty: restituisce 1 se coda vuota, 0 altrimenti.

  
  	int codaEmpty( Coda c ) {
  		return listaFirst(c) == listaEnd(c);
  	}
  	
  

Nota: con la realizzazione presentata sopra diventa ininfluente conoscere quale adt lista utilizzare. E' possibile anche utilizzare adt lista ricorsivo, implementando con esso una struttura dati imperativa.

Implementazione della Coda con un vettore circolare.

Tenendo conto che in una coda l'inserimento e l'estrazione avvengono da estremi opposti, possiamo sviluppare la coda con un array, utilizzando come cima della coda la testa dell'array, e come fondo l'altro estremo. Circolare significa che quando si giunge all'ultima posizione dell'array si ricomincia dalla prima.Si considererà piena o vuota la coda quando testa e fondo coincideranno.

Con questa idea si può sviluppare ADT coda nel seguente modo:

La struttura dati è la seguente:

	#define DIM 100
	typedef void* Elemento;
	typedef struct {
		void* ele[DIM];
		int testa, fondo;
	} _coda;
	
	typedef _coda *Coda;

Le due seguenti funzioni sono necessarie la prima per incrementare correttamente l'indice del vettore, la seconda per segnalare un uso scorretto della coda.

	static int piuuno( int i ) {
		return (i + 1) % DIM;
	}

	static fatal(char* x) {
		printf("\n%s\n", x);
		exit(-1);
	}

Le primitive sono:

	Coda codaCrea( void ) {
		Coda x = (Coda)malloc(sizeof( _coda ));
		x->testa =0; x->fondo = 1;
		return x;
	}

	Elemento codaFront( Coda c ) {
		if(codaEmpty(c)) fatal("ERRORE: front - coda vuota ");
		return c->ele[c->testa+1];
	}

	Coda codaEnqueue( Elemento e, Coda c ) {
		if( piuuno(c->fondo) == c->testa ) 
			fatal("ERRORE: enqueue - coda piena ");
		c->ele[c->fondo] = e;
		c->fondo = piuuno(c->fondo);
		return c;
	}

	Coda codaDequeue( Coda c) {
		if(codaEmpty(c)) fatal("ERRORE: dequeue - coda vuota ");
		c->testa = piuuno(c->testa);
		return c;
	}

	int codaEmpty( Coda c ) {
		return piuuno(c->testa) == c->fondo;
	}

Nota:

• al momento della creazione della coda testa e fondo vengono inizializzati rispettivamente a 0 e 1.

• Quando si inserisce un elemento nella coda, prima si incrementa fondo, poi si controlla se coincide con testa. In questo caso si conclude che la coda è piena, anche se rimane lo spazio per un inserimento.

• Similmente quando si estrae un elemento prima si incrementa testa poi si controlla se è uguale a fondo. In questo caso si conclude che la coda è vuota.