Kolejka (informatyka)

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Idea kolejki

Kolejka (ang. queue) – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).

System operacyjny (ang. Operating System, skrót OS) – oprogramowanie zarządzające systemem komputerowym, tworzące środowisko do uruchamiania i kontroli zadań użytkownika.Kolejka – zwana też ogonem lub ogonkiem. Forma nietrwałej zbiorowości powstająca przy transakcji (kolejki mieszkaniowe w PRL były trwałe, gdyż okres oczekiwania wynosił czasem powyżej 20 lat, także oczekiwanie na samochód w NRD trwało kilkanaście lat). Wiąże się ona ze zbyt małą liczbą osób oferujących dany towar/usługę w stosunku do zapotrzebowania i czasu obsługi. W wyniku tej sytuacji powstaje zgromadzenie ludzi, którzy organizują kolejność obsługi.

Operacje związane z kolejką zwyczajowo nazywa się enqueue („zakolejkuj”) oraz dequeue („odkolejkuj”). Kolejka działa tak jak kolejka w sklepie i ma podobną strukturę. Składa się z początku (Front, Head) oraz końca (Back, Tail). Nowy element zawsze dodawany jest na końcu, analogicznie do klienta, który zawsze staje na końcu kolejki. Usunięcie z kolejki odpowiada obsłużeniu klienta w sklepie, czyli osoby, która aktualnie czekała najdłużej (tj. znajduje się z przodu kolejki).

Proces – jedno z podstawowych pojęć w informatyce, definiowane jako egzemplarz wykonywanego programu. Każdy nowo powstały proces otrzymuje unikatowy numer, który go jednoznacznie identyfikuje, tzw. PID (od (ang.) process identifier).Kolejka priorytetowa (ang. priority queue) – abstrakcyjny typ danych służący do reprezentowania zbioru elementów, z których każdy ma przyporządkowaną wartość zwaną kluczem.

Specjalną modyfikacją kolejki jest kolejka priorytetowa – każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet (klucz), który służy do określenia kolejności poszczególnych elementów w zbiorze. Oznacza to, że pierwsze na wyjściu niekoniecznie pojawią się te dane, które w kolejce oczekują najdłużej, lecz te o największym (lub najmniejszym) priorytecie.

Wydawnictwo Naukowe PWN SA – wydawnictwo z siedzibą w Warszawie, założone w 1951, w obecnej formie prawnej działające od 1997. Wydawnictwo Naukowe PWN SA stanowi jednostkę dominującą Grupy kapitałowej PWN, w skład której wchodzi kilkanaście przedsiębiorstw, głównie wydawnictw.Bufor to obszar pamięci służący do przechowywania danych do komunikacji pomiędzy dwoma systemami, np. bufor karty sieciowej przechowuje pakiety, które mają zostać wysłane, a bufor karty graficznej – to co ma zostać wyświetlone na ekranie.

Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego rodzaju obsługą zdarzeń. W szczególności w systemach operacyjnych ma zastosowanie kolejka priorytetowa, przydzielająca zasoby sprzętowe uruchomionym procesom.

Przeciwieństwem kolejki jest stos, bufor typu LIFO (ang. Last In, First Out; ostatni na wejściu, pierwszy na wyjściu), w którym jako pierwsze obsługiwane są dane wprowadzone jako ostatnie.

Przypisy[ | edytuj kod]

  1. Cormen i in. 2012 ↓, s. 232.
  2. Cormen i in. 2012 ↓, s. 161-164.
  3. Banachowski, Diks i Rytter 2001 ↓, s. 70-78.
  4. Linux Priority-Queue Scheduler. lse.sourceforge.net. [dostęp 2018-03-13].

Bibliografia[ | edytuj kod]

  • „Elementarne struktury danych”: „Stosy i kolejki”. W: Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwo Naukowe PWN, 2012, s. 232-233. ISBN 978-83-01-16911-4.
  • „Podstawowe struktury danych”: „Lista”. W: Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2001, s. 25-27. ISBN 83-204-2658-8.






  • Reklama