c circular queue data structure
Ten samouczek dotyczący struktury danych kolejki cyklicznej w języku C ++ wyjaśnia, czym jest kolejka cykliczna, jakie są podstawowe operacje wraz z implementacją i aplikacjami:
Kolejka cykliczna to rozszerzenie podstawowej kolejki, o której mówiliśmy wcześniej. Znany jest również jako „bufor pierścieniowy”.
Co to jest kolejka cykliczna w C ++?
Kolejka cykliczna to liniowa struktura danych używana do przechowywania elementów danych. Wykonuje operacje zgodnie z podejściem FIFO (First In, First Out), a ostatnia pozycja w kolejce jest połączona z powrotem z pierwszą pozycją, tworząc okrąg.
=> Poszukaj całej serii szkoleń C ++ tutaj
Czego się nauczysz:
Cykliczna kolejka w C ++
Poniższy diagram przedstawia kolejkę cykliczną.
Powyższy obrazek przedstawia okrągłą strukturę danych o rozmiarze 10. Sześć pierwszych elementów jest już w kolejce i widzimy, że pierwsza pozycja i ostatnia pozycja są połączone. Dzięki takiemu rozmieszczeniu przestrzeń nie jest marnowana, jak to ma miejsce w liniowej kolejce.
jak utworzyć podwójnie połączoną listę w java
W kolejce liniowej po zapełnieniu kolejki usuwamy elementy z innego końca, a stan kolejki nadal jest wyświetlany jako pełny i nie możemy wstawić kolejnych elementów.
W kolejce cyklicznej, gdy kolejka jest pełna, a gdy usuwamy elementy z przodu, ponieważ ostatnia i pierwsza pozycja są połączone, możemy wstawić elementy z tyłu, które zostały zwolnione, usuwając element.
W następnej sekcji dowiemy się o podstawowych operacjach kolejki cyklicznej.
Podstawowe operacje
Niektóre z podstawowych operacji kolejki cyklicznej są następujące:
Z przodu: Zwraca pierwszą pozycję w kolejce cyklicznej.
Tylny: Zwraca tylną pozycję w kolejce cyklicznej.
Dodaj do kolejki: Enqueue (wartość) służy do wstawiania elementu do kolejki cyklicznej. Element jest zawsze wstawiany na końcu kolejki.
Postępujemy zgodnie z następującą sekwencją kroków, aby wstawić nowy element do kolejki cyklicznej.
# 1) Sprawdź, czy kolejka cykliczna jest pełna: test ((tył == ROZMIAR-1 && przód == 0) || (tył == przód-1)), gdzie „ROZMIAR” to rozmiar kolejki cyklicznej.
#dwa) Jeśli kolejka cykliczna jest pełna, wyświetla komunikat „Kolejka jest pełna”. Jeśli kolejka nie jest pełna, sprawdź, czy (tył == ROZMIAR - 1 && przód! = 0). Jeśli to prawda, ustaw wartość rear = 0 i wstaw element.
Dequeue: Funkcja Dequeue służy do usuwania elementu z kolejki. W kolejce cyklicznej element jest zawsze usuwany z interfejsu użytkownika. Poniżej podano kolejność operacji usuwania z kolejki w kolejce cyklicznej.
Kroki:
# 1) Sprawdź, czy kolejka cykliczna jest pusta: sprawdź, czy (przód == - 1).
#dwa) Jeśli jest pusta, wyświetl komunikat „Kolejka jest pusta”. Jeśli kolejka nie jest pusta, wykonaj krok 3.
# 3) Sprawdź, czy (przód == tył). Jeśli to prawda, ustaw front = rear = -1 w przeciwnym razie sprawdź, czy (front == size-1), jeśli to prawda, ustaw front = 0 i zwróć element.
Ilustracja
W tej sekcji omówimy szczegółową ilustrację dodawania / usuwania elementów w kolejce cyklicznej.
Rozważ następującą kolejkę cykliczną składającą się z 5 elementów, jak pokazano poniżej:
Następnie wstawiamy do kolejki element 1.
Następnie wstawiamy element o wartości 3.
Kiedy wstawimy elementy, aby kolejka była pełna, reprezentacja będzie taka, jak pokazano poniżej.
domyślna brama jest niedostępna
Teraz usuwamy dwa elementy, tj. Element 1 i element 3 z kolejki, jak pokazano poniżej.
Następnie wstawiamy lub umieszczamy element 11 w kolejce cyklicznej, jak pokazano poniżej.
Ponownie wstawmy element 13 do kolejki cyklicznej. Kolejka będzie wyglądać tak, jak pokazano poniżej.
Widzimy, że w kolejce kołowej przesuwamy lub wstawiamy elementy w okrąg. Dzięki temu możemy zająć całą przestrzeń kolejki, aż się zapełni.
Realizacja
Zaimplementujmy kolejkę cykliczną w C ++.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< Powyżej pokazano wynik operacji kolejki cyklicznej. Najpierw dodajemy elementy, a następnie usuwamy z kolejki lub dwa elementy. Następnie wstawiamy lub umieszczamy w kolejce trzy kolejne elementy w kolejce cyklicznej. Widzimy, że w przeciwieństwie do kolejki liniowej elementy są dodawane na końcu kolejki.
Implementacja powiązanej listy
Omówmy teraz połączoną implementację listy w kolejce cyklicznej. Poniżej podano połączoną implementację listy kolejki cyklicznej w C ++. Zauważ, że używamy struktury struct do reprezentowania każdego węzła. Operacje są takie same, jak omówione wcześniej, z tym wyjątkiem, że w tym przypadku musimy je wykonać w odniesieniu do połączonych węzłów list.
Dane wyjściowe pokazują kolejkę cykliczną po operacji umieszczenia w kolejce, po usunięciu z kolejki, a także po drugiej operacji umieszczania w kolejce.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< Wynik:
Następną implementacją jest program Java, który demonstruje kolejkę cykliczną za pomocą połączonej listy.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } Wynik:
Wynik powyższego programu jest podobny do poprzedniego programu.
Aplikacje
Omówmy niektóre zastosowania kolejki cyklicznej.
- Harmonogram procesora: Proces systemu operacyjnego, który wymaga wystąpienia jakiegoś zdarzenia lub zakończenia innych procesów w celu wykonania, jest często utrzymywany w kolejce cyklicznej, tak aby były wykonywane jeden po drugim, gdy spełnione są wszystkie warunki lub gdy wystąpią wszystkie zdarzenia.
- Zarządzanie pamięcią: Korzystanie ze zwykłych kolejek powoduje marnowanie miejsca w pamięci, jak już wspomniano w naszej powyższej dyskusji. Używanie kolejki cyklicznej do zarządzania pamięcią jest korzystne dla optymalnego wykorzystania pamięci.
- System sygnalizacji świetlnej sterowany komputerowo: Skomputeryzowane sygnały drogowe są często dodawane do kolejki cyklicznej, aby powtarzały się po upływie określonego czasu.
Wniosek
Kolejki cykliczne naprawiają główną wadę normalnej kolejki, w której nie możemy wstawiać elementów, gdy tylny wskaźnik znajduje się na końcu kolejki, nawet gdy usuwamy elementy, a miejsce jest opróżniane. W kolistej kolejce elementy są ułożone okrężnie, dzięki czemu przestrzeń w ogóle nie jest marnowana.
Widzieliśmy również główne operacje kolejki cyklicznej. Kolejki cykliczne są głównie przydatne do celów planowania i zastosowań, takich jak systemy sygnalizacji świetlnej, w których sygnały świecą na zmianę.
różnica między testowaniem obciążenia a testowaniem wydajności
W następnym samouczku dowiemy się o podwójnych kolejkach, które są po prostu nazywane „deque”.
=> Odwiedź tutaj, aby nauczyć się C ++ od podstaw
rekomendowane lektury
- Struktura danych kolejki w C ++ z ilustracjami
- Struktura danych kolejki priorytetowej w C ++ z ilustracją
- Struktura danych listy połączonej cyklicznie w C ++ z ilustracją
- Data Mart Tutorial - Rodzaje, przykłady i implementacja Data Mart
- Struktura danych stosu w C ++ z ilustracjami
- Przykłady eksploracji danych: najczęstsze zastosowania eksploracji danych 2021
- Struktura danych drzewa binarnego w C ++
- Kolejka priorytetowa w STL
