¿Por qué usarías una cola en lugar de una lista vinculada? ¿No es una cola una versión peor de una lista vinculada?

Comunica la intención a las personas que leen el código y hace imposible que los cambios se inserten o eliminen accidentalmente en el extremo equivocado. El tiempo y el dinero gastados en la evolución del software generalmente exceden con creces el gastado en la primera versión, por lo que no desea hacer nada que lo complique innecesariamente.

Como han señalado otras personas, eso también tiene beneficios potenciales de rendimiento. Una cola implementada con una lista vinculada de matrices usa menos ancho de banda de memoria (que a menudo es el límite que se encuentra cuando los programas “se quedan sin CPU”), tiene menos desalojos TLB y tiene menos sobrecarga de memoria que una implementada como una lista vinculada de nodos individuales . Esa optimización no permite la eliminación de elementos fuera de orden de tiempo constante como una simple lista vinculada, aunque eso no es necesario para una cola con objetos eliminados en orden de inserción.

Supongo que quiere decir que una cola es peor que una lista vinculada porque (algunas) las listas vinculadas admiten agregar y eliminar tanto desde el frente como desde la parte posterior de la colección.

Cuando diseña una colección especializada, desea asegurarse de que a las personas que la usan les resulte muy difícil de usar de cualquier otra manera que no sea la prevista: por lo tanto, la restricción de la cola (agregando solo en la parte posterior, quitando solo desde el frente) es deseable característica . Hay muchas aplicaciones (por ejemplo, procesamiento de trabajos, programación, comunicación entre hilos) en las que es muy deseable restringir al productor para que solo pueda agregar a la parte posterior y que el consumidor solo pueda eliminar desde el frente.

Además, una lista vinculada no siempre es la mejor manera de implementar una cola (aunque una lista vinculada garantiza O (1) agregar y quitar operaciones en todos los casos). Sin embargo, muchas veces, una matriz circular proporciona una implementación más eficiente: aunque cuando ocurren las operaciones de cambio de tamaño, agregar o eliminar será O (n) en lugar de O (1), la suma y eliminación amortizadas (promedio) seguirá siendo aproximadamente O (1) ) Además, una estructura de matriz a menudo tiene una mejor localidad de referencia: en una matriz bien implementada, los elementos contenidos a menudo se almacenan en direcciones de memoria contiguas en lugar de dispersarse por todo el lugar, lo que resulta en un mejor rendimiento.

En resumen, cuando diseña una colección especializada (o cualquier objeto), su objetivo es facilitar que sus clientes los usen correctamente y que sea muy difícil que lo usen incorrectamente. Por lo tanto, la inferioridad de la que se queja es una característica, no un error.

La cola es un caso especial de una lista vinculada. Una lista vinculada que se comporta como una cola debe describirse de otra manera como “una lista vinculada que solo permite agregar elementos en su parte frontal y eliminar elementos de su parte posterior”. Cada vez que alguien que lee el código se encuentra con esta lista vinculada especial, debe esforzarse por recordar esta descripción, ya que no todas las listas vinculadas se comportan de manera similar. Inversamente, lea ‘Cola’ y sabrá de inmediato que es diferente y cómo.

Everythingh se trata del diseño. A veces necesita colas para realizar algunos trabajos, como la mayoría de los sistemas operativos. Por ejemplo, el procesador está poniendo en cola todos los trabajos mientras realiza uno a la vez. Por otro lado, algunos mecanismos de búsqueda están utilizando listas vinculadas en sus algoritmos.

Como dije, se trata de algoritmos, y los algoritmos se refieren a los proyectos.

Piénselo desde una perspectiva orientada a objetos.

Un tipo de estructura de datos puede definirse por las operaciones que necesita realizar en él. push / pop para una cola o pila, vs operaciones de lista para una lista vinculada, etc.

Se puede implementar una cola con una lista vinculada debajo del capó. Pero si su programa / solo / necesita hacer la funcionalidad push / pop de una cola, al especificar una cola genérica le permite introducir otras implementaciones que aún cumplen con los requisitos de la cola, pero pueden no cumplir con la interfaz de una lista vinculada.

Por el contrario, si está tratando de utilizar todas esas otras cosas que puede hacer una lista vinculada, de todos modos no está utilizando una cola, y especificar una sería incorrecto. Incluso si parte de su caso de uso es similar, el hecho de que esté haciendo más con él implica que no está utilizando una cola.

Por ejemplo, una implementación de una cola es tener una matriz e indexarla apuntando al siguiente elemento y al último elemento, que funciona de manera circular. Esto tiene una capacidad máxima, pero mientras permanezca dentro de él, el rendimiento de la memoria puede ser mejor que una lista vinculada. La interfaz de cola oculta todas las diferencias de implementación entre la lista vinculada y la matriz circular, y puede elegir cuál crear y cambiar la funcionalidad fácilmente.

La diferencia entre usar una estructura de datos abstractos y una implementación específica puede ser más pronunciada en otros casos de uso, pero el principio general de diseño sigue siendo bueno. Por ejemplo, si quiero una Colección, en lugar de una lista o un conjunto o una lista vinculada, permite que los datos se pasen usando cualquier colección que esté almacenada naturalmente. Si mi objetivo es iterar sobre todo en la colección, ¿a quién le importa si es un conjunto o una lista o un montón?

la cola tiene más que ver con la interfaz y no tiene nada que ver con la implementación. sin embargo, tiene que garantizar el contrato de funcionalidad quince.

entonces, la cola da más abstracción y, por lo tanto, una forma más científica de diseño o análisis.

Hasta ahora, todas las respuestas, aunque técnicamente correctas, pierden por completo el uso de una cola. Veamos el concepto: cola significa una línea de operaciones en orden. Aquí hay una cola clásica:

Ahora, mira la cola. Es una línea ordenada donde la gente recibe servicio en una línea regular (en orden de prioridad mientras se alinearon). Al igual que una lista vinculada, ¿verdad?

Pero, ¿qué pasa si surge una necesidad más urgente? Alguien tiene que cortar la cola antes que los demás para recibir servicio. ¿Puede una lista vinculada acomodar esto fácilmente? ¡No! No sin un código realmente feo.

Entonces, ¿dónde encontrarías colas basadas en prioridades? … Tráfico de comunicaciones en tiempo real. Ejemplo militar: Ordinario, Prioritario, Flash como ejemplos. Así es como funciona:

1. El tráfico ordinario está en la cola en orden de envío y aceptación.
2. El tráfico prioritario salta a la cabecera de la línea (el siguiente mensaje a enviar)
3. El tráfico flash no solo salta al comienzo de la línea, sino que interrumpe todo el tráfico anterior (no Flash) e inmediatamente comienza la transmisión.

Intenta eso con una lista vinculada. Absolutamente no trabajador. Ninguna. Nada!

DESCARGO DE RESPONSABILIDAD: Este es un ejemplo y puede, o no, ser representativo de los sistemas de comunicaciones informáticas existentes en la actualidad. En términos telefónicos, el término Flash-Override se utiliza para eliminar todos los otros enlaces de voz competidores (en sesión) en deferencia a la llamada crítica para que pueda pasar (inmediatamente).

ADVERTENCIA: No se encuentre en un enlace de Autovon en el extranjero que llame a su hogar cuando el General quiera hacer una llamada en los Estados Unidos. (Todo salió bien al final. Después de la llamada, el general llamó al técnico y lo elogió por su rápida respuesta y reparación del circuito “inactivo”. ¿Yo? Tuve que colgar rápidamente con una nota de felices fiestas para mis padres.)

Una cola permite dos operaciones específicas (agregar a la cola, eliminar de la cabeza) y nada más. Al limitar las operaciones que puede hacer en una estructura de datos, es más comprobable porque solo tiene que verificar dos operaciones.

Una cola también proporciona flexibilidad porque puede implementarse utilizando cualquier estructura de datos (generalmente una matriz o lista vinculada). Una lista vinculada solo se puede implementar usando (bueno) una lista vinculada.

Dado que una cola tiene un contrato bien definido, también se prefiere desde el punto de vista de la legibilidad del código. Transmite una intención más clara que el código de lista enlazada equivalente.

Una cola es peor que una lista enlazada en el sentido de que no puede agregar / eliminar desde ningún punto arbitrario en la cola. Si no necesita agregar a ningún punto arbitrario en la cola, entonces este es un punto discutible.

Ninguna cola puede ser mucho más rápida, ya que se puede implementar usando matrices y vectores que son internamente mucho más rápidos que usar una lista vinculada.

La biblioteca estándar de C ++ ofrece estructuras para la lista y la cola y puede ver implementando la lista y la cola que una cola puede ser mucho más rápida que usar una lista vinculada.

No creo que la cola y las listas vinculadas caigan en la misma categoría. El propósito de la cola es garantizar el escenario FIFO (Primero en entrar, primero en salir) que se puede implementar utilizando una lista vinculada o una matriz. Mientras que la lista vinculada es una lista que contiene un enlace a otro elemento de la lista.