Coda di interi

Implementate una struttura dati che manipola numeri interi con il paradigma FIFO (First in First Out), usando una lista di interi con due puntatori alla testa e alla coda della lista. In particolare deve essere definito un nuovo tipo queue e devono essere implementate opportunamente due funzioni enqueue e dequeue per l'inserimento in coda e l'estrazione dalla testa.

Potete partire dal programma riportato in fondo alla pagina, che contiene alcune funzioni per manipolare liste di interi.

Scrivete poi un programma che:

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso i numeri:

1 2 3 4 5 6 7 8 0

il programma emette sul flusso di uscita:

1 3 5 7

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso i numeri:

14 2 -7 10 4 30 0

il programma emette sul flusso di uscita:

-7

Programma da completare


#include <stdio.h>
#include <stdlib.h>

struct element {  // definizione di un elemento della lista
  int info;
  struct element *next;    // prossimo elemento
};

typedef struct element  element;

element *insert(int n, element *h);
void printList(element *h);
element *delete(int x, element *h);



typedef ....


... enqueue( ... ){
  ...
}


... dequeue( ... ){
  ...
}


int main(){
  ...
}


/*  Inserisce un nuovo elemento contenente n in testa alla lista  h
    Restituisce la lista ottenuta. */
element *insert(int n, element *h){
  element *new = malloc(sizeof(element));
  new->info = n;
  new->next = h;
  return new;
}


/* Stampa gli elementi della lista   h */
void printList(element *h){
  /* h e' usato  per attraversare la  lista */
  for( ; h!= NULL; h=h->next)
    printf("%d ", h->info);
  putchar('\n');
}


/* Cancella l'elemento  x nella lista h  e restituisce la lista ottenuta */
element *delete(int n, element *h){
  element *tmp, *p;
  if(h->info == n){  // l'elemento da cancellare e' il primo
    tmp = h;
    h = h->next;
    free(tmp);
  }
  else{  // l'elemento da cancellare non  e' il primo
    for(p = h; p->next != NULL && p->next->info != n; p = p->next)
	    ; /* p e' l'elemento che precede x oppure l'ultimo della lista */
    if ( p->next != NULL ) {
        tmp = p->next;
	p->next = p->next->next;
    	free(tmp);
    }
  }
  return h;
}