next up previous contents index
Next: Tabella Up: Alcuni tipi di dati Previous: Stack   Indice   Indice analitico

Coda

La struttura dati coda (eng. ``queue'') è molto simile allo stack, con la fondamentale differenza che si tratta di una struttura dati FIFO (First In First Out): il primo elemento ad essere immesso in una coda è il primo ad essere estratto. Uno schema delle operazioni basilari da effettuare su di una coda è il seguente:
A differenza dello stack, per il quale abbiamo considerato solo l'operazione di lettura dell'ultimo elemento (peek), accederemo in lettura il primo e l'ultimo oggetto. La rappresentazione più semplice di una coda è tramite una lista semplice, con puntatore di coda.

// codal.h
// classe rappresentate una coda
// tramite una lista semplice con puntatore di coda

#ifndef _CODA_L_H_
#define _CODA_L_H_

template<class T>
class CodaL {
public:
  CodaL (bool Possiede = true) {  // costruttore default
    possiede = Possiede;
    primo = ultimo = 0; }
  ~CodaL ();

  T* first () const { return primo->oggetto; }
  T* last () const { return ultimo->oggetto; }
  T* pop ();
  T* push (T* nuovo_oggetto);
  bool vuota () const {
    if (primo == 0) return true;
    return false; }
  bool unitaria () const {
    if (primo == ultimo && primo != 0) return true;
    return false; }
private:
  // il costruttore di copia e la sovrapposizione
  // dell'operatore di assegnamento sono formalmente
  // identici alle medesime funzioni per una lista
  // semplice con puntatore di coda, per cui
  // eviteremo di definirle; esse vengono dichiarate private
  // per evitare un loro uso improprio
  CodaL (const CodaL&);
  const CodaL& operator= (const CodaL&);
  struct elem {
    elem* next;
    T* oggetto;
    elem (T* Oggetto, elem* Next = 0) {
      oggetto = Oggetto;
      next = Next; }
  };
  bool possiede;
  elem* primo;  // puntatore al primo elemento della lista
  elem* ultimo; // puntatore all'ultimo
};

template<class T>
CodaL<T>::~CodaL () {
  if (!vuota()) {
    for (elem* p = primo; primo != 0; p = primo) {
      primo = primo->next;
      if (possiede == true)
        delete p->oggetto;
      delete p;
    }
  }
}

template<class T>
T* CodaL<T>::pop () {
  T* tmp = 0;
  if (vuota()) ;
  else if (unitaria()) {
    if (possiede == true)
      delete primo->oggetto;
    else
      tmp = primo->oggetto;
    delete primo;
    primo = ultimo = 0;
  }
  else {
    elem* p = primo;
    primo = primo->next;
    if (possiede == true)
      delete p->oggetto;
    else
      tmp = p->oggetto;
    delete p;
  }
  return tmp;
}

template<class T>
T* CodaL<T>::push (T* nuovo_oggetto) {
  if (vuota())
    primo = ultimo = new elem(nuovo_oggetto);
  else
    ultimo = ultimo->next = new elem (nuovo_oggetto);
  return nuovo_oggetto;
}

#endif // _CODA_L_H_

Non c'è praticamente nulla di nuovo nella classe su presentata; un semplice esempio sull'utilizzo di essa è il seguente:


// ex11_3_1.cpp

#include "codal.h"
#include <iostream.h>
// librerie per la generazione di numero casuali
#include <stdlib.h>
#include <time.h>

void svuota(CodaL<double>& c) {
  while (!c.vuota())
    cout << *c.pop() << "\n";
}

void main() {
  CodaL<double> c(false);
  for (int i = 0; i < 5; i++)
    c.push(new double(double(rand()) / double(RAND_MAX)));
  *c.first() = -1.0;
  *c.last() = 1.0;
  svuota(c);
}

esempio di output:
-1
0.394383
0.783099
0.79844
1

Si noti che, al contrario dello stack, la coda rispetta l'ordine di inserimento dei dati.

Una interessante implementazione alternativa di una coda potrebbe essere quella di una ``coda limitata'', avente cioè un massimo numero di elementi in essa contenuti. Un esempio di utilizzo di tale struttura potrebbe essere il seguente: supponiamo di avere della memoria a disposizione, fisicamente limitata, possiamo tenere una coda di elementi in memoria, in maniera tale da eliminare automaticamente gli oggetti più ``vecchi'' una volta riempita la coda, supponendo che essi siano obsoleti. A titolo di esempio, implementeremo la classe CodaA come una classe template con due gradi di libertà: il tipo di dato immagazzinato (T) e il massimo numero di elementi contenuti nella coda (MAX).

Siccome MAX viene valutato a tempo di compilazione, possiamo addirittura utilizzare un array non dinamico; si nota comunque che tale metodo potrebbe risultare inefficiente nel caso si intenda costruire un gran numero di code aventi un numero massimo di elementi sempre diverso: in tal caso infatti il compilatore generebbe e compilerebbe una diversa classe per ogni diverso MAX. Tale problema si risolve facilmente utilizzando un array dinamico e passando il massimo numero di elementi al costruttore.


// codaa.h
// classe rappresentante una coda limitata
// tramite un array

#ifndef _CODA_A_H_
#define _CODA_A_H_

template<class T, unsigned int MAX>
class CodaA {
public:
  CodaA (bool Possiede = true);
  // tutti i membri sono non dinamici, per cui e` inutile
  // definire il cc, l'operatore = e il distruttore
  // CodaA (const CodaA&);
  // const CodaA& operator= (const CodaA&);
  // ~Coda ();

  T* primo () const;
  T* ultimo () const {
    if (indice == 0) return coda[MAX-1];
    else return coda[indice - 1]; }
  T* push (T* nuovo_oggetto);
  unsigned int max () const { return MAX; }
private:
  T* coda[MAX];
  unsigned indice;  // indice del primo elemento
  bool possiede;
  unsigned n_elem;
  // funzione interna che segnala quando l'array e` pieno
  bool pieno () const {
    if (n_elem >= MAX) return true;
    return false; }
};

template<class T, unsigned int MAX>
CodaA<T,MAX>::CodaA (bool Possiede) {
  possiede = Possiede;
  for (int i = 0; i < MAX; i++)
    coda[i] = 0;
  indice = 0;
  n_elem = 0;
}

template<class T, unsigned int MAX>
T* CodaA<T,MAX>::primo () const {
  if (!pieno() || (indice == MAX - 1))
    return coda[0];
  return coda[indice];
}

// attenzione: push restituisce un puntatore all'oggetto
// che viene (eventualmente) estratto
template<class T, unsigned int MAX>
T* CodaA<T,MAX>::push (T* nuovo_oggetto) {
  T* tmp = 0;
  if (!pieno()) {
    if (indice == (MAX - 1)) {
      indice = 0;
      coda[MAX - 1] = nuovo_oggetto;
    }
    else {
      indice++;
      coda[indice - 1] = nuovo_oggetto;
    }
    n_elem++;
    coda[indice - 1] = nuovo_oggetto;
    return tmp;
  }
  else if (indice == (MAX - 1)) {
    if (possiede == true)
      delete coda[0];
    else
      tmp = coda[MAX - 1];
    indice = 0;
    coda[MAX - 1] = nuovo_oggetto;
  }
  else {
    if (possiede == true)
      delete coda[indice];
    else
      tmp = coda[indice];
    indice++;
    coda[indice - 1] = nuovo_oggetto;
  }
  return tmp;
}

#endif // _CODA_A_H_

La funzione pop() non è stata implementata in quanto non necessaria: una volta che la coda è piena sarà la stessa funzione push a estrarre i primi elementi inseriti; si noti che tale funzione restituisce un puntatore all'oggetto estratto, non, come negli stack e nella CodaL, all'oggetto inserito.

Il seguente esempio mostra come si possa semplicemente utilizzare un oggetto di tipo CodaA:


// ex11_3_2.cpp

#include "codaa.h"
#include <iostream.h>

void main() {
  CodaA<int, 5> c(false);
  for (int i = 1; i <= c.max(); i++)
    c.push(new int(i));
  cout << "primo:\t" << *c.primo() << "\n";
  cout << "ultimo:\t" << *c.ultimo() << "\n";
  for (int i = 1; i <= c.max(); i++)
    cout << *c.push(new int(-i)) << "\n";
  cout << "primo:\t" << *c.primo() << "\n";
  cout << "ultimo:\t" << *c.ultimo() << "\n";
}

output:
primo: 1
ultimo: 5
1
2
3
4
5
primo: -1
ultimo: -5

ex-2
si implementino il costruttore di copia e l'operatore di assegnamento per la classe template CodaL;
ex-3
si reimplementi la classe CodaA utilizzando la variabile membro max come massimo numero di elementi contenuti, piuttosto dell'argomento template MAX


next up previous contents index
Next: Tabella Up: Alcuni tipi di dati Previous: Stack   Indice   Indice analitico
Claudio Cicconetti
2000-09-06