¿Cuáles son algunos ejemplos buenos y simples para colas? [cerrado]

9

Estoy enseñando CS2 ( Java and data structures), y tengo algunas dificultades para encontrar buenos ejemplos para usar cuando enseño colas. Las dos aplicaciones principales para las que los uso son la multithreadedtransmisión de mensajes (pero la programación MT está fuera del alcance del curso) y BFS-style algorithms(y no cubriré gráficos hasta más adelante en el término).

También quiero evitar ejemplos artificiales. La mayoría de las cosas en las que pienso, si realmente las resolviera de una sola hebra, usaría una lista en lugar de una cola. Tiendo a usar solo colas cuando el procesamiento y el descubrimiento están intercalados (por ejemplo, búsqueda), o en otros casos especiales, como los búferes de longitud limitada (por ejemplo, el mantenimiento de los últimos N elementos). En la medida de lo posible, estoy tratando de enseñarles a mis estudiantes buenas maneras de hacer cosas en programas reales, no solo juguetes para mostrar una característica.

¿Alguna sugerencia de algoritmos buenos o simples o aplicaciones de colas que pueda usar como ejemplos pero que requieran un mínimo de otro conocimiento previo?

Michael Ekstrand
fuente
+1, pero me abstendría de crear la etiqueta 'cola', considerando que solo contiene su pregunta. Hubiera usado 'estructuras de datos'.
K.Steff
@ K.Steff, puede tener ambas :-) Tenga en cuenta que cualquier etiqueta nueva está asociada con una sola pregunta al principio.
Péter Török
1
Es natural cubrir las colas cuando cubre BFS. ¿Por qué no guardar colas hasta entonces? No tiene que cubrir Colas con listas vinculadas y listas de matrices solo porque también tienen una representación lineal.
Kevin Cline
@ PéterTörök Me doy cuenta de que todas las etiquetas comienzan vacías, pero una búsqueda 'en cola' genera 313 preguntas, y ninguna otra ha creado la etiqueta 'en cola'. Esto es solo IMO, de todos modos
K.Steff
Un tema recurrente en las respuestas parece ser simulaciones de colas del mundo real. Hasta ahora he pensado que preferiría usar ejemplos de cosas en las que usaría una cola para resolver un problema que realmente surge en la programación, y que muchos de los ejemplos del mundo físico brillan mejor en entornos concurrentes. Sin embargo, dada la repetición de este tema, bien podría ser que no estoy en una línea de pensamiento útil. ¡Sigue enviando sugerencias! Y gracias a todos por su gran ayuda.
Michael Ekstrand

Respuestas:

14

Cuando estaba aprendiendo colas, mi profesor siempre usaba el ejemplo de una tienda. Hay 1 o más registros abiertos en un momento dado, y los Clientes ingresan a una cola u otra y se mueven a través de esa cola para comprar todos sus artículos.

De hecho, tuvimos que implementar un programa simple que pudiera mover a los Clientes a través de RegisterQueue, por lo que si realmente está buscando un programa, puede darles a los estudiantes este ejemplo, es simple y directo, pero también es algo que cada estudiante ha visto en la vida real. puede ayudarlos a comprender mejor el concepto.

Mike Caputo
fuente
Como dije, este ejemplo es muy intuitivo y también se usa con demasiada frecuencia;)
marktani
1
Puede agregar complejidad al tener una cola prioritaria para clientes con beneficios (plan Aero).
sixtyfootersdude
1
En mi opinión, los ejemplos más fáciles son los que encontramos en la vida. Un ejemplo de "línea" es una gran representación de una cola y debería ayudar a sus alumnos a aprender. De hecho, cuando pienso en las colas y en cómo se definen sus operaciones, a menudo pienso en el ejemplo de 'línea' para ayudarme a visualizarlo mejor.
Nicholas
Esta también es una gran oportunidad para tocar brevemente la teoría de colas: por qué una sola línea que sirve múltiples registros es mejor que una línea por registro. Permítales construir una simulación y jugar con ella. The Engineer Guy tiene una gran explicación simple: engineerguy.com/videos/video-lines.htm
jpeacock
5

Cuando aprendí las colas, mi maestra me las presentó usando una línea para autos en un control policial. Había una cola que contenía los carros ("cola de espera") y el policía siempre controlaba el próximo carro en la cola y lo enviaba a su colega para inspecciones adicionales o dejaba pasar el carro.

Un ejemplo muy utilizado es la cola en el supermercado ...

¿Por qué no les pides a tus alumnos que den algunos ejemplos ellos mismos?

Marktani
fuente
+1 por ejemplo de supermercado. ¡Lo mencionaste mientras escribía mi respuesta!
Mike Caputo
3

Un ejemplo que me viene a la mente es una línea de procesamiento de hamburguesas en, por ejemplo, McDonalds. Hay varios tipos de hamburguesas diferentes, cada una puede ser producida por varios trabajadores diferentes y cada una tiene su propia cola. A partir de ahí, después de un tiempo, una de las cajeras que ordenó ese tipo de hamburguesas toma las hamburguesas listas, en orden FIFO.

Por lo tanto, hay múltiples productores y consumidores, y cada cola está limitada.

Péter Török
fuente
Recuerdo a los compañeros de clase en la universidad comparando los diferentes estilos de arreglos de registro de comida rápida con diseños de procesadores. ¿Una cola manejada por múltiples registros? Cada registro con su propia cola? Múltiples trabajadores en la misma línea: procesamiento súper escalar. Fue divertido
3

Pensé en usar Amazon como ejemplo, en algún lugar de su sistema masivo debe haber una cola de pedidos que deben manejarse. que podría manejarse con una simple cola y cola. el sistema pondría en cola un pedido en el sistema cada vez que un cliente comprara un libro, y una persona de la bodega lo retiraría para recogerlo y publicarlo.

Entonces sería fácil comenzar a hablar sobre colas prioritarias, al introducir clientes principales, que podrían saltar la cola, podría introducir colas prioritarias.

¿Qué libro de texto estás usando?

Kim.Net
fuente
Carrano - Estructuras de datos y abstracción con Java .
Michael Ekstrand
2

Un ejemplo perfecto de una cola sería un banco procesando transacciones contra una cuenta. Por lo general, verá una lista de transacciones "pendientes" al final del día. Cuando se realiza la contabilidad, esas transacciones se aplican a la cuenta. Incluso podría entrar en el área de colas prioritarias con esto. Parece que la mayoría de los bancos dan prioridad a los débitos cuando procesan las transacciones nocturnas para que puedan pagar más de los honorarios de giro antes de aplicar cualquier crédito pendiente.

Las transacciones se insertan en la cola por orden de tiempo ejecutado y retirado y aplicado a la cuenta por el proceso contable.

Michael Brown
fuente
2

Solía ​​ser un programador de telecomunicaciones, así que esto me viene a la mente:

Una línea directa de servicio al cliente. Entra una llamada, no hay suficientes operadores para manejar la llamada y se coloca en una cola. Entra la siguiente llamada y también se coloca en la cola. Luego, cuando el siguiente operador está disponible, la primera llamada que ingresó en la cola se asigna al operador disponible.

programador
fuente
2

Los ejemplos obvios del mundo real serían cosas como líneas de pago, etc., pero dado que está buscando un ejemplo basado estrictamente en informática, ¿podría sugerir colas de programación de trabajos ?

No sé cuántos de sus estudiantes han tomado una clase de Sistemas Operativos, pero es una buena apuesta que todos hayan usado el Administrador de tareas para verificar sus procesos en algún momento u otro. Podría presentar un ejemplo simplificado de una cola de programación y asignarles algo de tarea para escribir un programa que genere (o acepte) una "tarea" de un tamaño determinado y los procese en orden FIFO cuando la "inicien".

Es un concepto bastante fácil de entender, demuestra la idea de que la cola opera en su contenido en el orden en que los acepta y les brinda una introducción (muy rudimentaria y simplificada) a la programación de la CPU. Solo mis dos bits.

Puede presentar su aplicación en subprocesos múltiples, pero a menos que los estudiantes ya hayan tenido alguna experiencia escribiendo programas de subprocesos, no les asignaría un trabajo que podría ser frustrante. Recuerdo que tuve problemas para aprender las estructuras de datos (especialmente en Java, no haber hecho C ++ y no haber aprendido nada sobre los punteros) en mi segundo año de universidad, por lo que un ejemplo simple pero práctico relacionado directamente con la informática es probablemente el mejor.

KChaloux
fuente
1

Mundo real:

  • Cada vez que la gente hace cola: cajero en la tienda de comestibles, en el restaurante esperando una mesa (puedes trabajar en esos buscapersonas que a veces dan en la analogía), etc. Es útil cuando notas que en el Reino Unido a menudo llamar a estas colas en lugar de líneas (común en NA)
  • Serie de libros de lectura ', author.publish => queue.push y student.read => queue.pop

Mundo no real:

  • Procesar los datos enviados en un entorno de subproceso único en el que el procesamiento lleva más tiempo que el envío (operaciones de pago para tiendas en línea, por ejemplo).
  • Cualquier colección FIFO que se pueda iterar puede usar colas y usar en while(queue.peek)lugar de un iterador.
Steven Evers
fuente
1

Me gusta usar los juegos como ejemplo porque generalmente es un poco más emocionante que el archivo IO o cualquier otra cosa que se te ocurra.

Entonces, cuando quieras emitir varios comandos seguidos a una unidad en un juego de estrategia (por ejemplo, tener un Zergling para explorar 4 esquinas de una base en orden, luego suicidarse en el centro de la base, una cola sería una buena opción .)

O tal vez tiene una aplicación que solo puede procesar 30 cuadros por segundo, pero puede obtener 4 o 5 entradas entre cuadros. Si tiene una entrada de cambio de arma y una entrada de disparar, desea asegurarse de que se manejen en el orden en que fueron recibidas; de lo contrario, puede granadas cuando desee un cuchillo. Y si granadas cuando quieres un cuchillo, lo vas a pasar mal. (pon eso en el meme del instructor de esquí y tíralo en tus toboganes) :)

Un servidor que maneja solicitudes es otra buena.

Una máquina CNC que toma la entrada. La máquina solo puede ir tan rápido, por lo que necesita poner en cola la entrada.

Justin
fuente
1

Algunos ejemplos que se me ocurren:

  • Calculadora: puede introducir prefijo y postfijo al mismo tiempo
  • Instrucciones para atar los zapatos. No se puede completar la siguiente operación hasta que haya realizado la última.
  • Buffers: tal vez un buffer telefónico utilizado para almacenar números que el usuario ha ingresado pero que aún no ha emitido el sonido.
  • Digestión
Sixtyfootersdude
fuente
1

Las líneas de fabricación están llenas de colas. Piense en una línea de botellas vacías que se dirigen a una máquina llenadora. Primero en entrar, primero en salir es una forma natural de aplicar un proceso secuencialmente a muchos objetos. Las colas también se utilizan para desacoplar un proceso de otro: la máquina de llenado no tiene que detenerse inmediatamente si hay un problema a corto plazo con la máquina de etiquetado.

Las colas se usan en el software de la misma manera. La salida de un proceso se puede poner en cola para ingresar a otro proceso. Esto es cierto ya sea que esté hablando de comunicación entre procesos, comunicación entre hilos o simplemente dividiendo un proceso complicado en partes que podrían ser manejadas por el mismo hilo.

En los sistemas operativos, las colas a menudo se utilizan para procesar entradas en orden. El sistema de archivos puede leer bloques de un dispositivo de almacenamiento y agregarlos a una cola, por ejemplo. O las interrupciones que manejan cosas como presionar teclas y movimientos del mouse crean eventos que se agregan a una cola de eventos para que no obtenga "uqeeu" en lugar de "cola" cuando está escribiendo.

Para una simple tarea de estudiante, creo que cualquier tarea que acepte una cantidad de entradas y luego las procese funcionaría. Por ejemplo, puede hacer que escriban un evaluador de expresión de postfix simple. Tendría tres partes:

  • leer una entrada, agregarla a la cola de entrada y repetir hasta que no haya más entradas

  • obtener un artículo de la cola

    • Si el elemento es un número, introdúzcalo en la pila de argumentos.
    • Si el elemento es un operador, haga estallar los argumentos necesarios y evalúe
    • agregar el resultado a la cola de salida
    • repite hasta que la pila esté vacía
  • lea un elemento de la cola de salida, imprímalo y repita hasta que la cola de salida esté vacía

Caleb
fuente
1

Al enseñar estructuras de datos, generalmente uso la aplicación de la simulación de colas bancarias donde los clientes esperan en una cola y hay una serie de ventanas de servicio.

El problema es simular el proceso para encontrar estadísticas de lo siguiente: el tiempo de espera de los clientes en la cola (máximo, mínimo, promedio) y el número de clientes que esperan en la cola. Utilizo una frecuencia predefinida de llegada de nuevos clientes cada minuto de un día y un tiempo de servicio promedio de un cliente en la ventana de servicio con valores del generador de números aleatorios.

El resultado serán recomendaciones para la cantidad óptima de ventanas de servicio y la cantidad óptima de sillas en la sala de espera que garantizarían la satisfacción del cliente. Aplicación muy interesante para estudiantes.

Malik Elamaireh
fuente
1

Cualquier algoritmo de programación casi siempre implica una cola.

Esto puede variar desde una simple cola de orden de llegada hasta una solicitud de almacenamiento intermedio para un solo consumidor.

Para una cola de programación de trabajo compleja donde las "tareas" pueden tener prioridades y los "trabajadores" tienen capacidades diferentes.

Un buen caso de uso para jugar podría ser: "Tiene un servidor de impresión central con cuatro impresoras conectadas, dos con capacidad de color, una con capacidad para imprimir a doble cara y otra para imprimir en papel más grande. Los usuarios pueden pagar más por un trabajo urgente, o menos si no les importa esperar más. Puede incurrir en multas si entrega tarde, por lo que desea obtener el mayor rendimiento posible ".

James Anderson
fuente