c circular queue data structure
Tento kurz o datové struktuře kruhové fronty C ++ vysvětluje, co je kruhová fronta, jaké jsou základní operace spolu s implementací a aplikacemi:
Kruhová fronta je rozšířením základní fronty, o které jsme hovořili dříve. Je také známý jako „Ring buffer“.
Co je kruhová fronta v C ++?
Kruhová fronta je lineární datová struktura, která se používá k ukládání datových položek. Provádí operace sledováním přístupu FIFO (First In, First Out) a poslední pozice ve frontě je spojena zpět s první pozicí a tvoří kruh.
=> Podívejte se na celou sérii školení C ++ zde
Co se naučíte:
Kruhová fronta v C ++
Následující diagram ukazuje kruhovou frontu.
Výše uvedený obrázek ukazuje kruhovou datovou strukturu o velikosti 10. Prvních šest prvků je již ve frontě a vidíme, že jsou spojeny první pozice a poslední pozice. Díky tomuto uspořádání nedochází k plýtvání prostorem, jak se to děje v lineární frontě.
příkaz sort v Linuxu s příklady
V lineární frontě po zaplnění fronty odstraníme prvky z jiného konce a stav fronty je stále zobrazen jako plný a nemůžeme vložit více prvků.
Když je v kruhové frontě plná fronta a když odstraníme prvky zepředu, protože jsou spojeny poslední a první pozice, můžeme vložit prvky vzadu, které se uvolnily odstraněním prvku.
V další části se dozvíme základní operace kruhové fronty.
Základní operace
Některé ze základních operací kruhové fronty jsou následující:
Přední: Vrátí přední pozici v kruhové frontě.
Zadní: Vrátí zadní pozici v kruhové frontě.
Zařadit do fronty: Enqueue (hodnota) se používá k vložení prvku do kruhové fronty. Prvek je vždy vložen na zadní konec fronty.
Podle následujícího sledu kroků vložíte nový prvek do kruhové fronty.
# 1) Zkontrolujte, zda je kruhová fronta plná: test ((zadní == SIZE-1 && přední == 0) || (zadní == přední-1)), kde „SIZE“ je velikost kruhové fronty.
#dva) Pokud je kruhová fronta plná, zobrazí se zpráva „Fronta je plná“. Pokud fronta není plná, zkontrolujte, zda (zadní == VELIKOST - 1 && přední! = 0). Pokud je to pravda, nastavte zadní = 0 a vložte prvek.
Dequeue: Funkce dequeue se používá k odstranění prvku z fronty. V kruhové frontě je prvek vždy odstraněn z frontendu. Níže je uvedena sekvence operace dequeue v kruhové frontě.
Kroky:
# 1) Zkontrolujte, zda je kruhová fronta prázdná: zkontrolujte, zda (front == - 1).
#dva) Pokud je prázdná, zobrazí se zpráva „Fronta je prázdná“. Pokud fronta není prázdná, proveďte krok 3.
# 3) Zkontrolujte, zda (přední == zadní). Pokud je to pravda, pak nastavte front = vzadu = -1 jinak zkontrolujte if (front == velikost-1), pokud je to pravda, pak nastavte front = 0 a vraťte prvek.
Ilustrace
V této části projdeme podrobnou ilustraci přidání / odebrání prvků v kruhové frontě.
Zvažte následující kruhovou frontu 5 prvků, jak je znázorněno níže:
pl sql rozhovor otázky a odpovědi
Dále vložíme položku 1 do fronty.
Dále vložíme položku s hodnotou 3.
Když vložíme prvky, aby se fronta zaplnila, bude reprezentace, jak je znázorněno níže.
Nyní odstraníme dva prvky, tj. Položku 1 a položku 3 z fronty, jak je znázorněno níže.
Dále vložíme nebo zařadíme prvek 11 do kruhové fronty, jak je znázorněno níže.
Opět vložme prvek 13 do kruhové fronty. Fronta bude vypadat níže.
Vidíme, že v kruhové frontě posouváme nebo vkládáme prvky do kruhu. Proto můžeme spotřebovat celý prostor fronty, dokud se nezaplní.
Implementace
Pojďme implementovat kruhovou frontu pomocí 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< Nahoře je zobrazen výstup operací kruhové fronty. Nejprve přidáme prvky a poté dva prvky vyřadíme nebo odebereme. Dále vložíme nebo zařadíme do fronty další tři prvky v kruhové frontě. Vidíme, že na rozdíl od lineární fronty se prvky přidávají na konec fronty.
Implementace propojeného seznamu
Pojďme si teď promluvit o implementaci propojeného seznamu kruhové fronty. Níže je uvedena implementace propojeného seznamu kruhové fronty v C ++. Všimněte si, že k reprezentaci každého uzlu používáme strukturu. Operace jsou stejné, jak bylo popsáno dříve, kromě toho, že v tomto případě je musíme provést s ohledem na uzly propojeného seznamu.
Výstup zobrazuje kruhovou frontu po operaci zařazování, řazení a také po druhé operaci zařazování.
#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ýstup:
Další implementací je program Java pro demonstraci kruhové fronty pomocí propojeného seznamu.
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ýstup:
Výstup výše uvedeného programu je podobný předchozímu programu.
Aplikace
Pojďme se bavit o některých aplikacích kruhové fronty.
- Plánování CPU: Proces operačního systému, který vyžaduje, aby došlo k nějaké události nebo aby některé další procesy byly dokončeny, je často udržován v kruhové frontě, aby se spouštěly jeden po druhém, když jsou splněny všechny podmínky nebo když nastanou všechny události.
- Správa paměti: Použití běžných front plýtvá paměťovým prostorem, jak již bylo zmíněno v naší diskusi výše. Použití kruhové fronty pro správu paměti je výhodné pro optimální využití paměti.
- Počítačem řízený systém dopravních signálů: Počítačové dopravní signály se často přidávají do kruhové fronty, aby se opakovaly po uplynutí zadaného časového intervalu.
Závěr
Kruhové fronty opravují hlavní nevýhodu normální fronty, kde nemůžeme vložit prvky, když je zadní ukazatel na konci fronty, i když prvky odstraníme a prostor se vyprázdní. V kruhové frontě jsou prvky uspořádány kruhově, takže prostor není vůbec zbytečný.
Také jsme viděli hlavní operace kruhové fronty. Kruhové fronty jsou většinou užitečné pro účely plánování a aplikace, jako jsou systémy dopravních signálů, kde signály svítí střídavě.
jak otevřít torrent soubor na macu
V našem dalším tutoriálu se dozvíme o frontách s dvojím zakončením, které se jednoduše nazývají „deque“.
=> Navštivte zde a dozvíte se C ++ od nuly
Doporučené čtení
- Struktura dat fronty v C ++ s ilustrací
- Struktura dat prioritní fronty v C ++ s ilustrací
- Datová struktura kruhového propojeného seznamu v C ++ s ilustrací
- Výukový program Data Mart - Typy, příklady a implementace Data Mart
- Skládejte datovou strukturu v C ++ s ilustrací
- Příklady dolování dat: Nejběžnější aplikace dolování dat 2021
- Struktura dat binárního stromu v C ++
- Prioritní fronta v STL
