c circular queue data structure
Tento výukový program o štruktúre údajov kruhového frontu C ++ vysvetľuje, čo je kruhový front, aké sú základné operácie spolu s implementáciou a aplikáciami:
Kruhový rad je rozšírením základného radu, o ktorom sme hovorili už skôr. Je tiež známy ako „Ring buffer“.
Čo je to kruhový rad v C ++?
Kruhový front je lineárna dátová štruktúra, ktorá sa používa na ukladanie dátových položiek. Vykonáva operácie sledovaním prístupu FIFO (prvý vstup, prvý výstup) a posledná pozícia vo fronte je spojená späť s prvou pozíciou a vytvára kruh.
=> Celú sériu školení pre C ++ nájdete tu
Čo sa dozviete:
Kruhový rad v C ++
Nasledujúci diagram zobrazuje kruhový rad.
Vyššie uvedený obrázok zobrazuje kruhovú dátovú štruktúru veľkosti 10. Prvých šesť prvkov je už vo fronte a vidíme, že sú spojené prvá a posledná pozícia. Vďaka tomuto usporiadaniu nezostane zbytočne stratený priestor, ako to býva v lineárnom rade.
čím otvoriť súbory jar
V lineárnom rade po zaplnení frontu odstránime prvky z iného konca a stav frontu sa bude stále zobrazovať ako plný a nemôžeme vložiť viac prvkov.
Keď je v kruhovom fronte plný rad, a keď odstránime prvky spredu, pretože sú spojené posledné a prvé polohy, môžeme vložiť prvky zozadu, ktoré sa uvoľnili odstránením prvku.
V nasledujúcej časti sa dozvieme základné operácie kruhového frontu.
Základné operácie
Niektoré zo základných operácií kruhového frontu sú tieto:
Predná strana: Vráti prednú pozíciu v kruhovom poradí.
Zadný: Vráti zadnú pozíciu v kruhovom poradí.
Poradie: Poradie (hodnota) sa používa na vloženie prvku do kruhového poradia. Element je vždy vložený na zadný koniec frontu.
Pri vkladaní nového prvku do kruhového poradia postupujeme podľa nasledujúcej postupnosti krokov.
# 1) Skontrolujte, či je kruhový rad plný: test ((zadný == SIZE-1 && predný == 0) || (zadný == predný-1)), kde „SIZE“ predstavuje veľkosť kruhového poradia.
#dva) Ak je kruhový front plný, zobrazí sa správa „Fronta je plná“. Ak poradie nie je plné, skontrolujte, či (zadné == VEĽKOSŤ - 1 && predné! = 0). Ak je to pravda, nastavte zadné = 0 a vložte prvok.
Poradie: Funkcia dequeue sa používa na odstránenie prvku z frontu. V kruhovom poradí je prvok vždy odstránený z klientskeho rozhrania. Ďalej je uvedená postupnosť operácie dequeue v kruhovom rade.
Kroky:
internet vecí, na ktoré sa majú spoločnosti pozerať
# 1) Skontrolujte, či je kruhový rad prázdny: skontrolujte, či (front == - 1).
#dva) Ak je prázdny, zobrazí sa správa „Fronta je prázdna“. Ak poradie nie je prázdne, vykonajte krok 3.
# 3) Skontrolujte, či (vpredu == vzadu). Ak je to pravda, potom nastavte predok = zadok = -1 inak skontrolujte, či (predok == veľkosť-1), ak je to pravda, potom nastavte predok = 0 a vráťte prvok.
Ilustrácia
V tejto časti si prejdeme podrobnou ilustráciou pridávania / odstraňovania prvkov v kruhovom rade.
Zvážte nasledujúci kruhový rad 5 prvkov, ako je uvedené nižšie:
Ďalej vložíme položku 1 do poradia.
Ďalej vložíme položku s hodnotou 3.
Keď vložíme prvky, aby sa fronta zaplnila, bude znázornené, ako je znázornené nižšie.
Teraz odstránime dva prvky, tj. Položku 1 a položku 3, z frontu, ako je uvedené nižšie.
Ďalej vložíme alebo zaradíme prvok 11 do kruhového radu, ako je znázornené nižšie.
Opäť vložíme prvok 13 do kruhového radu. Poradie bude vyzerať nasledovne.
Vidíme, že v kruhovom rade posúvame alebo vkladáme prvky do kruhu. Preto môžeme spotrebovať celý priestor frontu, kým sa nezaplní.
Implementácia
Implementujme kruhový rad pomocou 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< Vyššie je znázornený výstup operácií kruhového frontu. Najskôr pridáme prvky a potom dva prvky vyradíme alebo odstránime. Ďalej do kruhového poradia vložíme alebo zaradíme ďalšie tri prvky. Vidíme, že na rozdiel od lineárneho radu sa prvky pridávajú na koniec radu.
Implementácia prepojeného zoznamu
Pozrime sa teraz na implementáciu prepojeného zoznamu kruhového frontu. Ďalej je uvedená implementácia prepojeného zoznamu kruhového frontu v C ++. Upozorňujeme, že na zastupovanie každého uzla používame štruktúru struct. Operácie sú rovnaké, ako už bolo uvedené predtým, s výnimkou toho, že v tomto prípade ich musíme vykonať s ohľadom na uzly prepojeného zoznamu.
Výstup zobrazuje kruhovú frontu po operácii zaradenia, zaradenia a tiež po druhej operácii zaradenia.
#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: '< Výkon:
Ďalšou implementáciou je program Java na demonštráciu kruhového poradia pomocou prepojeného zoznamu.
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); } } Výkon:
Výstup vyššie uvedeného programu je podobný predchádzajúcemu programu.
Aplikácie
Poďme sa rozprávať o niektorých aplikáciách kruhového frontu.
- Plánovanie CPU: Proces operačného systému, ktorý vyžaduje, aby sa na vykonanie vyskytla nejaká udalosť alebo aby sa niektoré ďalšie procesy dokončili, je často udržiavaný v kruhovom rade, aby sa vykonávali jeden po druhom, keď sú splnené všetky podmienky alebo keď nastanú všetky udalosti.
- Správa pamäte: Používaním bežných radov sa míňa pamäťový priestor, ako už bolo spomenuté v našej diskusii vyššie. Používanie kruhového frontu na správu pamäte je prospešné pre optimálne využitie pamäte.
- Počítačom riadený systém dopravných signálov: Počítačové dopravné signály sa často pridávajú do kruhového radu, aby sa opakovali po uplynutí zadaného časového intervalu.
Záver
Kruhové fronty opravujú hlavnú nevýhodu normálneho frontu, keď nemôžeme vkladať prvky, keď je zadný ukazovateľ na konci frontu, aj keď prvky vymažeme a priestor sa vyprázdni. V kruhovej rade sú prvky usporiadané do kruhovej podoby, aby vôbec nedochádzalo k plytvaniu priestorom.
Boli sme tiež svedkami hlavných operácií kruhového frontu. Kruhové fronty sú väčšinou užitočné na účely plánovania a aplikácie, ako sú systémy dopravných signálov, kde signály svietia striedavo.
ako deklarovať front v jave
V našom ďalšom tutoriále sa dozvieme o obojstranných radoch, ktoré sa jednoducho nazývajú „deque“.
=> Navštívte tu a naučte sa C ++ od nuly
Odporúčané čítanie
- Dátová štruktúra frontu v C ++ s ilustráciou
- Štruktúra dát prioritného frontu v C ++ s ilustráciou
- Dátová štruktúra kruhového prepojeného zoznamu v C ++ s ilustráciou
- Výukový program Data Mart - Typy, príklady a implementácia Data Mart
- Skladať dátovú štruktúru v C ++ s ilustráciou
- Príklady dolovania dát: Najčastejšie aplikácie dolovania dát 2021
- Štruktúra dát binárneho stromu v C ++
- Prioritný front v STK
