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

9

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?

Michael Ekstrand
źródło
+1, ale powstrzymam się od tworzenia tagu „kolejka”, ponieważ zawiera on tylko twoje pytanie. Użyłbym „struktur danych”.
K.Steff
@ K.Steff, możesz mieć oba :-) Pamiętaj, że każdy nowy tag jest powiązany tylko z jednym pytaniem na początku.
Péter Török
1
Naturalne jest zakrywanie kolejek, gdy obejmuje się BFS. Dlaczego nie zapisać kolejek do tego czasu? Nie musisz pokrywać kolejek połączonymi listami i listami tablic, ponieważ mają one również liniową reprezentację.
kevin cline
@ PéterTörök Zdaję sobie sprawę, że wszystkie tagi zaczynają się puste, ale wyszukiwanie „kolejki” daje 313 pytania i żaden inny nie utworzył tagu „kolejki”. W każdym razie to tylko IMO
K.Steff,
Powtarzającym się motywem w odpowiedziach są symulacje kolejek w świecie rzeczywistym. Do tej pory myślałem, że wolałbym używać przykładów rzeczy, w których używałbym kolejki do rozwiązania problemu, który faktycznie powstaje w programowaniu, i że wiele przykładów świata fizycznego świeci najlepiej w równoczesnych środowiskach. Biorąc jednak pod uwagę powtórzenie tego tematu, może się okazać, że nie jestem pożytecznym tokiem myślenia. Nadal sugestie! I dziękuję wszystkim za wspaniałą pomoc.
Michael Ekstrand

Odpowiedzi:

14

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

Mike Caputo
źródło
Jak powiedziałem, ten przykład jest zarówno bardzo intuicyjny, jak i prawie zbyt często używany;)
marktani
1
Możesz zwiększyć złożoność, mając kolejkę priorytetową dla klientów z dodatkami (plan Aero).
sixtyfootersdude
1
IMO, najłatwiejszymi przykładami są te, które spotykamy w życiu. Przykład „linii” jest doskonałym przedstawieniem kolejki i powinien pomóc uczniom w nauce. W rzeczywistości, kiedy myślę o kolejkach i o tym, jak są zdefiniowane ich operacje, często myślę o „liniowym” przykładzie, który pomoże mi lepiej to zobaczyć.
Nicholas
To także świetna okazja, aby krótko omówić teorię kolejkowania: dlaczego pojedyncza linia obsługująca wiele rejestrów jest lepsza niż linia na rejestr. Pozwól im zbudować symulację i bawić się nią. Inżynier ma świetne, proste wyjaśnienie: engineerguy.com/videos/video-lines.htm
jpeacock
5

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?

marktani
źródło
+1 za przykład w supermarkecie. Wspomniałeś o tym, kiedy pisałem swoją odpowiedź!
Mike Caputo
3

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.

Péter Török
źródło
Przypominam sobie kolegów z klasy z college'u, porównujących różne style organizacji rejestrów fast food z projektami procesorów. Jedna kolejka obsługiwana przez wiele rejestrów? Każdy rejestr z własną kolejką? Wielu pracowników na tej samej linii - super skalarne przetwarzanie. To było zabawne.
3

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?

Kim.Net
źródło
Carrano - Struktury danych i abstrakcja w Javie .
Michael Ekstrand
2

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.

Michael Brown
źródło
2

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.

programista
źródło
2

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.

KChaloux
źródło
1

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.
Steven Evers
źródło
1

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.

Justin
źródło
1

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
sześćdziesiąt stóp
źródło
1

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

Caleb
źródło
1

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.

Malik Elamaireh
źródło
1

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

James Anderson
źródło