Kolejka może być opisana jako nieprosta liniowa struktura danych zgodna z porządkiem FIFO, w którym elementy danych są wstawiane z jednego końca (z tyłu) i usuwane z drugiego końca (z przodu). Inne warianty kolejki to kolejka cykliczna, podwójnie zakończona kolejka i kolejka priorytetowa.
Wykres porównania
| Podstawa do porównania | Linearna kolejka | Kolejka cykliczna |
|---|---|---|
| Podstawowy | Porządkuje elementy danych i instrukcje w porządku sekwencyjnym, jedna po drugiej. | Układa dane w schemacie kołowym, w którym ostatni element jest połączony z pierwszym elementem. |
| Kolejność wykonywania zadań | Zadania są wykonywane w kolejności, w jakiej zostały umieszczone wcześniej (FIFO). | Kolejność wykonywania zadania może się zmienić. |
| Wstawianie i usuwanie | Nowy element jest dodawany z tyłu i usuwany z przodu. | Wstawianie i usuwanie można wykonać w dowolnej pozycji. |
| Wydajność | Nieskuteczny | Działa lepiej niż kolejka liniowa. |
Definicja Linear Queue
Kolejka liniowa jest racjonalnie pierwszą uporządkowaną listą. Jest to tak zwana liniowa, ponieważ przypomina linię prostą, gdzie elementy są umieszczone jeden za drugim. Zawiera jednorodną kolekcję elementów, w których nowe elementy są dodawane na jednym końcu i usuwane z drugiego końca. Pojęcie kolejki można zrozumieć na przykładzie kolejki widzów oczekujących poza kasą biletową, aby uzyskać bilet do teatru. W tej kolejce osoba dołącza do tylnego końca kolejki, aby odebrać bilet, a bilet jest wystawiany na przednim końcu kolejki.
W kolejce wykonano kilka operacji
- Najpierw inicjalizowana jest kolejka do zera (tj. Pusta).
- Określ, czy kolejka jest pusta, czy nie.
- Określ, czy kolejka jest pełna, czy nie.
- Wstawienie nowego elementu od tylnego końca (Enqueue).
- Usunięcie elementu z przedniego końca (Usunięcie).
Kolejka może być zaimplementowana na dwa sposoby
- Statycznie (przy użyciu tablic)
- Dynamicznie (za pomocą wskaźników)
Ograniczeniem kolejki liniowej jest utworzenie scenariusza, w którym nie można dodać nowego elementu w kolejce, nawet jeśli kolejka zawiera puste miejsca. Powyższa sytuacja została zilustrowana na poniższym rysunku. Tutaj tył wskazuje ostatni indeks, podczas gdy wszystkie pola są puste, nie można dodać nowego elementu.
Definicja kolejki cyklicznej
Okrągła kolejka jest wariantem liniowej kolejki, która skutecznie pokonuje ograniczenie liniowej kolejki. W kolejce okrągłej nowy element jest dodawany na pierwszej pozycji kolejki, jeśli ostatni jest zajęty, a miejsce jest dostępne. Jeśli chodzi o kolejkę liniową, wstawianie może być wykonywane tylko od tylnego końca i usunięcie z przedniego końca. W pełnej kolejce po wykonaniu serii kolejnych usunięć w kolejce pojawia się pewna sytuacja, w której nie można dodać nowego elementu, nawet jeśli dostępna jest przestrzeń, ponieważ nadal występuje warunek niedopełnienia (Rear = max - 1).
Okrągła kolejka łączy oba końce za pomocą wskaźnika, w którym pierwszy element pojawia się po ostatnim elemencie. Śledzi także przód i tył, wprowadzając dodatkową logikę, dzięki czemu może śledzić elementy, które mają być wstawiane i usuwane. Dzięki temu cykliczna kolejka nie generuje warunku przepełnienia, dopóki kolejka nie będzie pełna.
Niektóre warunki, po których następuje kolejka cykliczna:
- Front musi wskazywać na pierwszy element.
- Kolejka będzie pusta, jeśli Front = Tył.
- Po dodaniu nowego elementu kolejka jest zwiększana o wartość jeden (tył = tył + 1).
- Gdy element zostanie usunięty z kolejki, front zostanie zwiększony o jeden (Front = Front + 1).
Kluczowe różnice między liniową kolejką a kolejką cykliczną
- Kolejka liniowa jest uporządkowaną listą, w której elementy danych są uporządkowane w porządku sekwencyjnym. Natomiast cykliczna kolejka przechowuje dane w sposób kołowy.
- Kolejka liniowa podąża za rozkazem FIFO w celu wykonania zadania (element dodany na pierwszej pozycji zostanie usunięty na pierwszej pozycji). I odwrotnie, w kolejce okrężnej kolejność operacji wykonywanych na elemencie może się zmienić.
- Wstawianie i usuwanie elementów jest ustalane w kolejce liniowej, tj. Dodawanie od końca tylnego i usuwanie z przedniego końca. Z drugiej strony, kolista kolejka jest w stanie wstawiać i usuwać element z dowolnego punktu, dopóki nie zostanie on zajęty.
- Kolejka liniowa marnuje przestrzeń pamięci, a kolejka cykliczna efektywnie wykorzystuje przestrzeń.
Implementacja kolejki liniowej
Przedstawiony poniżej algorytm ilustruje dodanie elementów w kolejce:
Kolejka potrzebuje trzech zmiennych danych, w tym jednej tablicy do przechowywania kolejki i innej, aby przechowywać początkową pozycję przednią i tylną równą -1.
insert (item, queue, n, rear) {if (tył == n), a następnie wydrukuj "przepełnienie kolejki"; else {tył = tył + 1; queue [tył] = element; }} Przedstawiony poniżej algorytm ilustruje usunięcie elementów w kolejce:
delete_circular (item, queue, rear, front) {if (tył == przód), a następnie drukuj "niedomiar kolejki"; else {front = front + 1; item = queue [front]; }} Implementacja okrągłej kolejki
Algorytm interpretacji dodania elementu w kolejce cyklicznej:
insert_circular (item, queue, rear, front) {tył = (tył + 1) mod n; jeśli (przód == tył), następnie wydrukuj "kolejka jest pełna"; else {queue [tył] = element; }} Algorytm wyjaśnia usuwanie elementu w kolejce cyklicznej:
delete_circular (item, queue, rear, front) {if (front == rear), a następnie print ("kolejka jest pusta"); else {front = front + 1; item = queue [front]; }} Wniosek
Kolejka liniowa jest nieefektywna w niektórych przypadkach, gdy elementy są wymagane do przejścia do pustych przestrzeni w celu wykonania operacji wstawiania. Z tego powodu ma tendencję do marnowania przestrzeni dyskowej, podczas gdy kolejka cykliczna w odpowiedni sposób wykorzystuje przestrzeń pamięci, ponieważ elementy są dodawane w dowolnej pozycji, jeśli istnieje pusta przestrzeń.
