¿alguien puede explicarme cómo implementar múltiples colas en una pila?
// implement stacks using plain arrays with push and pop functions var Stack1 = []; var Stack2 = []; // implement enqueue method by using only stacks // and the push and pop functions function Enqueue(element) { Stack1.push(element); } // implement dequeue method by pushing all elements // from stack 1 into stack 2, which reverses the order // and then popping from stack 2 function Dequeue() { if (Stack2.length === 0) { if (Stack1.length === 0) { return 'Cannot dequeue because queue is empty'; } while (Stack1.length > 0) { var p = Stack1.pop(); Stack2.push(p); } } return Stack2.pop(); } Enqueue('a'); Enqueue('b'); Enqueue('c'); Dequeue();Utiliza dos pilas, una para el frente de la cola y otra para el final de la cola. La pila frontal se ordena de manera que el primer elemento que se va a quitar de la cola esté en la parte superior, el segundo después, y así sucesivamente. La pila posterior se ordena de manera que el último elemento que puso en cola esté en la parte superior, el anterior a continuación, y así sucesivamente.
Cuando necesite poner en cola un elemento, simplemente empújelo a la pila posterior.
Cuando necesite sacar un elemento de la cola y la pila frontal no esté vacía, extraiga el primer elemento.
El problema surge cuando necesita sacar un elemento de la cola y la pila frontal está vacía. Luego tienes que mover todos los elementos de atrás hacia adelante. Los abres desde atrás y los empujas hacia adelante, uno a la vez.
Este procedimiento invierte el orden de los elementos en la cola posterior. Un elemento que sacas desde atrás se empuja sobre los elementos que están al frente. Entonces, después de esto, la pila frontal se ordena de la manera que requiere el invariante.
Los primeros dos casos son obviamente tiempo constante (con cualquier implementación razonable de una pila). El tercero es más caro, porque potencialmente implica muchas copias. Sin embargo, podemos argumentar a favor de un tiempo constante amortizado. Cada elemento se mueve de atrás hacia adelante solo una vez, así que ponga una moneda en el banco de amortización cada vez que ponga en cola un elemento, entonces puede pagar por mover el elemento al frente.