Какие хорошие, простые примеры для очередей? [закрыто]

9

Я преподаю CS2 ( Java and data structures), и мне трудно найти хорошие примеры для обучения в очередях. Двумя основными приложениями, для которых я их использую, является multithreadedпередача сообщений (но программирование на МТ выходит за рамки курса) и BFS-style algorithms(и я не буду охватывать графики до тех пор, пока не буду в терминах).

Я также хочу избежать надуманных примеров. Большинство вещей, о которых я думаю, если бы я действительно решил их однопоточным способом, я бы просто использовал список, а не очередь. Я склонен использовать очереди только тогда, когда обработка и обнаружение чередуются (например, поиск) или в других особых случаях, таких как буферы с ограниченной длиной (например, поддержание последних N элементов). Насколько это возможно, я пытаюсь научить своих учеников хорошим способам делать что-то в реальных программах, а не просто игрушкам, чтобы показать какую-то особенность.

Любые предложения хороших, простых алгоритмов или приложений очередей, которые я могу использовать в качестве примеров, но которые требуют минимум других предварительных знаний?

Майкл Экстранд
источник
+1, но я бы воздержался от создания тега «очередь», учитывая, что он содержит только ваш вопрос. Я бы использовал «структуры данных».
К.Стефф
@ K.Steff, вы можете иметь оба :-) Обратите внимание, что любой новый тег связан с только одним вопросом в начале.
Петер Тёрёк
1
Естественно покрывать очереди, когда вы покрываете BFS. Почему бы не сохранить очереди до тех пор? Вам не нужно покрывать очереди связанными списками и списками массивов только потому, что они также имеют линейное представление.
Кевин Клайн
@ PéterTörök Я понимаю, что все теги начинаются пустыми, но поиск «очереди» дает 313 вопросов, и никто другой не создал тег «очереди». Во всяком случае, это всего лишь ИМО
Стефф
Похоже, что повторяющаяся тема в ответах - моделирование очередей в реальном мире. До сих пор я думал, что предпочитаю использовать примеры вещей, в которых я бы использовал очередь для решения проблемы, которая действительно возникает в программировании, и что многие примеры из физического мира лучше всего отражаются в параллельных средах. Однако, учитывая повторение этой темы, вполне может быть, что я не нахожусь на полезном пути мышления. Следите за предложениями! И спасибо всем за вашу большую помощь.
Майкл Экстранд

Ответы:

14

Когда я изучал очереди, мой профессор всегда использовал пример магазина. В любой момент времени открыто 1 или более регистров, и клиенты входят в ту или иную очередь и перемещаются по этой очереди, чтобы приобрести все свои товары.

На самом деле нам пришлось реализовать простую программу, которая могла бы перемещать Клиентов через RegisterQueue, поэтому, если вы действительно ищете программу, вы можете дать студентам этот пример, простой и понятный, но также то, что каждый студент видел в реальной жизни, и так это может помочь им лучше понять концепцию.

Майк Капуто
источник
Как я уже сказал, этот пример очень интуитивен и также почти слишком часто используется;)
marktani
1
Вы можете добавить сложности, имея приоритетную очередь для клиентов с привилегиями (план Aero).
sixtyfootersdude
1
ИМО, самые простые примеры - это те, с которыми мы сталкиваемся в жизни. Пример «строки» - отличное представление очереди и должен помочь вашим студентам учиться. Фактически, когда я думаю об очередях и о том, как определяются их операции, я часто думаю о «строчном» примере, чтобы помочь мне лучше его визуализировать.
Николас
Это также отличная возможность кратко коснуться теории организации очередей: почему одна строка, обслуживающая несколько регистров, лучше, чем строка на регистр. Позвольте им построить симуляцию и поиграть с ней. У парня-инженера отличное простое объяснение: engineerguy.com/videos/video-lines.htm
jpeacock
5

Когда я узнал об очередях, мой учитель представил их мне, используя очередь для автомобилей у полицейского управления. Была очередь с машинами («очередь ожидания»), и полицейский всегда контролировал следующую машину в очереди и либо отправлял ее своему коллеге для дальнейших проверок, либо пропускал машину.

Очень часто используемый пример - очередь в супермаркете ...

Почему бы вам не попросить своих учеников привести несколько примеров самим?

marktani
источник
+1 за пример супермаркета. Вы упомянули об этом, когда я писал свой ответ!
Майк Капуто
3

Один пример, который мне приходит в голову, - это линия обработки гамбургеров, например, в McDonalds. Существует несколько видов разных бургеров, каждый из которых может быть изготовлен несколькими разными работниками, и у каждого своя очередь. Оттуда через некоторое время готовые гамбургеры, в порядке FIFO, забирает один из кассиров, который заказал такой гамбургер.

Таким образом, есть несколько производителей и потребителей, и каждая очередь ограничена.

Петер Тёрёк
источник
Я вспоминаю, как одноклассники в колледже сравнивали разные стили регистра фаст-фуда с процессорами. Одна очередь обрабатывается несколькими регистрами? Каждый регистр со своей очередью? Несколько рабочих на одной линии - супер скалярная обработка. Это было забавно.
3

Я подумал об использовании Amazon в качестве примера, где-то в их огромной системе должна быть очередь заказов, которую нужно обработать. который мог быть обработан простым enqueue и dequeue. система будет ставить в очередь заказ в системе каждый раз, когда клиент покупает книгу, а работник склада затем снимает ее с очереди, чтобы забрать и опубликовать.

Тогда было бы легко начать говорить о приоритетных очередях, представив основных клиентов, которые могут перейти в очередь, вы могли бы ввести приоритетные очереди.

Какой учебник вы используете?

Kim.Net
источник
Carrano - Структуры данных и абстракция с Java .
Майкл Экстранд
2

Прекрасным примером очереди будет банк, обрабатывающий транзакции по счету. Обычно вы увидите список «ожидающих» транзакций в конце дня. Когда учет завершен, эти транзакции применяются к учетной записи. С этим можно даже попасть в область приоритетных очередей. Похоже, что большинство банков при обработке ночных транзакций отдают предпочтение дебетам, поэтому они могут избежать чрезмерных комиссий, прежде чем применять какие-либо ожидающие кредиты.

Транзакции вставляются в очередь по порядку времени, выполняются и удаляются из очереди и применяются к счету в процессе учета.

Майкл Браун
источник
2

Раньше я работал программистом в области телекоммуникаций, так что это приходит на ум:

Горячая линия обслуживания клиентов. Принимается вызов, недостаточно операторов для обработки вызова, и он помещается в очередь. Приходит следующий вызов, и он также помещается в очередь. Затем, когда следующий оператор становится доступным, первый вызов, поступивший в очередь, назначается доступному оператору.

программист
источник
2

Очевидными примерами из реального мира могут быть такие вещи, как строки оформления заказа и тому подобное, но поскольку вы ищете пример, основанный исключительно на вычислениях, могу ли я предложить очереди для планирования заданий?

Я не знаю, сколько ваших учеников посещали занятия по операционным системам, но стоит поспорить, что все они использовали диспетчер задач для проверки своих процессов в тот или иной момент. Вы можете представить упрощенный пример очереди планирования и назначить им некоторую домашнюю работу, чтобы написать программу, которая генерирует (или принимает) «задачу» заданного размера и обрабатывает их в порядке FIFO, когда они «запускают» ее.

Это довольно простая для понимания концепция, демонстрирующая идею, что очередь работает с ее содержимым в том порядке, в котором она их принимает, и дает им (очень элементарное и упрощенное) введение в планирование ЦП. Просто мои два бита.

Вы можете использовать их в многопоточности, но если у студентов уже не было опыта написания многопоточных программ, я бы не назначил им работу, которая может разочаровать двух человек. Я помню, что у меня были проблемы с изучением структур данных (особенно в Java, когда я не изучал C ++ и не разбирался в указателях) на втором курсе колледжа, так что простой, но практический пример, непосредственно связанный с вычислениями, вероятно, является лучшим.

KChaloux
источник
1

Реальный мир:

  • Каждый раз, когда люди выстраиваются в очередь: кассир в продуктовом магазине, в ресторане в ожидании стола (вы можете работать на тех звуковых сигналах, которые они иногда выдают в аналогии), и т. Д. Это полезно, когда вы замечаете, что в Великобритании они часто вызывать эти очереди вместо строк (обычно в NA)
  • Чтение серии книг », author.publish => queue.push и student.read => queue.pop

Нереальный мир:

  • Обработка любых отправленных данных в однопоточной среде, где обработка занимает больше времени, чем отправка (например, операции проверки для интернет-магазинов).
  • Любая коллекция FIFO, которая может быть повторена, может использовать очереди и использовать while(queue.peek)вместо итератора.
Стивен Эверс
источник
1

Мне нравится использовать игры в качестве примера, потому что это, как правило, немного более захватывающе, чем файловый ввод-вывод или что-либо еще, что вы можете придумать.

Поэтому, если вы хотите подать несколько команд подряд одному юниту в стратегической игре (например, иметь Зерглинга, чтобы разведать 4 угла базы по порядку, а затем совершить самоубийство в центре базы, очередь будет хорошим выбором). .)

Или, может быть, у вас есть приложение, которое может обрабатывать только 30 кадров в секунду, но вы можете получить 4 или 5 входов между кадрами. Если у вас есть вход для смены оружия и вход для выстрела, вы хотите убедиться, что они обрабатываются в том порядке, в котором они были получены, в противном случае вы можете бросить гранату, когда захотите нанести нож. И если вы гранаты, когда хотите нож, у вас будет плохое время. (поместите это на мем инструктора лыжи и бросьте это в свои понижения) :)

Сервер обработки запросов является еще одним хорошим.

Станок с ЧПУ, принимающий данные. Машина может двигаться только так быстро, поэтому ей нужно поставить в очередь данные.

Джастин
источник
1

Некоторые примеры, которые я могу придумать:

  • Калькулятор - может вводить префикс и постфикс одновременно
  • Инструкция по завязыванию обуви. Невозможно завершить следующую операцию, пока вы не выполните последнюю
  • Буферы - возможно, телефонный буфер используется для хранения номеров, которые пользователь ввел, но еще не издал звуковой сигнал.
  • пищеварение
sixtyfootersdude
источник
1

Производственные линии полны очередей. Подумайте о линии пустых бутылок, направляющихся к разливочной машине. Первым-первым-первым - это естественный способ последовательного применения процесса ко многим объектам. Очереди также используются для отделения одного процесса от другого: разливочная машина не должна останавливаться немедленно, если есть кратковременная проблема с этикетировочной машиной.

Очереди используются в программном обеспечении примерно одинаково. Вывод одного процесса может быть поставлен в очередь для ввода в другой процесс. Это верно, говорите ли вы о межпроцессном взаимодействии, межпотоковом взаимодействии или просто разбиваете сложный процесс на части, которые все могут обрабатываться одним и тем же потоком.

В операционных системах очереди часто используются для обработки входных данных по порядку. Например, файловая система может считывать блоки с устройства хранения и добавлять их в очередь. Или прерывания, которые обрабатывают такие вещи, как нажатия клавиш и движения мыши, создают события, которые добавляются в очередь событий, чтобы вы не получали «uqeeu» вместо «queue» при наборе текста.

Для простого студенческого задания я думаю, что любая задача, которая принимает некоторое количество входных данных и затем обрабатывает их, будет работать. Например, вы могли бы попросить их написать простой оценщик выражений postfix. Было бы три части:

  • прочитайте ввод, добавьте его в очередь ввода и повторяйте до тех пор, пока не прекратится ввод

  • получить предмет из очереди

    • если элемент является числом, поместите его в стек аргументов
    • если элемент является оператором, выдвиньте необходимые аргументы и оцените
    • добавить результат в очередь вывода
    • повторять, пока стек не опустеет
  • прочитать элемент из очереди вывода, распечатать его и повторять до тех пор, пока очередь вывода не станет пустой

Калеб
источник
1

При обучении структурам данных я обычно использую приложение моделирования банковской очереди, в котором клиенты ждут в очереди, и существует ряд окон обслуживания.

Проблема состоит в том, чтобы смоделировать процесс, чтобы узнать статистику следующего: время ожидания клиентов в очереди (максимум, минимум, среднее) и количество клиентов, ожидающих в очереди. Я использую предопределенную частоту прихода нового клиента каждую минуту дня и среднее время обслуживания клиента в окне обслуживания со значениями из генератора случайных чисел.

Результатом будут рекомендации по оптимальному количеству окон обслуживания и оптимальному количеству стульев в зале ожидания, которые гарантировали бы удовлетворение клиента. Очень интересное приложение для студентов.

Малик Эламейр
источник
1

Любой алгоритм планирования почти всегда включает очередь.

Это может варьироваться от простой очереди «первым пришел - первым обслужен» до запроса буфера для одного потребителя.

Для сложной очереди планирования заданий, где «задачи» могут иметь приоритеты, а «работники» - разные возможности.

Хороший вариант использования для игры может быть следующим: «У вас есть центральный сервер печати с четырьмя подключенными принтерами, два из которых способны к цветной печати, один - для двусторонней печати, а другой - для печати на бумаге большего размера. Пользователи могут доплачивать за срочные задания, или меньше, если они не возражают ждать дольше. Вы можете понести штрафы, если опаздываете, поэтому вы хотите максимально возможную пропускную способность ».

Джеймс Андерсон
источник