[C++] Stack e Coda

[Mauri94]

Salve a tutti ragazzi, da poco abbiamo cominciato a studiare i puntatori e come strutture astratte abbiamo studiato solo le liste. (inserimento in testa, in coda, eliminazione di un nodo, visualizzazione dei nodi). Ci è stato chiesto di realizzare la classe 'stack' e la classe 'coda' con i relativi metodi per l'estrazione di un elemento e l'inserimento di un elemento. Ora a livello teorico so che lo STACK ha una struttura del tipo LIFO , last in - first out, cioè il primo ad entrare è l'ultimo ad uscire. Per quanto riguarda la CODA so che ha la struttura opposta, o meglio FIFO , first in - first out. Teoricamente ho buone basi sull'argomento perché l'ho trattato durante lo studio dell' assembler intel 8086. Sullo stack so che posso effettuare delle operazioni come push e pop, o meglio inserire dei dati oppure andarli a recuperare. A livello di linguaggio non ho però capito come procedere, ho cercato delle classi in giro e non ci ho capito molto. Potrei chiedervi un piccolo esempio, anche a livello concettuale ? Non capisco quali attributi dovrebbe avere la classe, o meglio le classi.

[Caiodark]

La struttura di partenza è sempre quella della lista, del resto se hai già tratto l'inserimento in testa e in coda non sono argomenti del tutto nuovi.
Per lo stack devi prevedere pop e push, entrambi in coda. Pop in teoria ti deve restituire l'ultimo elemento togliendolo dalla lista.
Per la Coda hai pushFront e popBack, sempre con il pop che toglie l'elemento che legge.

[Mauri94]

class nodo
{
   public:
      char inf; // Elemento del nodo
      nodo * next; // Puntatore
   
      nodo (char c)
      {
         inf = c;
         next=null;
      }
};

class stack
{
   private:
      nodo * head; // Puntatore di accesso alla lista

   public:
      // Metodo per l'inserimento dell'elemento in coda, ultimo nodo (push)
      // Metodo per il prelievo dell'elemento in testa, primo nodo (pop)
};

Che ne dici? Ho ragionato tenendo come riferimento una memoria logica orientata LO-HI

[Scara95]

Ma in uno stack non inserisci sempre nell'head? O_o

Comunque come base va bene...
per l'inserimento in testa devi allocare un nuovo oggetto e semplicemente farlo puntare al successivo...
per l'inserimento in coda scorrere tutta la lista fino al null e aggiungerlo...
per il pop prendi l'head e poi sostituisci ad essa head->next tutto qui...

[Who am I]

Prendendo spunto da std::list :
http://www.cplusplus.com/reference/stl/list/

Il miglior approccio è quello di scrivere prima i metodi generici, cioè :
-Un metodo che ti estrae il nodo in posizione i-esima;
-Un metodo che ti inserisce un nodo in posizione i-esima.

Oltre a un metodo che calcola la lunghezza della lista (che puoi chiamare size() come quello di std::list).

Una volta scritti questi due metodi puoi fare due classi stack e queue che ereditano dalla classe lista,ed usi il metodo di inserzione e di estrazione che hai scritto nella classe lista.
Ad esempio la pop sarà un' estrazione dell' ultimo nodo (quindi in posizione size()-1 per esempio).
Però il punto è che ti basta scrivere il metodo inserisci ed estrai, che potrai riutilizzare N volte.

[Scara95]

Originariamente inviato da Who am I
Prendendo spunto da std::list :
http://www.cplusplus.com/reference/stl/list/

Il miglior approccio è quello di scrivere prima i metodi generici, cioè :
-Un metodo che ti estrae il nodo in posizione i-esima;
-Un metodo che ti inserisce un nodo in posizione i-esima.

Oltre a un metodo che calcola la lunghezza della lista (che puoi chiamare size() come quello di std::list).

Una volta scritti questi due metodi puoi fare due classi stack e queue che ereditano dalla classe lista,ed usi il metodo di inserzione e di estrazione che hai scritto nella classe lista.
Ad esempio la pop sarà un' estrazione dell' ultimo nodo (quindi in posizione size()-1 per esempio).
Però il punto è che ti basta scrivere il metodo inserisci ed estrai, che potrai riutilizzare N volte.

E' vero, questo approccio è più corretto dal punto di vista di discendenza e parentela degli oggetti ed è più riusabile, concordo.

(effettivamente io sono abbituato a pensare in c , quindi non penso automaticamente all'ereditarietà)

[Mauri94]

Leggendo in ritardo la bellissima idea di 'Who am I' di utilizzare l' ereditarietà per risolvere il problema, ho già pensato ad una soluzione che prevede la creazione di 3 classi (1 per il nodo, 1 per lo stack e 1 per la coda). Mi stavo complicando la vita con il mio ragionamento LO-HI, in effetti dovrei aver risolto il problema procedendo così:

1- Stack : PUSH -> Inserisco i nuovi elementi in testa alla lista ; POP -> Ritiro gli elementi partendo dalla testa. In modo tale che l'ultimo ad entrare è il primo ad uscire.

2- Coda : PUSH -> Inserisci i nuovi elementi in coda alla lista ; POP -> Ritiro gli elementi partendo dalla testa. In modo tale che il primo ad entrare è il primo ad uscire.

Classe NODO :

class nodo
{
   public:
      char inf;
      nodo * next;
      nodo (char c)
      {
         inf=c;
         next=null;
      }
};

Classe STACK con relativo svolgimento dei metodi:

class stack
{
   private:
      nodo * head;
   public:
      void push (char x);
      stack * pop ();
};

void stack::push (char x)
{
   nodo * nuovo = new nodo (x);
   nuovo -> next = head;
   head = nuovo;
}

stack * stack::pop ()
{
   nodo * app = head;
   head = head -> next;
   return app;
}

Classe CODA con relativo svolgimento dei metodi:

class coda
{
   private:
      nodo * head;
   public:
      void push (char x);
      coda * pop ();
};

void coda::push (char x)
{
   nodo * app = head;
   nodo * nuovo = new nodo (x);
   if (app==null)
      cout <<"La lista è vuota!" <<endl;
   else
   {
      while (app -> next != null)
         app = app -> next;
      app -> next = nuovo;
   }
}

coda * coda::pop ()
{
   nodo * app = head;
   head = head -> next;
   return app;
}

Che ne pensate?

[Scara95]

coda * coda::pop ()
{
   nodo * app = head;
   head = head -> next;
   return app;
}

Questa e l'equivalente in stack è sbagliata, il valore di ritorno non è un puntatore a coda, ma a nodo.
inoltre non ti conviene dare come valore di ritorno un elemento nodo (classe usata internamente per costruire la struttura dati), ha più senso dare come valore di ritorno il valore contenuto da nodo, nel tuo caso nodo->inf che è di tipo char.

[Scara95]

Dimenticavo: per rendere la classe generica e non limitarla ad un tipo di dato potresti utilizzare un template, risulterebbe anche più corretto concettualmente.

[Mauri94]

Hai ragione, che stupido! Quindi così? :

nodo * coda::pop ()
{
   nodo * app = head;
   head = head -> next;
   return app -> inf;
}

Per quanto riguarda i template ci avevo già pensato, però per ora avevo buttato giusto qualcosa per cominciare a realizzare le classi che avrei successivamente ottimizzato.