Crear una cola FIFO en C

Question

¿Es posible crear una 'pila' FIFO en C sin usar 2 pilas?

Gracias!

(Lo siento por aquellos que respondieron a la anterior. Yo estaba pensando LIFO y FIFO significa.)

Answer 1

Es muy fácil. Simplemente implemente una lista doblemente enlazada, sosteniendo el puntero al último elemento de la lista.

Para agregar a la cola, cree un nuevo nodo al principio, vinculándolo al comienzo anterior. (inserción de lista normal)

Para eliminar de la cola, deslice el puntero hasta el último elemento, cambie el puntero al puntero del elemento anterior y devuelva el último elemento ... (Esta es la razón por la que la lista está doblemente vinculada La otra opción es una lista de enlace único e iteración de toda la lista para obtener punteros a los dos últimos elementos).

Answer 2

Usar 2 pilas para esto es una solución divertida y lenta. ¿Por qué mencionas stack cuando puedes usar una cola común? Es FIFO lo que quieres, ¿verdad? Puede usar una matriz para hacer una cola, modulando su longitud para hacerla circular.

Answer 3

Parece que está intentando hacer una cola, donde inserta en un extremo y tira del otro.

Una forma de hacerlo es con una lista vinculada. Puede almacenar punteros en la cabeza y la cola. Cuando inserte, agregue el nuevo registro a la cola y cuando saque algo de la cola, tome el nodo al que apunta el puntero de la cabeza. (O viceversa, no importa mucho)

Answer 4

¿No sería solo una lista vinculada estándar, excepto que solo define funciones para extraer el elemento principal y empujar cosas hacia el elemento cola? Incluso podría hacer esto en una lista individualmente vinculada con un puntero de cola, en lugar de una lista completamente doblemente vinculada.

Answer 5

También puede implementar una cola con circular array.

Answer 6

Creo que OP deseaba saber cómo manejarlo si todo lo que tiene son montones, por la razón que sea. El truco es recordar que empujar cosas en una pila y luego abrirlas invierte el orden de los elementos, por lo que puedes usar dos pilas para invertirlo dos veces.

Los elementos entrantes se insertan en la pila 1, y se eliminan en stack2 cuando la pila2 está vacía. Por lo tanto, el primer elemento se coloca en la pila 1, se quita inmediatamente y se coloca en la pila 2, listo para la salida. Los elementos subsiguientes se acumulan en la pila 1 hasta que la pila 2 aparece, en cuyo punto el último elemento va a la pila 2, luego a la penúltima, y ​​así sucesivamente hasta que la pila 1 esté vacía nuevamente. Ahora todos los elementos se vuelven a apilar en stack2, con el más nuevo en la parte inferior y el más antiguo en la parte superior. Las nuevas pulsaciones continúan acumulándose en stack1, esperando que stack2 se vacíe nuevamente, y stack2 solo produce los elementos en el orden original hasta que estén vacíos, momento en el que repetimos el proceso de apilar y volver a apilar.

No haré comentarios acerca de la eficiencia, etc .; es solo "podrías hacerlo de esa manera". Me lo preguntaron en una entrevista y mi respuesta inmediata fue "¿Qué tipo de idiota haría ? Solo implemente una cola real y termine con eso". No creo que esa fuera la respuesta que estaban buscando.

Answer 7

Aunque ya se han propuesto soluciones correctas, me gustaría corregir que FIFO no sea realmente una pila.

Esa pregunta se encuentra a menudo en la clase de Algoritmos, donde le piden que construya una utilizando stacks y compruebe que el costo amortizado para la inserción y eliminación es O (1).

FIFO pueden ser construidos utilizando la lista doblemente enlazada, una matriz/vector con un puntero comenzar y terminar, con matrices circulares, etc, etc ...