Problema implementazione stack stramite coda

**Darèios89** · 21-05-2010, 17:43

Non va.....ho sbagliato forse qualcosa nel metodo?
Ti posto l'intera classe Coda che implementa l'interfaccia:

codice:

public class Queue<E> implements Stack<E>
{
	private int size;
	
	private Queue <E> coda;
	
	private Node <E> top;
	
	private Node<E> front;
	
	private Node<E> rear;
	
	public Queue()
	{
		
		rear=top=null;
		front=rear;
		size=0;
	}
	
	public boolean isEmpty(){return(top==null);}
	
	public int getSize(){return size;}
	
	public E top() throws EmptyStackException
	{
		
		if(isEmpty()) throw new EmptyStackException("Stack vuoto.");
		return rear.getElement();
		
	}
	
	public E pop() throws EmptyStackException
	{
		if(isEmpty()) throw new EmptyStackException("Stack vuoto.");
		E object=front.getElement();
		Queue<E> appoggio=new Queue<E>();
		
		if(coda.getSize()==1) coda=null;
		
		while(front.getNext()!=null)
		{
			appoggio.push(front.getElement());
			front=front.getNext();
		}
		
		coda=appoggio;
		
		return object;
	
		
		/*

		E object=front.getElement();
		front=front.getNext();
		size--;
		
		if(size==0)
			rear=null;
		return object;*/
	}
	
	public void push(E element)
	{
		Node <E> node=new Node<E>(element, null);
		if(isEmpty())
			front=node;
		else rear.setNext(node);
		rear=node;
		size++;
	}
	
	public String toString()
	{
		String Coda="[";
		Node<E> node;
		for(node=new Node<E>(front.getElement(),front.getNext());node.getNext()!=null; node=node.getNext())
		Coda+=node.getElement()+", ";
		Coda+=node.getElement()+"]";
		
		return Coda;
	}
		
		
}

A parte il toString() che credo sia sicuramente sbagliato perchè stampa al contrario.
In output mi dovrebbe stampare il numero di EmptyStackException e di sotto la configurazione dello stack:
Ma così gli errori risultano 0 e la configurazione contiene solo 24.....

P.S Oltre al problema principale di sopra,perchè se all'inizio al posto di inizializzare solamente la coda "coda" faccio la creazione, poi ho un' eccezione?

**andbin** · 21-05-2010, 18:04

Originariamente inviato da Darèios89
[code]public class Queue<E> implements Stack<E>
{

private Queue <E> coda;

Scusa eh ma se il tuo "stack basato su coda" si chiama Queue e dentro usi Queue (che è proprio sé stesso) ... che senso ha?? Perché la tua coda (proprio quel campo 'coda' intendo) è del tipo della tua classe .... che è uno stack!

Devi avere una classe per la Queue es.

public class Queue<E> .......
o se Queue è una interfaccia e va quindi implementata
public class MiaCoda<E> implements Queue<E> .....

e un'altra classe per il tuo "stack basato su coda" es. (nomi sparati eh):

public class StackConCoda<E> implements Stack<E> .....
...qui usa la implementazione della queue...

**Darèios89** · 21-05-2010, 18:20

Quindi dato che la coda la implemento con listalinkata, deduco che devo creare anche una classe lista linkata semplice?

**Darèios89** · 21-05-2010, 19:26

Ho un altro problema....io ho creato la classe coda:

E poi la classe Stackconcoda, Ho un NullpointerException nel toString di Stackconcoda:

codice:

public class Queue<E>
{
	private int size;
	
	private Node<E> front;
	
	private Node<E> rear;
	
	public Queue()
	{
		
		front=null;
		rear=null;
		size=0;
	}
	
	public boolean isEmpty(){return(rear==null);}
	
	public int getSize(){return size;}
	
	public E front(){
		if(isEmpty()) throw new EmptyQueueException("Coda vuota.");
		return front.getElement();
		}
		
	public Node<E> NextFront() {
		
		return front.getNext();
		}
	

	public E dequeue() throws EmptyQueueException
	{
		if(isEmpty()) throw new EmptyQueueException("Coda vuoto.");
		E object=front.getElement();
		front=front.getNext();
		size--;
		
		if(size==0)
			rear=null;
		return object;
	}
	
	public void enqueue(E element)
	{
		Node <E> node=new Node<E>(element, null);
		if(isEmpty())
			rear=node;
		else rear.setNext(node);
		rear=node;
		size++;
	}
	
}

codice:

public class Stackconcoda<E> implements Stack<E>
{
	private int size;
	
	private Queue <E> coda;
	
	private Node <E> top;
	
	public Stackconcoda()
	{
		top=null;
		size=0;
	}
	
	public boolean isEmpty(){return(top==null);}
	
	public int getSize(){return size;}
	
	public E top() throws EmptyStackException
	{
		
		if(isEmpty()) throw new EmptyStackException("Stack vuoto.");
		return top.getElement();
		
	}
	
	public E pop() throws EmptyStackException
	{
		if(isEmpty()) throw new EmptyStackException("Stack vuoto.");
		E object=coda.front();
		Queue<E> appoggio=new Queue<E>();
		
		if(coda.getSize()==1) coda=null;
		
		
		Node<E>node=new Node<E>(coda.front(),coda.NextFront());
		while(node.getNext()!=null)
		{
			appoggio.enqueue(node.getElement());
			node=node.getNext();
		}
		
		coda=appoggio;
		
		return object;
		/*

		E object=front.getElement();
		front=front.getNext();
		size--;
		
		if(size==0)
			rear=null;
		return object;*/
	}
	
	public void push(E element)
	{
		Node <E> node=new Node<E>(element, top);
		if(isEmpty())
		top=node;
		else top.setNext(node);
		top=node;
		size++;
	}
	
	public String toString()
	{
		String Stack="[";
		Node<E> node;
		for(node=new Node<E>(coda.front(),coda.NextFront());node.getNext()!=null; node=node.getNext())
		Stack+=node.getElement()+", ";
		Stack+=node.getElement()+"]";
		
		return Stack;
	}
		
		
}

.

**Darèios89** · 22-05-2010, 15:03

Non capisco perchè......mannaggia...

**andbin** · 22-05-2010, 15:35

Originariamente inviato da Darèios89

codice:

public class Queue<E>
{
   ....
	
	public void enqueue(E element)
	{
		Node <E> node=new Node<E>(element, null);
		if(isEmpty())
			rear=node;
		else rear.setNext(node);
		rear=node;
		size++;
	}
	
}

Già solo la Queue non "quadra". Se aggiungi un elemento, è logico andare ad aggiornare 'rear' ma se è il primo elemento devi anche aggiornare 'front'. E questo non lo fai.
E c'è anche altro di dubbio, comunque.

Originariamente inviato da Darèios89

codice:

public class Stackconcoda<E> implements Stack<E>
{
	private int size;
	
	private Queue <E> coda;
	
	private Node <E> top;
...

E nemmeno Stackconcoda "quadra". Perché dovresti usare i Node?? Se ti metti ad usare i Node con i vari setNext() ecc... stai usando il linkamento tra i nodi ... non una coda. E allora che "stack con coda" sarebbe??

In StackConCoda, il tuo "stack" .... è solo il Queue!! I push() fanno andare direttamente nella Queue, non c'è nulla di particolare da dire. I pop() ... no, nel senso che Queue non ha un pop(). Ha un dequeue() che torna il primo inserito ... non l'ultimo.
E allora puoi fare la procedura che ho detto: scarichi la Queue mettendo tutto in un'altra Queue ma tenendo da parte l'ultimo che poi restituisci. E la nuova Queue diventa la Queue "corrente" del tuo StackConCoda.

**Darèios89** · 22-05-2010, 19:31

Senti scusa, io sto sclerando, detto chiaro.

Non sto capendo come lavorare senza i metodi dei nodi, quindi ti chiederei se puoi di farmi la classe Coda tu....

**andbin** · 22-05-2010, 23:55

Originariamente inviato da Darèios89
quindi ti chiederei se puoi di farmi la classe Coda tu....

Ehm ... no, dovresti farlo tu. Primo, perché il "compito" è tuo, secondo perché ti assicuro che è molto molto più semplice di quanto forse hai pensato finora.

Partiamo da un presupposto: che hai una classe Queue corretta e funzionante. Dove ci sono i due metodi principali enqueue() (inserisce in coda) e dequeue() (estrae dalla coda). Più ovviamente altri metodi che possono servire come isEmpty() o altri.
Ma quelli che gestiscono in modo vero e proprio la coda sono i primi due.

Ora, la classe Queue che avevi postato mi pareva un po' dubbia e non proprio corretta ... quindi per prima cosa verifica bene il suo funzionamento.

Adesso, per quello che dirò, possiamo dare per scontato che Queue funzioni? Bene.

Devi fare una classe che gestisce uno "stack" e che è basata su una coda. Questo vuol dire che all'interno di un oggetto StackConCoda dovrebbe esserci .... un Queue!

In StackConCoda potresti avere anche solo 1 campo:

private Queue<E> coda;

e basta. Non serve avere dei "nodi" o liste o altro.

Il push() del tuo stack banalmente e semplicemente inserisce l'elemento nella Queue. Più lineare di così si muore .....

Il pop() del tuo stack non può banalmente invocare 1 metodo della Queue e basta. Primo perché Queue non ha un pop() e secondo perché il dequeue(), che esiste, restituisce il primo elemento .... non l'ultimo. Queue è FIFO (first-in ...), Stack è LIFO (last-in ...).
Ma si può fare con un escamotage. Si "scarica" tutta la Queue corrente in una nuova Queue tenendosi però l'ultimo elemento che si dovrà restituire. Il reference alla nuova Queue lo assegni al campo 'coda' in modo che diventi effettivamente la "coda" dello stack (quella svuotata non sarà più referenziata e finirà in pasto al garbage collector, prima o poi).

Tutto qui.

**Darèios89** · 23-05-2010, 12:40

Ehm ... no, dovresti farlo tu. Primo, perché il "compito" è tuo, secondo perché ti assicuro che è molto molto più semplice di quanto forse hai pensato finora.

Hai ragione, bene, mi sono messo a rivedere un pò di cose....allora, ho cambiato qualcosa nella classe coda di prima, volevo chiederti conferma..

codice:

public class Queue<E>
{
	private int size;
	
	private Node<E> front;
	
	private Node<E> rear;
	
	public Queue()
	{
		
		front=null;
		rear=null;
		size=0;
	}
	
	public boolean isEmpty(){return(rear==null);}
	
	public int getSize(){return size;}
	
	public E front(){
		if(isEmpty()) throw new EmptyQueueException("Coda vuota.");
		return front.getElement();
		}
		
	public E rear()
		{
			if(isEmpty()) throw new EmptyQueueException("Coda vuota");
			return rear.getElement();
		}
		
	
	public E dequeue() throws EmptyQueueException
	{
		if(isEmpty()) throw new EmptyQueueException("Coda vuoto.");
		E object=front.getElement();
		if (size==1)
			front=rear=null;
		else
		front=front.getNext();
		size--;
		
		return object;
	}
	
	public void enqueue(E element)
	{
		Node <E> node=new Node<E>(element, null); //rear o null?
		if(isEmpty())
		
			front=rear=node;
		
		else rear.setNext(node);
		rear=node;
		size++;
	}
	
	/*public String toString()
	{
		
	}*/
	
}

Spero la enqueue() e la dequeue() siano corretti, anche se ho un dubbio per la enqueue(), ho messo un commento, ho il dubbio se il nodo che creo debba avere come next null oppure rear in questo caso, io ho messo null.

Poi ho fatto la classe Stackconcoda:

codice:

public class Stackconcoda<E> implements Stack<E>
{
	//private int size;
	
	private Queue <E> coda;
	
	//private Node <E> top;
	
	public Stackconcoda(Queue<E> coda)
	{
		this.coda=coda;
	}
	
	public boolean isEmpty(){return(coda.getSize()==0);}
	
	public int getSize(){return coda.getSize();}
	
	public E top() throws EmptyStackException
	{
		if(isEmpty()) throw new EmptyStackException("Stack vuoto.");
		E object=coda.rear();
		return object;
		
	}
	
	public E pop() throws EmptyStackException
	{
		Queue <E>appoggio=new Queue<E>();
		
		while(coda.getSize()!=1)
		{
			E object=coda.dequeue();
			appoggio.enqueue(object);
		}
		
		E object=coda.dequeue();
		coda=appoggio;
		
		return object;

	}
	
	public void push(E element)
	{
		
		coda.enqueue(element);
	}
	
	/*public String toString()
	{
		return coda.toString();
	}*/
}

Non so....tu hai detto di usare un oggetto Stackconcoda che ha al suo interno un oggetto Coda...
Temo che ci sia qualcosa di sbagliato perchè nell'output dove dovrebbe segnarmi per la pop() gli errori con lo stack vuoto mi dà 0 errori, e non risulta.....
Poi devo pensare come realizzare il toString, perchè essendo uno stack dovrei stampare gli elementi della lista al contrario...

**Darèios89** · 24-05-2010, 12:03

Ci sono ancora errori?

Discussione: Problema implementazione stack stramite coda

Strumenti discussione

Ricerca discussione

Visualizza

Permessi di invio