TechCodeview

W informatyce kolejka to liniowa struktura danych, w której komponenty są umieszczane na jednym końcu i usuwane z drugiego zgodnie z zasadą „pierwsze weszło, pierwsze wyszło” (FIFO). Tę strukturę danych można wykorzystać do kontrolowania sekwencji działań lub przechowywania danych. C to język komputerowy z możliwością tworzenia kolejek w postaci tablic lub list połączonych.

Charakterystyka:

• Kolejka to rodzaj liniowej struktury danych, którą można zbudować za pomocą tablicy lub połączonej listy.
• Elementy są przenoszone na koniec kolejki podczas usuwania z przodu.
• Umieszczenie w kolejce (dodanie elementu z tyłu) i usunięcie z kolejki (usunięcie elementu z przodu) to dwie operacje w kolejce.
• Gdy elementy są często dodawane i usuwane, kolejka może zostać zbudowana jako kolejka cykliczna, aby zapobiec marnowaniu pamięci.

Korzystanie z tablicy:

Aby zaimplementować kolejkę w C przy użyciu tablicy, najpierw zdefiniuj maksymalny rozmiar kolejki i zadeklaruj tablicę o tym rozmiarze. Liczby całkowite przód i tył zostały odpowiednio ustawione na 1. Zmienna front reprezentuje przedni element kolejki, a zmienna back reprezentuje element tylny.

Przed wypchnięciem nowego elementu na końcową pozycję kolejki należy zwiększyć zmienną wsteczną o 1. Kolejka jest teraz pełna i nie można już dodawać żadnych dodatkowych elementów, gdy pozycja tylna osiąga maksymalną pojemność kolejki. Dodajemy element na początek kolejki i zwiększamy zmienną frontu tylko o jeden, aby usunąć element z kolejki. Jeżeli pozycje przednia i tylna są sobie równe i nie można już usunąć więcej elementów, to można powiedzieć, że kolejka jest pusta.

Poniżej znajduje się przykład kolejki napisanej w C, która wykorzystuje tablicę:

Język programowania C:

 #define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } 

Dane wyjściowe kodu będą następujące:

Wyjście:

 10 20 30 Queue is empty-1 

Wyjaśnienie:

1. Najpierw kolejkujemy do kolejki trzy elementy 10, 20 i 30.
2. Następnie usuwamy z kolejki i drukujemy przedni element kolejki, czyli 10.
3. Następnie usuwamy z kolejki i ponownie drukujemy przedni element kolejki, czyli 20.
4. Następnie usuwamy z kolejki i ponownie drukujemy przedni element kolejki, czyli 30.
5. Na koniec usuwamy z kolejki pustą kolejkę, co zwraca komunikat „Kolejka jest pusta” i zwraca -1.

Korzystanie z listy połączonej:

Innym alternatywnym podejściem do konstruowania kolejki w języku programowania C jest użycie listy połączonej. Każdy z węzłów w kolejce jest wyrażany przy użyciu tej metody przez węzeł, który zawiera wartość elementu i wskaźnik do kolejnego węzła w kolejce. Aby śledzić odpowiednio pierwszy i ostatni węzeł w kolejce, używane są wskaźniki przód i tył.

Tworzymy nowy węzeł z wartością elementu i ustawiamy jego kolejny wskaźnik na NULL, aby dodać element do kolejki. Do nowego węzła ustawiamy wskaźniki przód i tył jeśli kolejka jest pusta. Jeśli nie, aktualizujemy tylny wskaźnik i ustawiamy następny wskaźnik starego tylnego węzła tak, aby wskazywał nowy węzeł.

Podczas usuwania węzła z kolejki najpierw usuwany jest węzeł poprzedni, następnie wskaźnik frontu jest aktualizowany na kolejny węzeł w kolejce, a na koniec zostaje zwolniona pamięć, którą zajmował usunięty węzeł. Jeśli po usunięciu przedni wskaźnik ma wartość NULL, kolejka jest pusta.

Oto przykład kolejki zaimplementowanej w C przy użyciu połączonej listy:

Język programowania C:

 #include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } 

Dane wyjściowe kodu będą następujące:

Wyjście:

 10 20 30 Queue is empty-1 

Wyjaśnienie:

1. Najpierw kolejkujemy do kolejki trzy elementy 10, 20 i 30.
2. Następnie usuwamy z kolejki i drukujemy przedni element kolejki, czyli 10.
3. Następnie usuwamy z kolejki i ponownie drukujemy przedni element kolejki, czyli 20.
4. Następnie usuwamy z kolejki i ponownie drukujemy przedni element kolejki, czyli 30.
5. Na koniec próbujemy usunąć z kolejki pustą kolejkę, co powoduje wyświetlenie komunikatu „Kolejka jest pusta” i zwrócenie -1.

Zalety:

• Kolejki są szczególnie przydatne do implementowania algorytmów wymagających przetwarzania elementów w dokładnej kolejności, takich jak przeszukiwanie wszerz i planowanie zadań.
• Ponieważ operacje kolejkowe mają złożoność czasową O(1), można je wykonać szybko nawet w ogromnych kolejkach.
• Kolejki są szczególnie elastyczne, ponieważ można je po prostu zaimplementować przy użyciu tablicy lub połączonej listy.

Niedogodności:

• Kolejki, w przeciwieństwie do stosu, nie można zbudować za pomocą pojedynczego wskaźnika, co sprawia, że ​​implementacja kolejki jest nieco bardziej skomplikowana.
• Jeśli kolejka jest zbudowana jako tablica, może wkrótce się zapełnić, jeśli zostanie dodanych zbyt wiele elementów, co spowoduje problemy z wydajnością lub nawet awarię.
• W przypadku korzystania z listy połączonej do implementacji kolejki obciążenie pamięci każdego węzła może być znaczne, szczególnie w przypadku małych elementów.

Wniosek:

Aplikacje korzystające z kolejek – kluczowej struktury danych – obejmują między innymi systemy operacyjne, sieci i gry. Są idealne dla algorytmów, które muszą obsługiwać elementy w określonej kolejności, ponieważ można je łatwo utworzyć za pomocą tablicy lub połączonej listy. Kolejki mają jednak wady, które należy wziąć pod uwagę przy wyborze struktury danych dla konkretnej aplikacji, takie jak zużycie pamięci i złożoność implementacji.