Okrągła kolejka w C: jak zaimplementować?
Opublikowany: 2020-10-23Dane są ułożone w kołowej kolejce we wzór kołowy, gdzie ostatni element jest połączony z pierwszym elementem. W przeciwieństwie do kolejki liniowej, w której zadania są wykonywane w systemie FIFO (pierwsze weszło, pierwsze wyszło), kolejność wykonywania zadań w kolejce cyklicznej może ulec zmianie. Operacje wstawiania i usuwania można wykonać w dowolnej pozycji.
Kolejka okrężna jest bardziej wydajna niż kolejka liniowa. W graficznej reprezentacji kolejki kołowej można zaobserwować, że pozycje przednia i tylna są połączone, tworząc okrąg, w którym operacje są zawsze wykonywane na zasadzie FIFO. Każdy nowy element jest dodawany z tyłu i usuwany z przodu. Kolejka okrężna ma lepsze wykorzystanie i ma złożoność czasową O(1).
Źródło
Spis treści
Zastosowania kolejki okrężnej
- Planowanie procesora: Kolejki cykliczne wykorzystują puste przestrzenie pamięci, które znajdują się w kolejkach liniowych.
- System ruchu: W systemie ruchu, za pomocą okrężnych kolejek, sygnalizacja świetlna jest obsługiwana w ustalonych odstępach czasu.
- Zarządzanie pamięcią: Systemy operacyjne często utrzymują ciąg procesów przygotowanych do wykonania lub oczekujących na wystąpienie określonego zdarzenia.
Dowiedz się: C Program do sortowania bąbelków: Sortowanie bąbelków w C
Przykładowy kod z wyjaśnieniem
Linia 1: // (1) Preprocesory
Linia 2: // Ustaw limit kolejki na 5 elementów
Linia 3: #include<stdio.h>
Linia 4: #zdefiniuj LIM 5
Linia 5: // (2) Deklaracje typu danych kolejki
Linia 6: // dane przechowują dane; delPos, pozycja do usunięcia; długość, nie. z
Linia 7: // elementy aktualnie obecne w kolejce
Linia 8: typedef struct kolejka {
Linia 9: int dane[LIM], delPos, długość;
Linia 10: } Q;
Wiersz 11: // (3) Deklaracje globalne
Linia 12: // Funkcje i zmienna globalna q typu kolejki struktury
Linia 13: Qq;
Linia 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();
Linia 15: // (4) Wywołuje funkcję UI po inicjalizacji
Linia 16: int main()
Linia 17: {
Linia 18: initQ();
Linia 19: ui_Q_Ops();
Linia 20: powrót 0;
Linia 21: }
Linia 22: // (5) Zainicjuj kolejkę
Linia 23: void initQ()
Linia 24: {
Linia 25: q.length = 0;
Linia 26: q.delPos = 0;
Linia 27: }
Linia 28: // (6) Pętla sterowana menu wywołuje prawidłowe funkcje
Linia 29: nieważne ui_Q_Ops()
Linia 30: {
Linia 31: int wybór=0;
Linia 32: wprowadzanie znaków[16];
Linia 33: while(wybór!=4){
Linia 34: printf(” \n ———————-\n”);
Linia 35: printf(” 1. Wstaw do kolejki \n “);
Linia 36: printf(” 2. Usuń z kolejki \n “);
Linia 37: printf(” 3. Wyświetl pozycje kolejki \n “);
Linia 38: printf(” 4. Zakończ program \n „);
Linia 39: printf(” Wpisz wybór : “);
Linia 40: if (fgets(input, 15, stdin) != NULL){
Linia 41: if (sscanf(input, “%d”, &choice) == 1){
Linia 42: przełącznik(wybór){
Linia 43: przypadek 1: insertQel();
Linia 44: przerwa;
Linia 45: przypadek 2: usuńQel();
Linia 46: przerwa;
Linia 47: przypadek 3: displayQels();
Linia 48: przerwa;
Linia 49: przypadek 4: powrót;
Linia 50: domyślnie: printf("Nieprawidłowy wybór\n ");
Linia 51: kontynuuj;
Linia 52: }
Linia 53: } inny
Wiersz 54: printf(” Nieprawidłowy wybór \n „);
Linia 55: }
Linia 56: }
Linia 57: }
Linia 58: // (7) Wstaw do kolejki
Linia 59: // Jeśli długość jest taka sama jak MAX Limit, kolejka jest pełna, w przeciwnym razie wstaw
Linia 60: // osiągnięta cyklicznie z długością sumy i modułem delPos przez MAX Limit
Linia 61: // i przyrost długości
Linia 62: void insertQel()
Linia 63: {
Wiersz 64: int el, inspo;
Linia 65: wprowadzanie znaków[16];
Linia 66: if (q.length == LIM){
Linia 67: printf(”Kolejka jest pełna \n”);
Linia 68: powrót;
Linia 69: }
Linia 70: inspo = (q.delPos + q.length) % LIM;
Linia 71: printf(” Wprowadź element do wstawienia: “);
Linia 72: if (fgets(input, 15, stdin) != NULL){
Linia 73: if (sscanf(input, “%d”, &el)){
Linia 74: q.data[inspos] = el;
Linia 75: q.długość++;
Linia 76: } jeszcze
Linia 77: printf(” Nieprawidłowe dane wejściowe \n „);
Linia 78: }
Linia 79: }
Linia 80: // (8) Usuń z kolejki
Linia 81: // Jeśli Length wynosi 0, kolejka jest pusta, w przeciwnym razie usuń w delPos
Linia 82: // i zmniejszanie długości
Linia 83: void usuńQel()
Linia 84: {
Linia 85: if (q.length == 0){
Linia 86: printf(”Kolejka jest pusta \n”);
Linia 87: } inny {
Linia 88: printf(” Element usunięty %d \n “, q.data[q.delPos]);
Linia 89: q.delPos = (q.delPos + 1) % LIM;
Linia 90: q.długość–;
Linia 91: }
Linia 92: }
Linia 93: // (9) Wyświetl elementy kolejki
Linia 94: // Wyświetlaj w sposób kołowy, uruchamiając pętlę rozpoczynającą się od delPos
Linia 95: // i dodanie iteratora i modułu przez Max Limit
Linia 96: void displayQels()
Linia 97: {
Linia 98: wewn. i;
Linia 99: if (q.length == 0){
Linia 100: printf(” Kolejka jest pusta \n “);
Linia 101: } inny {
Linia 102: printf(” Elementami kolejki są: “);
Linia 103: for(i = 0; i < q.długość; i++){
Linia 104: printf(„%d”, q.data[(q.delPos+i)%LIM]);
Linia 105: }
Linia 106: printf(”\n”);
Linia 107: }
Linia 108: }
Linia 109:
Wyjścia:
Operacje na kolejce okrężnej
1. insertQel() – Wstawianie elementu do Circular Queue
W kolejce cyklicznej funkcja enQueue() służy do wstawiania elementu do kolejki cyklicznej. W okrągłej kolejce nowa funkcja jest zawsze umieszczana w tylnej pozycji. Funkcja enQueue() przyjmuje jako parametr jedną wartość całkowitą i wstawia ją do kolejki cyklicznej. Następujące kroki są realizowane w celu wstawienia elementu do kolejki okrężnej:
Krok 1 – Sprawdź, czy długość jest taka sama jak MAX Limit. Jeśli prawda, oznacza to, że kolejka jest PEŁNA. Jeśli jest FULL, wyświetl „Kolejka jest pełna” i zakończ funkcję.
Krok 2 – Jeśli NIE jest FULL, wstaw wartość, która jest osiągana cyklicznie z długością sumy i modułem delPos przez MAX Limit i długość przyrostu
2. deleteQel() – usuwanie elementu z Circular Queue
W kolejce cyklicznej deQueue() jest funkcją używaną do usuwania elementu z kolejki cyklicznej. W kolejce okrężnej element jest zawsze usuwany z pozycji przedniej. Funkcja deQueue() nie przyjmuje żadnej wartości jako parametru. Poniższe kroki są zaimplementowane w celu usunięcia elementu z kolejki okrężnej…
Krok 1 – Sprawdź, czy kolejka jest PUSTA. (przód == -1 && tył == -1)
Krok 2 – Jeśli jest PUSTY, wyświetl „Kolejka jest pusta” i zakończ funkcję.
Krok 3 – Jeśli NIE jest PUSTY, wyświetl usunięte elementy zgodnie z pozycjami. Po dodaniu każdego elementu przejdź do następnego limitu kolejki modów.
3. displayQels() – Wyświetla elementy kolejki, które są obecne w Circular Queue. Aby wyświetlić elementy kolejki okrężnej, zaimplementowano następujące kroki:
Krok 1 – Sprawdź, czy kolejka jest PUSTA.
Krok 2 – Jeśli długość wynosi 0, oznacza to, że jest PUSTY, a następnie wyświetl „Kolejka jest pusta” i zakończ funkcję.
Krok 3 – Jeśli NIE jest PUSTY, zdefiniuj zmienną całkowitą „i”.
Krok 4 – Ustaw i na 0.
Krok 5 – Ponownie wyświetl elementy zgodnie z pozycją i wartością przyrostu o jeden (i++). Powtarzaj to samo, aż 'i <q.length' zmieni się na FAŁSZ.
Kolejkę cykliczną można również zaimplementować za pomocą połączonej listy. Oto algorytmy:
- Algorytm dla kolejki:
if (FRONT == NULL) // Wstawianie pustej kolejki
PRZÓD = TYŁ = nowy węzeł
koniec jeśli
w przeciwnym razie
REAR -> next = newNode // Wstawianie po ostatnim elemencie
TYŁ = nowy węzeł
koniec jeszcze
TYŁ -> następny = PRZÓD
Zakończ kolejkę
- Algorytm dla Dequeue:
if(FRONT == NULL) // Warunek niedopełnienia
Drukuj „Przepełnienie kolejki”
zakończ kolejkowanie
koniec jeśli
else if(FRONT == REAR) // Kolejka zawiera tylko jeden węzeł
temp = PRZÓD -> dane
wolny (tymczasowy)
PRZÓD = PRZÓD -> następny
TYŁ -> następny = PRZÓD
koniec jeśli
else if (FRONT == N – 1) // Jeśli FRONT jest ostatnim węzłem
front = 0 // Ustaw FRONT jako pierwszy węzeł
koniec jeśli
zakończ kolejkowanie
Przeczytaj także: Python Vs C: Kompletne porównanie side-by-side
Wniosek
Struktury danych i algorytmy mają ogromne znaczenie nie tylko w programowaniu w C, ale także w innych językach. Jego wartość jest bezprecedensowa, a w przypadku tak ważnych tematów lepiej jest zainwestować w kursy zaprojektowane i prowadzone przez ekspertów, które zapewnią doskonały dodatek do Twojego portfolio. upGrad oferuje szeroką gamę bogatych w moc kursów, które nie tylko poprawiają Twoje umiejętności, ale także budują silne filary podstaw.
Został zaprojektowany przez renomowaną IIIT-B, gdzie nie tylko dostarcza treści najwyższej jakości, ale także sprawia, że jesteś częścią silnej sieci, w której będziesz łączyć się z ludźmi, którzy rozwijają się na tej samej ścieżce kariery, a także z ekspertami branżowymi, którzy rozwiewa Twoje wątpliwości i wspiera Cię za każdym razem.
Pomogłoby ci poznanie ich mentalności i procesu myślowego. A jedną z unikalnych rzeczy, które otrzymujesz w upGrad, jest to, że możesz wybrać opcje EMI i nie obciążać kieszeni.
Mamy nadzieję, że będziesz miał doskonałą okazję do nauki podczas wykonywania tych projektów C. Jeśli chcesz dowiedzieć się więcej i potrzebujesz mentoringu ze strony ekspertów branżowych, zapoznaj się z dyplomem PG upGrad i IIIT Banglore w zakresie programowania pełnego stosu .