Apilar usando una cola

Question

Estaba navegando por algunas preguntas de la entrevista y tropecé con esto. Me hizo destrozar mi cabello.

¿Alguien sabe cómo implementar una pila usando la cola ?.

Answer 1

push: inserte el elemento en la parte posterior de la cola.

pop: quite un elemento de la parte frontal, insértelo inmediatamente en la parte posterior, repita N-1 veces, donde N es el tamaño de la cola, luego elimine el último elemento y devuélvalo.

Answer 2

Versión A:

empuje:

enqueue en cola1

pop:

mientras que el tamaño de cola1 es mayor que 1, la tubería quitadas de artículos de cola1 en cola2 quitar de la cola y el retorno el último elemento de queue1, luego cambie los nombres de queue1 y queue2

Version B:

empuje:

enqueue en cola2 poner en cola todos los artículos de cola1 en cola2, a continuación, cambiar los nombres de cola1 y cola2

pop:

deqeue de cola1

Answer 3

concepto de usar una cola para implementar la pila toma O (2n) o (máquina independiente) O (n) complejidad del espacio. Pero cuando trabajas para una matriz de gran tamaño, el doble de tamaño puede no estar disponible, también la complejidad del tiempo es O (n^2) o precisamente O (n * (n + 1)/2) en caso de que intentes usar solo una cola.