Ho la seguente domanda a casa:
Implement the stack methods push(x) and pop() using two queues.
Mi sembra strano perché:
- Una pila è una coda (LIFO)
- Non vedo perché ti occorrono due code per implementarlo
Ho cercato in giro:
e trovato un paio di soluzioni. Questo è quello che ho finito con:
public class Stack<T> {
LinkedList<T> q1 = new LinkedList<T>();
LinkedList<T> q2 = new LinkedList<T>();
public void push(T t) {
q1.addFirst(t);
}
public T pop() {
if (q1.isEmpty()) {
throw new RuntimeException(
"Can't pop from an empty stack!");
}
while(q1.size() > 1) {
q2.addFirst( q1.removeLast() );
}
T popped = q1.pop();
LinkedList<T> tempQ = q1;
q1 = q2;
q2 = tempQ;
return popped;
}
}
Ma non capisco quale sia il vantaggio rispetto all'utilizzo di una singola coda; la versione in due code sembra inutilmente complicata.
Diciamo che per i push è il più efficiente del 2 (come ho fatto sopra), push sarebbe rimasto lo stesso, e pop avrebbe semplicemente bisogno di iterare fino all'ultimo elemento e di restituirlo. In entrambi i casi, push sarebbe O(1) e pop sarebbe O(n) ; ma la versione a coda singola sarebbe drasticamente più semplice. Dovrebbe richiedere solo un ciclo for.
Mi manca qualcosa? Qualsiasi comprensione qui sarà apprezzata.