Jakie są dobre, proste przykłady kolejek? [Zamknięte]

Uczę CS2 ( Java and data structures) i mam trudności z wymyśleniem dobrych przykładów do wykorzystania podczas nauczania kolejek. Dwie główne aplikacje, w których ich używam, to multithreadedprzekazywanie wiadomości (ale programowanie MT nie wchodzi w zakres kursu) i BFS-style algorithms(i nie będę obejmował wykresów później).

Chcę też uniknąć wymyślonych przykładów. Większość rzeczy, o których myślę, gdybym miał je rozwiązać w sposób jednowątkowy, użyłbym raczej listy niż kolejki. Zwykle używam kolejek tylko wtedy, gdy przetwarzanie i wykrywanie są przeplatane (np. Wyszukiwanie) lub w innych specjalnych przypadkach, takich jak bufory o ograniczonej długości (np. Utrzymanie ostatnich N elementów). W zakresie praktycznym staram się uczyć moich uczniów dobrych sposobów robienia rzeczy w prawdziwych programach, a nie tylko zabawek, aby pokazać jakąś funkcję.

Jakieś sugestie dobrych, prostych algorytmów lub aplikacji kolejek, które mogę wykorzystać jako przykłady, ale które wymagają minimum innej wcześniejszej wiedzy?

Kiedy uczyłem się kolejek, mój profesor zawsze korzystał z przykładu sklepu. W danym momencie jest otwarty jeden lub więcej rejestrów, a klienci wchodzą do jednej lub drugiej kolejki i przechodzą przez tę kolejkę, aby kupić wszystkie swoje produkty.

W rzeczywistości musieliśmy wdrożyć prosty program, który mógłby przeprowadzać klientów przez RegisterQueue, więc jeśli faktycznie szukasz programu, możesz dać uczniom ten przykład, który jest prosty i bezpośredni, ale także coś, co każdy uczeń widział w życiu i tak dalej może pomóc im lepiej zrozumieć tę koncepcję.

Kiedy nauczyłem się kolejek, mój nauczyciel przedstawił mi je, stosując zestaw samochodów do kontroli policyjnej. Była kolejka z samochodami („kolejka oczekujących”), a policjant zawsze kontrolował następny samochód w kolejce i albo wysyłał go do swojego kolegi do dalszych kontroli, albo pozwalał, aby samochód przejechał.

Przykładem bardzo często stosowanym jest kolejka na super-rynku ...

Dlaczego nie poprosisz swoich uczniów o podanie przykładów?

Jednym z przykładów, który przychodzi mi na myśl, jest linia przetwarzania hamburgerów, np. McDonalds. Istnieje kilka rodzajów różnych burgerów, każdy może być wyprodukowany przez kilku różnych pracowników i każdy ma swoją kolejkę. Stamtąd po chwili gotowe hamburgery są odbierane, w kolejności FIFO, przez jednego z kasjerów, który zamówił tego rodzaju burgera.

Jest więc wielu producentów i konsumentów, a każda kolejka jest ograniczona.

Pomyślałem o użyciu Amazon jako przykładu, gdzieś w ich ogromnym systemie musi być kolejka zamówień, którą trzeba obsłużyć. które można obsłużyć prostą kolejką i kolejką. system umieszczał w kolejce zamówienie w systemie za każdym razem, gdy klient kupował książkę, a następnie osoba z magazynu składała ją z kolejki, aby ją wybrać i opublikować.

Łatwo byłoby wtedy zacząć mówić o kolejkach priorytetowych, wprowadzając głównych klientów, którzy mogą przeskoczyć kolejkę, można wprowadzić kolejki priorytetowe.

Z jakiego podręcznika korzystasz?

Idealnym przykładem kolejki byłyby transakcje bankowe przetwarzane na konto. Zwykle pod koniec dnia wyświetlana jest lista „oczekujących” transakcji. Po zakończeniu księgowania transakcje są stosowane do konta. Dzięki temu możesz nawet dostać się do obszaru priorytetowych kolejek. Wydaje się, że większość banków priorytetowo traktuje obciążenia przy przetwarzaniu transakcji nocnych, aby mogły przedłużyć opłaty wstępne, zanim zastosują jakiekolwiek oczekujące kredyty.

Transakcje są wstawiane do kolejki według kolejności wykonania i usuwane z kolejki oraz stosowane na koncie przez proces księgowy.

Kiedyś byłem programistą telekomunikacyjnym, więc przychodzi mi na myśl:

Infolinia obsługi klienta. Przychodzi połączenie, nie ma wystarczającej liczby operatorów do obsługi połączenia i jest ono umieszczane w kolejce. Nadchodzi następne połączenie i jest ono również umieszczane w kolejce. Następnie, gdy następny operator stanie się dostępny, pierwsze połączenie, które weszło do kolejki, zostaje przypisane do dostępnego operatora.

Oczywistymi przykładami w świecie rzeczywistym byłyby takie rzeczy, jak linie do kasy, i tak, ale skoro szukasz przykładu opartego ściśle na informatyce, czy mogę zasugerować kolejki planowania zadań ?

Nie wiem, ilu twoich uczniów wzięło udział w zajęciach z systemów operacyjnych, ale dobrze się stało, że wszyscy korzystali z Menedżera zadań, aby sprawdzić swoje procesy w pewnym momencie. Możesz wprowadzić uproszczony przykład kolejki planowania i przypisać jej zadanie domowe do napisania programu, który generuje (lub akceptuje) „zadanie” o danym rozmiarze i przetwarza je w kolejności FIFO, gdy je „uruchomi”.

Jest to dość łatwa do zrozumienia koncepcja, demonstruje ideę, że kolejka działa na jej zawartości w kolejności, w której je akceptuje, i daje im (bardzo podstawowe i uproszczone) wprowadzenie do planowania procesora. Tylko moje dwa bity.

Możesz przywołać ich zastosowanie w wielowątkowości, ale jeśli uczniowie nie mieliby już doświadczenia w pisaniu programów wątkowych, nie przypisałbym im pracy, która może wywołać dwie frustracje. Pamiętam, że miałem problemy z nauką struktur danych (szczególnie w Javie, ponieważ nie uczyłem się C ++ i nie nauczyłem się niczego na temat wskaźników) na drugim roku studiów, więc prosty, ale praktyczny przykład bezpośrednio związany z obliczeniami jest prawdopodobnie najlepszy.

Prawdziwy świat:

• Za każdym razem, gdy ludzie ustawiają się w szeregu: kasjerka w sklepie spożywczym, w restauracji czeka na stolik (możesz pracować przy tych sygnałach dźwiękowych, które czasem podają w analogii) itp. Jest to pomocne, gdy zauważysz, że w Wielkiej Brytanii często wywoływać te kolejki zamiast linii (wspólne w NA)
• Czytanie serii książek ', autor.publish => kolejka.push i student.read => kolejka.pop

Świat nierealny:

• Przetwarzanie przesłanych danych w środowisku jednowątkowym, w którym przetwarzanie trwa dłużej niż przesłanie (np. Operacje kasowe dla sklepów internetowych)
• Każda kolekcja FIFO, którą można iterować, może używać kolejek i używać while(queue.peek)zamiast iteratora.

Lubię używać gier jako przykładu, ponieważ jest to na ogół trochę bardziej ekscytujące niż plikowe We / Wy lub cokolwiek innego, co możesz wymyślić.

Więc jeśli chcesz wydać kilka poleceń z rzędu jednostce w grze strategicznej (np. Poproś Zerglinga o zwiad 4 rogów bazy, a następnie samobójstwo na środku bazy, kolejka będzie dobrym wyborem .)

A może masz aplikację, która może przetwarzać tylko 30 ramek na sekundę, ale możesz uzyskać 4 lub 5 danych wejściowych między ramkami. Jeśli masz wkład do zmiany broni i strzelania, chcesz się upewnić, że zostaną one obsłużone w kolejności, w jakiej zostały otrzymane, w przeciwnym razie możesz granat, gdy chcesz noże. A jeśli granatujesz, kiedy chcesz nozić, będziesz miał zły czas. (umieść to na memie instruktora narciarstwa i wrzuć do slajdów) :)

Serwer obsługujący żądania jest kolejnym dobrym.

Maszyna CNC przyjmująca dane wejściowe. Maszyna może jechać tak szybko, więc musi ustawić kolejkę w kolejce.

Kilka przykładów, o których mogę myśleć:

• Kalkulator - może jednocześnie wprowadzić przedrostek i postfiks
• Instrukcje wiązania butów. Nie można ukończyć następnej operacji, dopóki nie wykonasz ostatniej
• Bufory - Być może bufor telefoniczny służy do przechowywania numerów wprowadzonych przez użytkownika, ale nie wydał jeszcze dźwięku
• Trawienie

Linie produkcyjne są pełne kolejek. Pomyśl o linii pustych butelek zmierzających do maszyny do napełniania. Pierwszy na pierwszym to naturalny sposób sekwencyjnego zastosowania procesu do wielu obiektów. Kolejki służą również do oddzielenia jednego procesu od drugiego: maszyna do napełniania nie musi się natychmiast zatrzymywać, jeśli wystąpi krótkotrwały problem z maszyną do etykietowania.

Kolejki są używane w oprogramowaniu na prawie te same sposoby. Dane wyjściowe jednego procesu można ustawić w kolejce w celu wprowadzenia do innego procesu. Dzieje się tak niezależnie od tego, czy mówisz o komunikacji między procesami, komunikacji między wątkami, czy po prostu dzielisz skomplikowany proces na części, które mogą być obsługiwane przez ten sam wątek.

W systemach operacyjnych kolejki są często używane do przetwarzania danych wejściowych w kolejności. System plików może na przykład czytać bloki z urządzenia pamięci masowej i dodawać je do kolejki. Lub przerwania, które obsługują takie czynności, jak naciśnięcia klawiszy i ruchy myszy, tworzą zdarzenia, które są dodawane do kolejki zdarzeń, dzięki czemu nie pisze się „uqeeu” zamiast „kolejki” podczas pisania.

W przypadku prostego zadania studenckiego myślę, że każde zadanie, które przyjmie pewną liczbę danych wejściowych, a następnie przetworzy je, zadziała. Na przykład, możesz poprosić ich o napisanie prostego ewaluatora wyrażeń postfiksowych. Miałby trzy części:

• przeczytaj dane wejściowe, dodaj je do kolejki wejściowej i powtarzaj, aż nie będzie już żadnych danych wejściowych

• dostać przedmiot z kolejki

  • jeśli element jest liczbą, pchnij go na stos argumentów
  • jeśli element jest operatorem, wstaw niezbędne argumenty i oceń
  • dodaj wynik do kolejki wyjściowej
  • powtarzaj, aż stos będzie pusty

• odczytać element z kolejki wyjściowej, wydrukować go i powtarzać, aż kolejka wyjściowa będzie pusta

W nauczaniu struktur danych zwykle używam aplikacji symulacji kolejek bankowych, w której klienci czekają w kolejce i jest wiele okien usług.

Problem polega na symulacji procesu w celu znalezienia statystyk dotyczących: czasu oczekiwania klientów w kolejce (maks., Min., Średnia) oraz liczby klientów oczekujących w kolejce. Korzystam ze z góry określonej częstotliwości przybywania nowego klienta co minutę dziennie i średniego czasu obsługi klienta w oknie serwisowym z wartościami z generatora liczb losowych.

Rezultatem będą zalecenia dotyczące optymalnej liczby okien serwisowych i optymalnej liczby krzeseł w poczekalni, która zagwarantuje zadowolenie klienta. Bardzo interesująca aplikacja dla studentów.

Każdy algorytm planowania prawie zawsze obejmuje kolejkę.

Może to wahać się od prostej kolejki „kto pierwszy, ten lepszy” do żądania bufora dla pojedynczego konsumenta.

Do złożonej kolejki planowania zadań, w której „zadania” mogą mieć priorytety, a „pracownicy” mają różne możliwości.

Dobrym przykładem użycia do zabawy może być: „Masz centralny serwer druku z czterema podłączonymi drukarkami, dwiema kolorowymi, jedną zdolną do drukowania dwustronnego i drugą do drukowania na większym papierze. Użytkownicy mogą dodatkowo zapłacić za pilną pracę, lub mniej, jeśli nie mają nic przeciwko czekaniu dłużej. Możesz ponieść kary, jeśli spóźnisz się, więc chcesz jak najwięcej przepustowości ”.