Problema implementazione stack stramite coda

[Darèios89]

Dovrei implementare un' interfaccia Stack tramite coda.
Il problema è nella pop() e push() che non sto capendo come gestire.
In uno stack la pop e la push vengono fatte sempre in top, mentre nella coda l'estrazione avviene in testa(front) e l'inserimento in rear(coda).
Quindi come posso farla funzionare visto che prevede queste cose fatte in modo diverso?

La classe l'ho scritta così:

public class Queue<E> implements Stack<E>
{
	private int errori=0;
	
	private int size;
	
	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(errori+" errori generati");
		return rear.getElement();
		
	}
	
	public E pop() throws EmptyStackException
	{
		if(isEmpty()) throw new EmptyStackException(errori+" errori generati");
		E object=front.getElement();
		rear=rear.getNext();
		size--;
		front=null;
		front=rear;
		return object;
	}
	
	public void push(E element)
	{
		Node <E> node=new Node<E>(element, rear);
		rear=node;
		front=rear;
		size++;
	}
}

[andbin]

Originariamente inviato da Darèios89
Dovrei implementare un' interfaccia Stack tramite coda.

Se una queue fa proprio solo da "coda" nel senso: entra da una parte, esce dall'altra parte (e basta) mi pare abbastanza intuitivo che non puoi e non avrebbe senso usarla per uno stack.

Ma potresti anche avere una collezione che fa sia da queue, sia da stack.
Prendi per esempio java.util.LinkedList che è standard del framework. Può funzionare sia da stack che da queue perché ha tutti i metodi per inserire ed estrarre sia in head che in tail.

[Darèios89]

Siccome sono abbastanza confuso, tu cosa pensi si debba usare?
L'esercizio dice:

Si realizzi un'implementazione dell'interfaccia Stack<E> (come vista a lezione)
utilizzando esclusivamente istanze della classe Queue<E>.
In seguito si realizzi un programma Java che, utilizzando la nuova classe creata,
prenda in input una sequenza di operazioni di push e pop e restituisca in output la
configurazione finale dello stack così ottenuto.
Input
Il file di input contiene una sequenza di operazioni push e pop, una per riga,
terminanti con il simbolo “ ;” (punto e virgola). Le operazioni di push prendono
come input un numero intero compreso tra 0 e 99.
Output
il file di output contiene due righe. La prima riga indica il numero di
EmptyStackException generate durante l'esecuzione. La seconda riga contiene la
configurazione finale dello stack, dall'elemento in testa fino all'elemento in fondo
allo stack.

L'interfaccia stak è banale, con top e i metodi push(), pop()..eccetera.
Ma lì dice con una coda, quindi come faccio se la coda funziona in quel modo?
Non capisco come può funzionare sia da stack che da queue...
Non posso usare classi precostruite da Java, devo fare tutto da solo purtroppo.

[Darèios89]

Un aiutino??
Per piacere.

[andbin]

Stavo ragionando su questa frase.

Si realizzi un'implementazione dell'interfaccia Stack<E> (come vista a lezione)
utilizzando esclusivamente istanze della classe Queue<E>.

Ma non mi torna affatto .... che senso ha??

L'unica cosa che mi verrebbe in mente di fare che è tecnicamente fattibile è questa: se hai una queue con 5 elementi e vuoi prendere l'ultimo elemento inserito, dalla queue teoricamente/logicamente non potresti. Perché una coda non fa uscire l'ultimo inserito ma il primo. Cosa si potrebbe pensare di fare? Beh, in modo molto contorto estrai i primi 4 elementi e li metti in un'altra nuova queue. Il quinto (l'ultimo insomma) lo estrai e te lo tieni.

Ma scusate se lo dico, mi pare abbastanza cervellotico ... della serie "come usare un cacciavite per piantare un chiodo".

Originariamente inviato da Darèios89
Non posso usare classi precostruite da Java, devo fare tutto da solo purtroppo.

Sì sì ok. Prima parlavo di LinkedList ma solo a titolo di esempio.

[Darèios89]

Ah interessante.......bè..oggi proverò...e ti farò sapere...
Si questi esercizi sono davvero strani, cioè io mi ci metto a farli, capisco che siano fatti per esercitarsi...ma entro i limiti del normale
Non capisco perchè fare cose così contorte.
A dopo.

[Darèios89]

Allora vorrei basarmi sulla tua idea.....più o meno dovrebbe essere così:

http://www.allfreeportal.com/imghost...324615Idea.JPG


La push non dovrebbe darmi problemi perchè la faccio sempre in un senso, la pop invece nell'altro senso che non mi serve.
Allora il fatto è che usando la coda di appoggio dovrei reinserire gli elementi di quest'ultima in quella di partenza su cui sto invocando il metodo, ed è questa cosa che non riesco a fare.
Altrimenti....dato che all'interno del metodo pop creo un'altra coda di appoggio...c'è un modo per fare capire al mio metodo che voglio fare...come una sorta di assegnamento?
Cioè dato che la coda di partenza diventerà come quella di appoggio posso in qualche modo asegnare alla coda su cui sto invocando il metodo, la coda diappoggio?
la parte di codice senza reinserire gli elementi, l'ho fatta così, quella per inserire in una coda di supporto gli elementi.

public E pop() throws EmptyStackException
	{
		if(isEmpty()) throw new EmptyStackException(errori+" errori generati");
		
		Queue<E> appoggio=new Queue<E>();
		while(front.getNext()!=null)
		{
			appoggio.push(front.getElement());
                                      front=front.getNext();

		}
		
			rear=null;

Per il resto...che possibilità ho?

P.S. stavo pensando, forse mi conviene implementare normalmente la queue e la dequeue e poi nel main fare il lavoro sulla coda di supporto?

[andbin]

Originariamente inviato da Darèios89
il fatto è che usando la coda di appoggio dovrei reinserire gli elementi di quest'ultima in quella di partenza su cui sto invocando il metodo

No. La coda che tu chiami di "appoggio" la fai diventare "la coda" del tuo stack, facendo "perdere" il riferimento a quella vecchia semplicemente assegnando al campo di istanza la nuova coda.

[Darèios89]

Ma nel metodo stesso pop?
Cioè nel main posso fare questa cosa o creo all'interno del metodo una nuova coda?

[andbin]

Originariamente inviato da Darèios89
Ma nel metodo stesso pop?
Cioè nel main posso fare questa cosa o creo all'interno del metodo una nuova coda?

Molto abbozzato

public class StackConCoda<E> implements Stack<E> {
    private Queue<E> coda;
    
    ...
    
    public E pop() throws EmptyStackException {
        ...
        Queue<E> appoggio = .....
        
        .....
        
        coda = appoggio;
        
        return ....
    }
    ....
}