[JAVA] Invertire una coda (queue)

[rubikk]

Ciao a tutti, vi chiedo aiuto per tentare di capire dove sbaglio (per parafrasare una famosa canzone, la programmazione non sarà mai il mio mestiere ).

Premettendo che sto studiando Strutture Dati per un corso universitario, tra gli esercizi relativi alla queue c'è questo:
Scrivere la funzione

public static <E> void reverse(Queue<E> Q)

che inverte il contenuto della coda Q.

Ricordo che queue rappresenta una coda di tipo FIFO, in cui gli inserimenti avvengono in coda e le cancellazioni in testa, e che le operazioni consentite sono enqueue (inserimento in coda) e dequeue (estrazione dalla testa).

Problema: come ottengo l'inversione della coda? Avevo pensato a una cosa del genere:

public Queue<E> reverseQueue(Queue<E> coda) {
queue1 = new ArrayQueue<E>(capacity);
queue1 = (ArrayQueue<E>) coda; 
while (!queue1.isEmpty()) 	
queue2.enqueue(queue1.dequeue());
return queue2;}

ma la logica suggerisce che togliendo dal fondo e reinserendo in testa ottengo, alla fine, di nuovo la situazione di partenza. Qualche idea in proposito?

Lo step successivo invece sarebbe di fare la stessa operazione usando un metodo ricorsivo... e se qualcuno avesse consigli anche per questo sarebbe cosa graditissima!

[unomichisiada]

Originariamente inviato da rubikk
Ciao a tutti, vi chiedo aiuto per tentare di capire dove sbaglio (per parafrasare una famosa canzone, la programmazione non sarà mai il mio mestiere ).

Premettendo che sto studiando Strutture Dati per un corso universitario, tra gli esercizi relativi alla queue c'è questo:
Scrivere la funzione

public static <E> void reverse(Queue<E> Q)

che inverte il contenuto della coda Q.

Ricordo che queue rappresenta una coda di tipo FIFO, in cui gli inserimenti avvengono in coda e le cancellazioni in testa, e che le operazioni consentite sono enqueue (inserimento in coda) e dequeue (estrazione dalla testa).

Problema: come ottengo l'inversione della coda? Avevo pensato a una cosa del genere:

public Queue<E> reverseQueue(Queue<E> coda) {
queue1 = new ArrayQueue<E>(capacity);
queue1 = (ArrayQueue<E>) coda; 
while (!queue1.isEmpty()) 	
queue2.enqueue(queue1.dequeue());
return queue2;}

ma la logica suggerisce che togliendo dal fondo e reinserendo in testa ottengo, alla fine, di nuovo la situazione di partenza. Qualche idea in proposito?

Lo step successivo invece sarebbe di fare la stessa operazione usando un metodo ricorsivo... e se qualcuno avesse consigli anche per questo sarebbe cosa graditissima!

Per ottenere un'inversione degli elementi puoi usare uno stack, anzi direi che è l'unico modo che mi viene in mente.
Facendolo con una funzione ricorsiva non hai bisogno dello stack (perché usi quello di sistema).

[unomichisiada]

Ti do una dritta sulla versione non ricorsiva e l'altra te la fai da solo tenendo presente ciò che ti ho detto sullo stack di sistema.

public Queue<E> reverseQueue(Queue<E> coda) {
Stack<E> stack = new Stack<E>();
while (!coda.isEmpty()) 	
    stack.push(coda.dequeue());
while (!stack.isEmpty()) 	
    coda.enqueue(stack.pop());
return coda;
}

Il codice non è testato ma l'idea di base si capisce

[rubikk]

Ti ringrazio, effettivamente anche io non sono riuscito ad immaginare una maniera per fare la stessa cosa senza utilizzare una struttura diversa dalla coda, e a ben pensarci l'esercizio non prevede limitazioni da questo punto di vista. Eppure mi ero fissato sull'idea di farlo senza utilizzare strutture dati "esterne" con la frustrazione di svariati tentativi inutili

Grazie ancora davvero!