Programista projektuje obsługę bufora drukowania dokumentów. Najnowsze zadanie drukowania jest ustawiane na końcu kolejki, a najstarsze jest przekazywane do wydruku. Strukturą danych najlepiej pasującą do problemu jest
W tym przypadku najlepiej pasuje kolejka działająca według zasady FIFO, czyli First In, First Out. Chodzi o to, że zadanie, które trafiło do bufora jako pierwsze, powinno jako pierwsze zostać obsłużone przez drukarkę. Nowe dokumenty są dopisywane na końcu kolejki, a drukarka pobiera dokument z jej początku. To dokładnie opisuje mechanizm kolejki FIFO, bardzo typowy dla buforów, kolejek komunikatów, obsługi żądań sieciowych czy zadań w systemie operacyjnym. Moim zdaniem to jeden z najbardziej praktycznych przykładów struktur danych, bo łatwo go sobie wyobrazić jak zwykłą kolejkę w sklepie. W dobrych praktykach projektowania takiego bufora trzeba też pamiętać o synchronizacji dostępu, jeśli wiele programów dodaje zadania naraz, oraz o obsłudze błędów drukowania. Czasem stosuje się kolejki priorytetowe, ale tylko wtedy, gdy wymaganie mówi, że niektóre dokumenty mają mieć pierwszeństwo. Tutaj jasno jest podane, że najstarsze zadanie idzie do wydruku, więc klasyczne FIFO jest najbardziej trafne.
W tym zadaniu łatwo pomylić pojęcia, bo kilka odpowiedzi brzmi podobnie technicznie, ale opisują zupełnie inne zachowanie. Stos działa według zasady LIFO, czyli Last In, First Out. Oznacza to, że element dodany jako ostatni jest zdejmowany jako pierwszy. Gdyby bufor drukowania działał jak stos, to najnowszy dokument byłby drukowany przed starszymi. W praktyce byłoby to dość kiepskie i niesprawiedliwe, bo starsze zadania mogłyby czekać bardzo długo, a nawet zostać ciągle spychane przez nowsze dokumenty. Z mojego doświadczenia uczniowie często kojarzą dodawanie na koniec z operacją push na stosie, ale zapominają, że kluczowe jest też to, skąd element jest później pobierany.
Sterta też nie jest właściwym wyborem dla zwykłego bufora drukowania. Heap służy głównie do sprawnego wybierania elementu o największym albo najmniejszym priorytecie, na przykład w kolejce priorytetowej. To ma sens, gdy zadania mają priorytety, terminy lub koszty, ale w treści pytania nie ma nic o priorytetach. Jest za to wyraźnie powiedziane, że najstarsze zadanie ma iść do wydruku. LIFO jako sama zasada również odpada, bo jest przeciwieństwem oczekiwanego zachowania. Poprawne myślenie jest takie: skoro pierwszy dokument, który trafił do bufora, ma być pierwszy obsłużony, to potrzebujemy kolejki FIFO. W profesjonalnych systemach taki wybór daje przewidywalność, prostszą diagnostykę i zachowanie zgodne z intuicją użytkownika.
Sterta też nie jest właściwym wyborem dla zwykłego bufora drukowania. Heap służy głównie do sprawnego wybierania elementu o największym albo najmniejszym priorytecie, na przykład w kolejce priorytetowej. To ma sens, gdy zadania mają priorytety, terminy lub koszty, ale w treści pytania nie ma nic o priorytetach. Jest za to wyraźnie powiedziane, że najstarsze zadanie ma iść do wydruku. LIFO jako sama zasada również odpada, bo jest przeciwieństwem oczekiwanego zachowania. Poprawne myślenie jest takie: skoro pierwszy dokument, który trafił do bufora, ma być pierwszy obsłużony, to potrzebujemy kolejki FIFO. W profesjonalnych systemach taki wybór daje przewidywalność, prostszą diagnostykę i zachowanie zgodne z intuicją użytkownika.