Kolejka (informatyka): Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Bibliografia, linki zewnętrzne, szablon |
linki zewnętrzne, wikizacja, źródła/przypisy, akt. |
||
Linia 1:
[[Plik:Data Queue.svg|thumb|Idea kolejki]]
'''Kolejka''' ([[język angielski|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_(programowanie)|bufor]] typu '''FIFO''', ''First In, First Out''; ''pierwszy na wejściu, pierwszy na wyjściu'').
Operacje związane z kolejką zwyczajowo nazywa się ''enqueue'' („zakolejkuj”) oraz ''dequeue'' („odkolejkuj”){{odn|Cormen|Leiserson|Rivest|Stein|2012|s=232}}. 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).
Specjalną modyfikacją kolejki jest [[kolejka priorytetowa]] – każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet, który modyfikuje kolejność późniejszego wykonania. 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 priorytecie.▼
▲Specjalną modyfikacją kolejki jest [[kolejka priorytetowa]] – każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet (klucz), który
Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego rodzaju obsługą zdarzeń. W szczególności w [[system operacyjny|systemach operacyjnych]] ma zastosowanie kolejka priorytetowa, przydzielająca zasoby sprzętowe uruchomionym [[proces (informatyka)|procesom]].▼
▲Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego rodzaju obsługą zdarzeń. W szczególności w [[system operacyjny|systemach operacyjnych]] ma zastosowanie kolejka priorytetowa, przydzielająca zasoby sprzętowe uruchomionym [[proces (informatyka)|procesom]]{{r|linux_scheduler}}.
Przeciwieństwem kolejki jest [[stos (informatyka)|stos]], [[bufor (programowanie)|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 ==
{{commonscat|Queue data structure}}▼
{{Przypisy|
{{Wikibooks | Struktury danych/Kolejki}}▼
<ref name="linux_scheduler">http://lse.sourceforge.net/scheduling/PrioScheduler.html</ref>
}}
[[Kategoria:Struktury danych]]▼
== Bibliografia ==
* {{Cytuj książkę | odn = tak | imię = Thomas | nazwisko = Cormen | imię2 = Charles | nazwisko2 = Leiserson | imię3 = Ronald | nazwisko3 = Rivest | imię4 = Clifford | nazwisko4 = Stein | tytuł = Wprowadzenie do algorytmów | wydawca = [[Wydawnictwo Naukowe PWN]] | miejsce = Warszawa | rok = 2012 | isbn = 978-83-01-16911-4 | rozdział = Elementarne struktury danych. Stosy i kolejki | strony = 232-233}}
* {{Cytuj książkę | odn = tak | imię = Lech | nazwisko = Banachowski | imię2 = Krzysztof | nazwisko2 = Diks | imię3 = Wojciech | nazwisko3 = Rytter | tytuł = Algorytmy i struktury danych | wydawca = [[Wydawnictwa Naukowo-Techniczne]] | miejsce=Warszawa | rok = 2001 | isbn = 83-204-2658-8 | rozdział = Podstawowe struktury danych. Lista | strony = 25-27}}
▲{{commonscat|Queue data structure}}
▲{{Wikibooks | Struktury danych/Kolejki}}
▲[[Kategoria:Struktury danych]]
| |||