Lettere in coda

Nel programma riportato in calce trovate l'implementazione di alcune funzioni che realizzano, tramite l'uso di liste concatenate, una struttura dati coda.

Scrivete una funzione extract che, avendo come argomento una coda, ne stampi ed estragga tutti gli elementi (alla fine dell'esecuzione, la coda argomento della funzione deve essere vuota).

Completando il main, scrivete un programma che:

NB: non basta che il programma produca l'output corretto, deve anche definire ed usare come specificato la struttura dati coda.

Se lo ritenete utile, potete scrivere funzioni aggiuntive.

Esempio

Eseguendo

./soluzione C

avendo nel flusso di ingresso le lettere:

bAfrNmfhCKlRUPNiwCIs

il programma emette sul flusso di uscita:

bfrNmfhClRPNCs

Esempio

Eseguendo

./soluzione S

avendo nel flusso di ingresso le lettere:

czuZtTzkwJSCVtSxZYktTlKCPZzNhicbTPiviIryQ

il programma emette sul flusso di uscita:

kwJxYkKy

Programma da completare

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


struct element {  // definizione di un elemento della lista
  char ch;
  struct element *next;    // prossimo elemento
};

typedef struct queue {
  struct element *head;
  struct element *tail;
  int count;
} *Queue;


Queue init();
void enqueue(char ch, Queue q);
char dequeue(Queue q); // assume che la coda non sia vuota

// inserite qui la funzione extract e eventuali altre funzioni aggiuntive
...


int main( ... ){
  Queue q, v, c, s;

  ...

  // lettura delle lettere e inserimento nella coda q
  ...

  // estrazione dalla coda e distribuzione delle lettere nelle code v,c,s
  ...

  // stampa della coda opportuna
  switch( ... ) {
    case 'V': extract(v);
      break;
    case 'C': extract(c);
      break;
    case 'S': extract(s);
  }

	...

  return 0;
}



Queue init(){
  Queue q = malloc(sizeof(struct queue));
  q->head = NULL;
  q->count = 0;
  return q;
}

void enqueue(char ch, Queue q){
  struct element *new = malloc(sizeof(struct element));
  new->ch = ch;
  new->next = NULL;
  if (q->head == NULL)
    q->head = new; // la coda era vuota
  else {
    q->tail->next = new; // attacco in coda
  }
  q->tail = new;
  q->count++;
}

// assumo che la coda non sia vuota
char dequeue(Queue q){
  char ch;
  struct element *testa = q->head;
  ch = testa->ch;
  q->head = q->head->next;
  free(testa);
  q->count--;
  return ch;
}