c circular queue data structure
Questo tutorial sulla struttura dei dati della coda circolare C ++ spiega cos'è la coda circolare, quali sono le operazioni di base insieme all'implementazione e alle applicazioni:
Una coda circolare è un'estensione della coda di base di cui abbiamo discusso in precedenza. È anche noto come 'Ring buffer'.
Cos'è la coda circolare in C ++?
Una coda circolare è una struttura dati lineare utilizzata per memorizzare elementi di dati. Esegue le operazioni seguendo l'approccio FIFO (First In, First Out) e l'ultima posizione in coda viene ricollegata alla prima posizione per formare un cerchio.
=> Cerca qui l'intera serie di formazione C ++
Cosa imparerai:
Coda circolare in C ++
Il diagramma seguente mostra una coda circolare.
L'immagine sopra mostra una struttura dati circolare di dimensione 10. I primi sei elementi sono già in coda e vediamo che la prima posizione e l'ultima posizione sono unite. A causa di questa disposizione, lo spazio non va sprecato come accade in una coda lineare.
migliore app per schede attività per più dipendenti
In una coda lineare dopo che la coda è piena, eliminiamo gli elementi da un'altra estremità e lo stato della coda viene ancora mostrato come pieno e non possiamo inserire più elementi.
Nella coda circolare, quando la coda è piena, e quando togliamo gli elementi dal fronte poiché l'ultima e la prima posizione sono collegate, possiamo inserire gli elementi sul retro che è stato liberato cancellando l'elemento.
Nella sezione successiva, impareremo le operazioni di base della coda circolare.
Operazioni di base
Alcune delle operazioni di base della coda circolare sono le seguenti:
Davanti: Restituisce la prima posizione nella coda circolare.
Posteriore: Restituisce la posizione posteriore nella coda circolare.
Accodare: Enqueue (valore) viene utilizzato per inserire un elemento nella coda circolare. L'elemento è sempre inserito in fondo alla coda.
Seguiamo la seguente sequenza di passaggi per inserire un nuovo elemento nella coda circolare.
# 1) Controlla se la coda circolare è piena: test ((rear == SIZE-1 && front == 0) || (rear == front-1)), dove 'SIZE' è la dimensione della coda circolare.
#Due) Se la coda circolare è piena, viene visualizzato un messaggio come 'La coda è piena'. Se la coda non è piena, controlla se (rear == SIZE - 1 && front! = 0). Se è vero, impostare rear = 0 e inserire l'elemento.
Dequeue: La funzione Dequeue viene utilizzata per eliminare un elemento dalla coda. Nella coda circolare, l'elemento viene sempre eliminato dal front-end. Di seguito è riportata la sequenza per l'operazione di rimozione dalla coda in una coda circolare.
Passaggi:
# 1) Controlla se la coda circolare è vuota: controlla se (front == - 1).
quale downloader di video mp4 è compatibile con youtube
#Due) Se è vuoto, visualizzare il messaggio 'La coda è vuota'. Se la coda non è vuota, eseguire il passaggio 3.
# 3) Verificare se (anteriore == posteriore). Se è vero allora imposta front = rear = -1 altrimenti controlla se (front == size-1), se è vero allora imposta front = 0 e restituisce l'elemento.
Illustrazione
In questa sezione, esamineremo un'illustrazione dettagliata dell'aggiunta / rimozione di elementi nella coda circolare.
Considera la seguente coda circolare di 5 elementi come mostrato di seguito:
Successivamente, inseriamo l'elemento 1 nella coda.
Successivamente, inseriamo un elemento con valore 3.
Quando inseriamo gli elementi per riempire una coda, la rappresentazione sarà come quella mostrata di seguito.
Ora eliminiamo i due elementi, ovvero l'elemento 1 e l'elemento 3, dalla coda come mostrato di seguito.
Successivamente, inseriamo o accodiamo l'elemento 11 nella coda circolare come rappresentato di seguito.
Inseriamo nuovamente l'elemento 13 nella coda circolare. La coda apparirà come mostrato di seguito.
Vediamo che nella coda circolare spostiamo o inseriamo elementi in un cerchio. Quindi possiamo consumare l'intero spazio della coda fino a quando non si riempie.
Implementazione
Implementiamo la coda circolare utilizzando 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< Sopra è mostrato l'output delle operazioni di coda circolare. Innanzitutto, aggiungiamo gli elementi e quindi rimuoviamo dalla coda o rimuoviamo due elementi. Successivamente, inseriamo o accodiamo altri tre elementi nella coda circolare. Vediamo che a differenza della coda lineare, gli elementi vengono aggiunti alla fine della coda.
Implementazione di elenchi collegati
Parliamo ora dell'implementazione dell'elenco collegato di una coda circolare. Di seguito è riportata l'implementazione dell'elenco collegato della coda circolare in C ++. Nota che usiamo struct per rappresentare ogni nodo. Le operazioni sono le stesse discusse prima tranne che in questo caso, dobbiamo eseguirle rispetto ai nodi della lista collegata.
L'output mostra la coda circolare dopo l'operazione di accodamento, rimozione dalla coda e anche dopo la seconda operazione di accodamento.
#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: '< Produzione:
L'implementazione successiva è un programma Java per dimostrare la coda circolare utilizzando l'elenco collegato.
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); } } Produzione:
L'output del programma precedente è simile al programma precedente.
Applicazioni
Parliamo di alcune delle applicazioni della coda circolare.
- Pianificazione della CPU: Il processo del sistema operativo che richiede il verificarsi di alcuni eventi o il completamento di altri processi per l'esecuzione viene spesso mantenuto in una coda circolare in modo che vengano eseguiti uno dopo l'altro quando tutte le condizioni sono soddisfatte o quando si verificano tutti gli eventi.
- Gestione della memoria: L'uso di code ordinarie spreca spazio di memoria come già accennato nella nostra discussione precedente. L'utilizzo di una coda circolare per la gestione della memoria è utile per un utilizzo ottimale della memoria.
- Sistema di segnali stradali controllati da computer: I segnali stradali computerizzati vengono spesso aggiunti a una coda circolare in modo che si ripetano dopo che è trascorso l'intervallo di tempo specificato.
Conclusione
Le code circolari risolvono il principale svantaggio di una coda normale in cui non possiamo inserire elementi quando il puntatore posteriore è alla fine della coda anche quando cancelliamo gli elementi e lo spazio viene svuotato. In una coda circolare, gli elementi sono disposti in modo circolare, in modo che lo spazio non venga affatto sprecato.
Abbiamo anche visto le principali operazioni della coda circolare. Le code circolari sono principalmente utili per scopi di pianificazione e applicazioni come i sistemi di segnali stradali in cui i segnali si illuminano a turno.
tutorial elenco collegato c ++
Nel nostro prossimo tutorial, impareremo a conoscere le code a doppia estremità che sono semplicemente chiamate 'deque'.
=> Visita qui per imparare il C ++ da zero
Lettura consigliata
- Struttura dei dati della coda in C ++ con illustrazione
- Priorità Struttura Dati Coda In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
- Tutorial sul data mart - Tipi, esempi e implementazione del data mart
- Stack Struttura Dati In C ++ Con Illustrazione
- Esempi di data mining: applicazioni più comuni del data mining 2021
- Struttura dei dati dell'albero binario in C ++
- Coda prioritaria in AWL
