Tipi di dati astratti: Lo Stack, con algoritmo in Java 5.0

Eccoci finalmente arrivati alla prima stuttura di dati che andremo ad analizzare, lo Stack.

391px-Data stack

Prima di cominciare vorrei fare una piccola premessa, utilizzo il linguaggio Java per implementare gli algoritmi (in particolare Java 5.0), si presume (come ho citato nell’articolo precedente) che conosciate almeno in piccola parte il linguaggio Java, in particolare Classi, interfacce, Variabili assegnamenti e operatori/operazioni, cicli, packages e chi pi ne ha pi ne metta. Non vorrei trattare guide riguardanti la normale programmazione in Java in quanto ci sono degli ottimi libri che permettono di superare addirittura un esame universitario (nel mio caso cos stato :P ), mi permetto quindi di citarvi l’ottimo Java Mattone dopo Mattone, liberamente scaricabile e utilizzabile da tutti, non sar aggiornatissimo ma una volta acquisiti i fondamenti iniziali aggiornarsi alle ultime versioni di Java non sar un problema ;) .

Uno Stack una struttura di dati astratta, all’universit lo chiamiamo TDA (Tipo di Dati Astratto), definizione forse pi azzeccata perch una volta definita questa struttura avremo proprio un nuovo tipo di dato da poter utilizzare per i nostri programmi.

Il principio di funzionamento di uno Stack semplicissimo, immaginate una pila di piatti dove l’ultimo ad essere posizionato il primo ad uscire e cos man mano potremo prendere sempre l’ultimo piatto (elemento/oggetto). Questa tipologia di inserimento/rimozione oggetti prende il nome di last-in first-out (LIFO), in parole povere il primo ad entrare l’ultimo ad uscire.

In uno stack/pila abbiamo principalmente due funzionalit che chiameremo con il nome di metodi:

  • push(e): Inserisce l’elemento e, naturalmente in testa allo stack;
  • pop(): pop invece non ha bisogno di argomenti/parametri perch prende, o meglio toglie, dal nostro stack l’ultimo elemento e ce lo restituisce. In questo metodo per, nel caso lo stack fosse vuoto, avremo un errore perch pop() non sar capace di prendere elementi dallo stack, gli errori in java vengono comunemente definiti come eccezioni;

Inoltre ai nostri due metodi che definiscono la base di funzionamento dello stack abbiamo anche 3 metodi aggiuntivi, non saranno obbligatori ma ci permettono di gestire al meglio l’intero stack e di gestire alcune eccezioni risparmiando cos anche un po di tempo:

  • size(): ritorna il numero degli elementi nello stack;
  • isEmpty(): ritorna un valore booleano (vero, falso) per indicare se lo stack vuoto o meno;
  • top():top invece un metodo abbastanza simile al pop() soltanto che invece di togliere l’elemento dallo stack per fornircene il contenuto si limita soltanto a leggerlo e restiturci il risultato, in questo modo naturalmente non potremo leggere il contenuto dell’elemento successivo (contenuto sotto) finch non effettueremo il pop(), anche questo metodo lancia un eccezione nel caso lo stack sia vuoto.

Il codice per la rispettiva interfaccia in Java 5.0 sar di questo tipo:

 package stack;
 
 import exception.EmptyStackException;
 
 public interface Stack<E> {
  public int size();
  public boolean isEmpty();
  public E top() throws EmptyStackException;
  public void push (E element);
  public E pop() throws EmptyStackException;
 }

Tramite l’interfaccia potremo implementare tutti gli algoritmi e definire la struttura di dati che pi ci piace senza dover per forza fornire dettagli sulle nostre implementazioni semplicemente perch dovremmo soddisfare tutti i requisiti richiesti dall’interfaccia e quindi implementare tutti i metodi. Da notare che importo da un secondo package, exception, la classe EmptyStackException che ci permetter di gestire i nostri errori di tipo Stack Vuoto, il codice il seguente:

package exception;

@SuppressWarnings("serial")
public class EmptyStackException extends RuntimeException{

public EmptyStackException(String exception) {
super(exception);
}

}

In questo articolo implementeremo una rudimentale struttura di dati per lo Stack grazie ad un array, come potrete ben capire da soli avremi dei problemi:

  • Dovendo dichiarare l???array avremo una dimensione ben definita e quindi non pi modificabile (con tutti i problemi che naturalmente ne deriveranno);
  • Una volta riempito l???array il push, se eseguito ancora, lancer un???eccezione di stack pieno (FullStackException);
  • Gli elementi nell???array verranno aggiunti da destra verso sinistra;
  • Riempito l???array e quindi il push per effettuare una nuova push dovremmo per forza di cose effettuare una pop;

Vediamo quindi il codice in Java 5.0:

package stack;

import exception.EmptyStackException;
import exception.FullStackException;

public class ArrayStack<E> implements Stack<E>{
 protected int capacity;
 public static final int CAPACITY = 1000;
 protected E[] S;
 protected int top = -1;
 
 public ArrayStack() {
  this(CAPACITY);
 }
 @SuppressWarnings("unchecked")
 public ArrayStack(int capacity) {
  this.capacity=capacity;
  S = (E[]) new Object[capacity];
 }
 public boolean isEmpty() {
  return (top<0);
 }
 public E pop() throws EmptyStackException {
  E element;
  if (isEmpty())
   throw new EmptyStackException("Lo stack e' vuoto.");
  element = S[top];
  S[top--] = null;
  return element;
 }
 public void push(E element) throws FullStackException{
  if (size() == capacity)
   throw new FullStackException("Lo stack e' pieno.");
  S[++top] = element;
 }
 public int size() {
  return top+1;
 }
 public E top() throws EmptyStackException {
  if (isEmpty()) throw new EmptyStackException("Lo stack e' vuoto.");
  return S[top];
 }
 public String toString() {
  String s;
  s = "[";
  if (size() > 0) s+= S[0];
  if (size() > 1)
   for (int i=1; i<= size()-1; i++)
    s += ", " + S[i];
  return s+"]";
 }
 public void status(String op, Object element) {
  System.out.print("------>" + op);
  System.out.println(", returns " + element);
  System.out.print("result: size = "+size() + ", isEmpty = "+ isEmpty());
  System.out.println(", stack: " + this);
 }
}

Da notare che stata richiamata una nuova classe per le eccezioni di Stack pieno, seguendo l???esempio della prima classe di Exception semplicissimo creare un???altra classe con nome variato, ma gia ce ce l???ho salvata in Eclipse vi copio anche questa parte ;) :

package exception;

@SuppressWarnings("serial")
public class FullStackException extends RuntimeException{

 public FullStackException(String errore) {
  super(errore);
 }

}

Come vedrete ci sono anche alcuni metodi accessori che utilizzeremo per la nostra classe di test:

package stack;

public class TestArrayStack {
 public static void main(String[] args) {
  Object o;
  ArrayStack<Integer> A = new ArrayStack<Integer>();
  A.status("new ArrayStack<Integer> A", null);
  A.push(7);
  A.status("A.push(7)", null);
  o = A.pop();
  A.status("A.pop()", o);
  A.push(9);
  A.status("A.push(9)", null);
  o = A.pop();
  A.status("A.pop()", o);
  ArrayStack<String> B = new ArrayStack<String>();
  B.status("new ArrayStack<String> B", null);
  B.push("Bob");
  B.status("B.push(\"Bob\")", null);
  B.push("Alice");
  B.status("B.push(\"Alice\")", null);
  o = B.pop();
  B.status("B.pop()", o);
  B.push("Eve");
  B.status("B.push(\"Eve\")", null);
 }

}

Perdonatemi se non mi dilungo a spiegare il codice pi di tanto stasera ho perso 4 ore per poter formattare il codice senza perdere validazione W3C e senza perdere alcune parti di codice di Java 5.0 incompatibili con WordPress (mi chiude i tag in automatico) e con il plugin Wp-Syntax che ho dovuto modificare per eliminare il controllo sulle identazioni e su tutti i caratteri speciali html (su quelli il controllo manuale sempre migliore ;) ), poi con l???editor avanzato sempre su ???disattivato??? chiaro :P

Il libro di riferimento Data Structures and Algorithms in Java, fourth edition.
Di Michael T. Goodrich e Roberto Tamassia (in english naturalmente ehehhe ). L???algoritmo rispecchia lo stesso metodo risolutore riportato nel libro, ma il bello cominceremo a vederlo tra poco quando il libro non riporter pi degli esempi tanto carini, ma io l???anno scorso queste cose le ho fatte fino a met corso???diciamo che sono molto anticipato sul libro e sul programma ehehe ;)

Naturalmente qualsiasi cosa chiedete, nei limiti del possibile prover a darvi una risposta, ma sono dell???idea che questi esercizi dobbiate farveli da soli non vale la pena di copiare questi, si fa una figura di m??? all???interrogazione perch difficilmente si sapr discutere codice non commentato di altre persone ne tantomeno si sapr dove spostarsi esattamente con lo sguardo e con il ditino. Sisi mi stato chiesto addirittura questo in un esame per verificare l???autenticit del mio codice!!!

Tag: ,

13 Commenti a “Tipi di dati astratti: Lo Stack, con algoritmo in Java 5.0”

  1. alexwizard scrive:

    bellissimo post!
    spero ne seguano tanti altri prossimamente…
    non vedo l’ora di leggerli!
    grazie.

  2. [...] simile al pop dello stack, legge il primo elemento della coda senza per toglierlo da essa, lancia un’eccezione se [...]

  3. Traffyk scrive:

    Grazie AlexWizard, oggi ne ho pubblicato un altro :D
    Comunque benvenuto nel mio blog, la prima volta se non sbaglio che ti vedo..non hai un sito/blog? Sai mi piace sempre sbirciare siti/blog dei miei lettori/commentatori :P

  4. TheKaneB scrive:

    piccola correzione
    in questo modo naturalmente non potremo leggere il contenuto dell

  5. Traffyk scrive:

    We ciao Antonio grazie per la correzione ;) Ho aggiustato, comunque a inizio articolo ho pubblicato il link al libro Java mattone su mattone, questa parte un pochino pi avanzata e avrei anche il piacere di fare una guida for dummies ma purtroppo il tempo non c’ proprio quindi mi limito in buona parte a ricopiare per intero l’esercizio che ho svolto… Ehehe se vedi l’articolo sulla coda ancora peggio :P

    Riguardo al copiare ehehe non so se hai letto, in un esame mi fu chiesto di mettere il ditino sulle parti di codice che commentavo per vedere se davvero sapevo dove muovermi..fortunatamente ho sempre avuto l’abitudine di rifare da capo anche algoritmi interamente gia svolti proprio per avere la padronanza assoluta sugli algoritmi :)

  6. TheKaneB scrive:

    Quel libro davvero fatto bene, ho dato solo una sfogliata al pdf perch almeno al momento non mi interessa approfondire il Java, ma i contenuti sono di prima qualit! ;)
    Riguardo al copiare gli esercizi fondamentale saperli implementare da zero, altrimenti non si pu minimamente sognare di diventare programmatori! ^_^

  7. LiLy scrive:

    Ciao, se non ho capito hai superato l’esame di programmazione ad oggetti in java. Posso chiederti che testo hai utilizzato? A me hanno consigliato “Thinking in Java”, ma davvero prolisso…. Complimenti per il blog.
    Ciao!

  8. Traffyk scrive:

    Ciao LiLy ho appunto citato l’ottimo libro Java Mattone su Mattone nel primo paragrafo dell’articolo, sul quale ho studiato e superato l’esame LP2 (Linguaggi di Programmazione 2), davvero molta pratico e ha pochi fronzoli teorici (odio la teoria), un programmatore deve saper concepire algoritmi, spesso un esempio pratico vale pi di mille parole per lo scopo ;)

  9. x Traffyk

    Raffaele, ma il libro di riferimento Data Structures and Algorithms in Java, fourth edition, disponibile anche on-line?

  10. Traffyk scrive:

    Ciao Marcello purtroppo quel libro non disponibile online che io sappia.. potresti provare sui mezzi di diffusione alternativi ma credo avrai scarsi risultati, io ho dovuto comprarlo il libro.

Lascia un Commento



  • Metti mi piaceeee!!!

  • Feed RSS e contatti

    il mio super sexy feed rss
    Contatti (email, msn):

  • Weber Saint-Gobain

    Weber Saint-Gobain Sono agente tecnico commerciale, in qualità di collaboratore esterno, rappresentante l'agenzia Weber Saint-Gobain per la provincia di Salerno.
    Per maggiori informazioni ti invito a visitare il mio nuovo sito www.agenzianappo.it.
  • Consigli

    Questo blog è ospitato su Dreamhost, sei invece vuoi provare l'avventura di blogger e seguire le mie orme perchè non provi a visitare Italian Bloggers, Guadagnare Scrivendo!.

  • OpenStreetMap

    openstreetmap Sono mapper su OpenStreetMap, un progetto mondiale gratuito per la creazione di mappe stradali. Il mio nome utente è Traffyk.
  • Come guadagna il blog e disclaimer

    Semplicissimo, grazie a SprinTrade, ecco un mio articolo che spiega come guadagnare facendo scaricare giochi.
    Per qualsiasi richiesta comunque contattatemi via mail (sopra) o lasciate un commento.