PUERTA | PUERTA-CS-2001 | Pregunta 41

¿Cuál es el número mínimo de pilas de tamaño n necesarias para implementar una cola de tamaño n?
(A) Uno
(B) Dos
(C) Tres
(D) Cuatro

Respuesta: (B)
Explicación: Se puede implementar una cola usando dos pilas. Deje que la cola que se implementará sea q y las pilas utilizadas para implementar q sean stack1 y stack2. q se puede implementar de dos maneras:

Método 1 (Al hacer que la operación enQueue sea costosa)
Este método se asegura de que el elemento recién ingresado esté siempre en la parte superior de la pila 1, de modo que la operación de deQueue simplemente salte de la pila 1. Para poner el elemento en la parte superior de stack1, se usa stack2.

enQueue(q, x)
  1) While stack1 is not empty, push everything from satck1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.

dnQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it

Método 2 (Al hacer que la operación de eliminación de cola sea costosa)
En este método, en la operación en cola, el nuevo elemento se ingresa en la parte superior de la pila 1. En la operación de eliminación de cola, si la pila 2 está vacía, todos los elementos se mueven a la pila 2 y finalmente se devuelve la parte superior de la pila 2.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
  1) If both stacks are empty then error.
  2) If stack2 is empty
       While stack1 is not empty, push everything from satck1 to stack2.
  3) Pop the element from stack2 and return it.

Fuente: https://www.geeksforgeeks.org/queue-using-stacks/
Cuestionario de esta pregunta