data-structures - prioridad - pilas y colas en java

Pila y cola, ¿por qué? (11)

Usa una cola cuando quieras sacar cosas en el orden en que las pones.
Usa una pila cuando quieras sacar cosas en el orden inverso al que las colocaste.
Use una lista cuando desee sacar algo, independientemente de cuándo los coloque (y cuando no desee que se eliminen automáticamente).

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

Además de la aplicación de 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.

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).

Cuando desee 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.

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.

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 "empujas" una en la parte superior, y cuando la quitas, la "reventas". De ahí provienen esas palabras).

En la cafetería, ve 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é son buenos? 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 de profundidad primero . 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 una caminata amplia . 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 por cada rama que salga de ella , los numera nuevamente (consecutivamente con la primera) y los coloca 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 muy básicos en programación.

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.

La pila (LIFO - Último en entrar primero en salir) y una Cola (FIFO - Primero en entrar primero en salir) establecen y ordenan en que sus elementos son insertados y eliminados de una colección.

Puede utilizar una matriz o una lista vinculada como la estructura de almacenamiento para implementar el patrón 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.

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ámicos.

Una cola / pila enlazada enlazada 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).

Las matrices / listas y stacks / 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, una larga 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.

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)

La pila es la última en entrar, la primera en salir (LIFO)

Las matrices y las 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.

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 el suyo" si lo desea, o aprovechar una abstracción ya implementada.