Stack and Queue, ¿Por qué?

Question

¿Por qué y cuándo debería usar estructuras de datos de pila o de cola en lugar de matrices/listas? ¿Puedes mostrar un ejemplo de estado que sea mejor si usas stack o queue?

Answer 1

Porque ayudan a administrar sus datos de una manera más particular que las matrices y las listas.

cola es primero en entrar, primero en salir (FIFO)

Pila es el último en entrar, primero en salir (LIFO)

matrices y listas son de acceso aleatorio. Son muy flexibles y también fácilmente corruptibles. SI desea administrar sus datos como FIFO o LIFO, es mejor usar esas colecciones ya implementadas.

Answer 2

Cuando desea aplicar un cierto patrón de uso en su estructura de datos. Significa que cuando estás depurando un problema, no tendrás que preguntarte si alguien insertó aleatoriamente un elemento en el medio de tu lista, estropeando algunas invariantes.

Answer 3

1. utilizar una cola cuando se quiere hacer las cosas en el orden en que se pone en.
2. Utilice una pila cuando se quiere hacer las cosas en el orden inverso de lo que los pone en.
3. Utilice una lista cuando desee extraer algo, independientemente de cuándo los coloque (y cuando no desee que se eliminen automáticamente).

Answer 4

Es una cuestión de intenciones. Las pilas y las colas a menudo se implementan usando matrices y listas, pero la adición y eliminación de elementos se define más estrictamente.

Answer 5

Una pila o cola es una estructura de datos lógica; se implementaría bajo las cubiertas con una estructura física (por ejemplo, lista, matriz, árbol, etc.)

Le invitamos a "lanzar su propio" si lo desea, o aprovechar una abstracción ya implementada.

Answer 6

Además del cumplimiento del uso que otros ya han mencionado, también hay un problema de rendimiento. Cuando desee eliminar algo del comienzo de una matriz o una lista (ArrayList), normalmente tardará O (n) en tiempo, pero para una cola tardará O (1) tiempo. Eso puede marcar una gran diferencia si hay muchos elementos.

Answer 7

La pregunta es ambigua, ya que puede representar el tipo de datos abstractos de una pila o cola utilizando una matriz o estructura de datos vinculada.

La diferencia entre una implementación de lista enlazada de una pila o cola y una implementación de matriz tiene la misma compensación básica que cualquier matriz frente a la estructura de datos dinámica.

Una cola vinculada/vinculada tiene inserciones/eliminaciones flexibles y de alta velocidad con una implementación razonable, pero requiere más almacenamiento que una matriz. Las inserciones/eliminaciones son económicas al final de una matriz hasta que se queda sin espacio; una implementación de matriz de una cola o pila requerirá más trabajo para cambiar el tamaño, ya que necesitaría copiar el original en una estructura más grande (o fallar con un error de desbordamiento).

Answer 8

Las matrices/listas y las pilas/colas no son conceptos mutuamente excluyentes. De hecho, cualquier implementación de pilas o colas que encuentres casi seguro usan matrices o listas debajo del capó.

Las estructuras de matriz y lista proporcionan una descripción de cómo se almacenan los datos, un largo con garantías de la complejidad de las operaciones fundamentales en las estructuras.

Las pilas y las colas proporcionan una descripción de alto nivel de cómo se insertan o eliminan los elementos. FIFO para colas, FILO para pilas.

Por ejemplo. si está implementando una cola de mensajes, usará una cola. Pero la cola misma puede almacenar cada mensaje en una lista. "Empujar" un mensaje que se agrega al principio de la lista, "apareciendo" un mensaje que se toma desde el final de la lista.

Answer 9

La pila y la cola son formas más avanzadas de manejar una colección que la matriz en sí misma, lo que no establece ningún orden en la forma en que se comportan los elementos dentro de la colección.

El Stack (LIFO - Último en entrar primero) y una Cola (FIFO - Primero en entrar primero en salir) establecen y ordenan en que sus elementos se insertan y se quitan de una colección.

Puede utilizar una matriz o una lista vinculada como la estructura de almacenamiento para implementar el patrón de pila o cola. O incluso cree con esas estructuras básicas patrones más complejos como árboles binarios o colas de prioridad, que también podrían traer no solo un orden en la inserción y eliminación de elementos sino también clasificarlos dentro de la colección.

Answer 10

Has estado en una cafetería, ¿verdad? y visto una pila de platos? Cuando se agrega una placa limpia a la pila, se coloca encima. Cuando se retira una placa, se retira de la parte superior. Por lo tanto, se llama Last-In-First-Out (LIFO). Una pila de computadoras es así, excepto que contiene números, y puede hacer una de una matriz o una lista, si lo desea. (Si la pila de placas tiene un resorte debajo, dicen que "empuja" una en la parte superior, y cuando quita una, la "levanta". De ahí provienen esas palabras.)

En la cafetería, ir hacia atrás, donde lavan los platos. Tienen una cinta transportadora donde colocan las placas para lavar en un extremo y salen por el otro extremo, en el mismo orden. Es una cola o Primero en entrar, primero en salir (FIFO). También puede hacer uno de esos de una matriz o una lista si lo desea.

¿Para qué sirven? Bueno, supongamos que tiene una estructura de datos de árbol (que es como un árbol real hecho de madera, excepto que está boca abajo), y desea escribir un programa para recorrerlo completamente, a fin de imprimir todas las hojas.

Una forma es hacer una caminata en profundidad. Empiezas en el maletero y vas a la primera rama, y ​​luego vas a la primera rama de esa rama, y ​​así sucesivamente, hasta que llegas a una hoja e imprimes. Pero, ¿cómo retrocedes para llegar a la siguiente sucursal? Bueno, cada vez que bajas por una rama, "presionas" cierta información en tu pila, y cuando haces una copia de seguridad, la "reventas" de nuevo, y eso te dice qué rama tomar a continuación. Así es como se hace un seguimiento de qué rama hacer a continuación en cada punto.

Otra forma es un paseo en anchura a pie. Comenzando por el tronco, numeras todas las ramas del tronco y colocas esos números en la cola. Luego saca un número del otro extremo, vaya a esa rama, y ​​para cada rama que sale de es, los numera nuevamente (consecutivamente con el primero) y los pone en la cola. A medida que sigas haciendo esto, primero vas a visitar las ramas que están a una rama del tronco. Luego, va a visitar todas las ramas que están a 2 ramas del tronco, y así sucesivamente. Eventualmente llegarás a las hojas y podrás imprimirlas.

Estos son dos conceptos básicos en la programación.

Answer 11

Creo que la pila y la cola son conceptos de acceso a la memoria que se utilizan según la demanda de la aplicación. Por otro lado, la matriz y las listas son dos técnicas de acceso a la memoria y se utilizan para implementar conceptos de pila (LIFO) y cola (FIFO).