next up previous contents index
Next: Coda Up: Alcuni tipi di dati Previous: Lista bilaterale   Indice   Indice analitico

Stack

Lo stack è un contenitore comune all'interno di una gran varietà di programmi; esso rappresenta infatti un array unidimensionale, che abbia la seguente particolarità: è possibile accedere esclusivamente l'ultimo elemento che si è inserito, cioè l'accesso è di tipo LIFO (Last In First Out, it. ``l'ultimo elemento che viene inserito è il primo a uscire''). Le due operazioni più comuni da effettuare su di uno stack sono schematizzate come segue:
Effettuare un push su di uno stack significa semplicemente aggiungere un elemento in testa ad esso, mentre effettuare un pop corrispondere ad eliminare l'ultimo elemento inserito; un'altra operazione comune è il peek: lettura del valore dell'elemento di testa dello stack. L'esempio più ovvio di stack è la memoria allocata dai nostri programmmi per le variabili automatiche: il compilatore inserisce nello stack le variabili mano a mano che esse vengono create all'interno dei vari blocchi, in maniera tale che le ultime a essere create, nei blocchi più interni, solo le prime ad essere deallocate e viceversa.

Noi presenteremo, a titolo di esempio, due possibili implementazioni di uno stack: StackL tramite una lista semplice, StackA tramite un array dinamico; i nostri stack saranno di tipo molto semplice, consentendo essenzialmente le tre operazioni fondamentali su descritte. Entrambe, ovviamente, saranno implementate con una classe template. Visto che le funzioni costruttore di copia e sovrapposizione dell'operatore di assegnamento sono formalmente identiche alle corrispodenti funzioni della classe Lista, eviteremo di ripeterle; esse saranno pertante dichiarate private, in maniera tale da inibire un uso improprio da parte dell'utilizzatore della classe.


// stackl.h
// classe rappresentante uno stack
// implementato tramite una lista semplice

#ifndef _STACK_L_H_
#define _STACK_L_H_

#include <iostream.h>

template<class T>
class StackL {
public:
  StackL (bool Possiede = true) {
    possiede = Possiede;
    testa = 0; }
  ~StackL ();

  bool possesso () const { return possiede; }
  T* peek () const;
  T* pop ();
  T* push (T* nuovo_oggetto);
  StackL& operator+= (T* nuovo_oggetto) {
    push(nuovo_oggetto); return *this; }
private:
  StackL (const StackL&);
  const StackL operator= (const StackL&);
  struct elem {
    elem* next;
    T* oggetto;
    elem (T* Oggetto, elem* Next = 0) {
      oggetto = Oggetto;
      next = Next; }
  };
  elem* testa;
  bool possiede;
};

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

template<class T>
T* StackL<T>::peek () const {
  if (testa != 0)
    return testa->oggetto;
  return 0;
}

template<class T>
T* StackL<T>::pop () {
  T* tmp = 0;
  if (testa != 0) {
    elem* p = testa;
    testa = testa->next;
    if (possiede == true)
      delete p->oggetto;
    else
      tmp = p->oggetto;
    delete p;
  }
  return tmp;
}

template<class T>
T* StackL<T>::push (T* nuovo_oggetto) {
  testa = new elem (nuovo_oggetto, testa);
  return nuovo_oggetto;
}

#endif // _STACK_L_H_

Come si vede, la rappresentazione di uno stack tramite una lista semplice è del tutto naturale: le funzioni di inserimento ed estrazioni corrispondono ad operazioni effettuare sulla testa della lista e, per questo motivo, sono semplici da realizzare e efficienti nella esecuzione. Un esempio di utilizzo della classe StackL è:


// ex11_2_1.cpp
#include "stackl.h"

void svuota(StackL<int>& s) {
  while (s.peek() != 0)
    cout << *s.pop() << "\n";
}

void main() {
  StackL<int> s1 (false);
  s1.push(new int(4));
  s1.push(new int(-1));
  s1.push(new int(3));
  s1 += new int(7);
  svuota(s1);
}

output:
7
3
-1
4

Una struttura dati che può ugualmente rappresentare uno stack è l'array dinamico. Supponiamo di avere dunque il nostro vettore di puntatori; se dobbiamo effettuare un inserimento le operazioni che dobbiamo effettuare sono le seguenti: copia dell'intero vettore in uno temporaneo, eliminazione del vettore preeistente, allocazione di memoria per il nuovo vettore, copia degli elementi dal vettore temporaneo a quello definitivo; tali operazioni hanno un costo di esecuzione che, se lo stack è ``grande'', è non indifferente; un discorso del tutto analogo lo si può condurre per la rimozione di un elemento. Dunque utilizzare un array per rappresentare uno stack, nel quale le uniche operazioni sono l'inserimento e l'estrazione, sembra una strada poco agibile. In realtà possiamo allocare e deallocare memoria non una cella per volta, ma a blocchi: stabiliamo a nostra discrezione la dimensione di un blocco11.3 e, in un certo senso, quantizziamo le operazioni di inserimento ed estrazione. Supponiamo ad esempio di prendere blocchi di 5 celle; quando operiamo il primo pop allochiamo un array di 5 elementi, il quale permane fino al sesto pop, con il quale dovremo deallocare l'array di 5 elementi e allocarne uno di 10, e così via.


// stacka.h
// classe rappresentante uno stack
// implementato tramite un array dinamico

#ifndef _STACK_A_H_
#define _STACK_A_H_

const int DIM_BLOCCO = 5;

template<class T>
class StackA {
public:
  StackA (bool Possiede) {
    stack = 0; n_elem = 0;
    possiede = Possiede; }
  StackA (const StackA&);
  ~StackA ();

  unsigned int quanti () const { return n_elem; }
  T* peek () const;
  T* pop ();
  T* push (T* nuovo_oggetto);
private:
  const StackA& operator= (const StackA&);
  T** stack;
  unsigned int n_elem;
  unsigned int allocati;
  bool possiede;
};

template<class T>
StackA<T>::StackA (const StackA& s) {
  possiede = false;
  n_elem = s.n_elem;
  allocati = s.allocati;
  if (n_elem != 0) {
    int i; // variabile contatore
    stack = new T*[allocati];
    for (i = 0; i < n_elem; i++)
      stack[i] = s.stack[i];
    // azzera i puntatori rimasti fluttuanti
    for (i = n_elem; i < allocati; i++)
      stack[i] = 0;
  }
  else
    stack = 0;
}

template<class T>
StackA<T>::~StackA () {
  if (possiede == true)
    for (int i = 0; i < n_elem; i++)
      delete stack[i];
  delete[] stack;
}

template<class T>
T* StackA<T>::peek () const {
  if (n_elem > 0)
    return stack[n_elem - 1];
  return 0;
}

template<class T>
T* StackA<T>::pop () {
  T* tmp = 0;
  if (n_elem <= 0)
    return tmp;
  if (n_elem % DIM_BLOCCO == 1) {
    if (n_elem == 1) {
      if (possiede == true)
        delete stack[0];
      else
        tmp = stack[0];
      delete[] stack;
      stack = 0;
      allocati = 0;
      n_elem = 0;
    }
    else {
      allocati -= DIM_BLOCCO;
      T** stack2 = new T*[allocati];
      for (int i = 0; i < allocati; i++)
        stack2[i] = stack[i];
      if (possiede == true)
        delete stack[allocati];
      else
        tmp = stack[n_elem - 1];
      stack = stack2;
      n_elem--;
    }
  }
  else {
    if (possiede == true)
      delete stack[n_elem - 1];
    else
      tmp = stack[n_elem - 1];
    stack[n_elem - 1] = 0;
    n_elem--;
  }
  return tmp;
}

template<class T>
T* StackA<T>::push (T* nuovo_oggetto) {
  if (n_elem == 0) {
    allocati = DIM_BLOCCO;
    stack = new T*[allocati];
    for (int i = 0; i < allocati; i++)
      stack[i] = 0;
    stack[0] = nuovo_oggetto;
    n_elem = 1;
  }
  else if (n_elem % DIM_BLOCCO == 0) {
    allocati += DIM_BLOCCO;
    T** stack2 = new T*[allocati];
    for (int i = 0; i < n_elem; i++)
      stack2[i] = stack[i];
    n_elem++;
    stack2[n_elem - 1] = nuovo_oggetto;
    for (int j = n_elem; j < allocati; j++)
      stack2[j] = 0;
    stack = stack2;
  }
  else {
    n_elem++;
    stack[n_elem - 1] = nuovo_oggetto;
  }
  return nuovo_oggetto;
}

#endif // _STACK_A_H_

Un programma che mostri l'utilizzo di uno StackA è il seguente:


// ex11_2_2.cpp

#include "stacka.h"
#include "stringa.h"
#include <iostream.h>


void stampa(const StackA<Stringa>& s) {
  StackA<Stringa> copia(s);
  while (copia.peek() != 0)
    cout << *copia.pop() << "\n";
}

void main() {
  StackA<Stringa> s(false);
  s.push(new Stringa("BeOS"));
  s.push(new Stringa("FreeBSD"));
  s.push(new Stringa("IRIX"));
  s.push(new Stringa("Linux"));
  s.push(new Stringa("NetBSD"));
  s.push(new Stringa("QNX"));
  s.push(new Stringa("Solaris"));
  s.push(new Stringa("SunOS"));
  s.push(new Stringa("Windows NT"));
  s.pop();
  stampa (s);
}

output:
SunOS
Solaris
QNX
NetBSD
Linux
IRIX
FreeBSD
BeOS

Abbiamo presentato dunque due alternative per la realizzazione di uno stack; la domanda che facilmente sorge è la seguente: qual è la strada migliore? Dipende. Uno stack implementato con una lista ha una velocità di esecuzione indipendente dal numero di elementi in esso contenuti, mentre uno stack implementato con un array dinamico impiega un tempo decisamente minore quando non deve riallocare nuova memoria per il push o deallocarne per il pop; per questo motivo uno stack il cui numero di elementi si mantiene più o meno costante, dal momento della creazione fino alla distruzione, è meglio rappresentabile con un array, mentre in generale è preferibile la struttura a lista.

ex-2
si costruisca una classe CoseDaFare, avente le seguenti funzioni membro:


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