Wpisany przez Michał Knasiecki
poniedziałek, 01 sierpnia 2005 22:56
Kolejka jest strukturą liniowo uporządkowanych danych w której dołączać nowe dane można jedynie na koniec kolejki a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w przypadku
stosu, z tą różnicą, że usuwamy dane od początku a nie od końca.
Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n).
Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.
Schemat kolejki wygląda następująco:
Przykład w JavaScript:
Obraz kolejki:
Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n).
Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.
Schemat kolejki wygląda następująco:
Przykład w JavaScript:
Obraz kolejki:
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Kamil Dworak | C# | Visual Studio 2008 |  | |
  / 7 |
| Michał Knasiecki | C/C++ |  | |
/ 6 | |
| Marian | C/C++ | C++ | | |
/ 4 |
| Marian | C/C++ | | |
/ 3 | |
| Kamil Dworak | Java | JDK 1.6 |  | |
/ 2 |
| Tomasz Lubiński | Java Script |  | |
/ 2 | |
| Jakub Konieczny | Python |  | |
/ 3 |
Poprawiony: środa, 06 kwietnia 2011 20:37