c circular queue data structure
Aquest tutorial sobre l'estructura de dades de la cua circular de C ++ explica què és la cua circular, quines són les operacions bàsiques juntament amb la implementació i les aplicacions:
Una cua circular és una extensió de la cua bàsica que hem comentat anteriorment. També es coneix com 'Ring buffer'.
Què és la cua circular a C ++?
Una cua circular és una estructura de dades lineal que s’utilitza per emmagatzemar elements de dades. Realitza operacions seguint l’enfocament FIFO (First In, First Out) i l’última posició de la cua es torna a connectar a la primera posició per formar un cercle.
=> Cerqueu aquí tota la sèrie de formació C ++
Què aprendreu:
Cua circular a C ++
El diagrama següent mostra una cua circular.
La imatge anterior mostra una estructura circular de dades de mida 10. Els primers sis elements ja estan a la cua i veiem que la primera posició i l'última posició estan units. A causa d’aquest arranjament, l’espai no es perd com passa en una cua lineal.
llocs gratuïts de transmissió d’anime en anglès doblats
En una cua lineal després que la cua estigui plena, suprimim els elements d'un altre extrem i l'estat de la cua es mostra com a ple i no podem inserir més elements.
A la cua circular, quan la cua està plena i quan traiem elements de la part davantera ja que hi ha connectades les darreres i primeres posicions, podem inserir els elements de la part posterior que es van deixar eliminant l'element.
A la secció següent, coneixerem les operacions bàsiques de la cua circular.
Operacions bàsiques
Algunes de les operacions bàsiques de la cua circular són les següents:
Davant: Retorna la posició frontal a la cua circular.
Posterior: Retorna la posició posterior a la cua circular.
Posada a la cua: Enqueue (valor) s’utilitza per inserir un element a la cua circular. L'element sempre s'insereix a la part posterior de la cua.
Seguim la següent seqüència de passos per inserir un element nou a la cua circular.
# 1) Comproveu si la cua circular està plena: prova ((posterior == SIZE-1 && frontal == 0) || (posterior == frontal-1)), on 'SIZE' és la mida de la cua circular.
# 2) Si la cua circular està plena, es mostrarà un missatge com a 'La cua està plena'. Si la cua no està plena, comproveu si (posterior == SIZE - 1 && frontal! = 0). Si és cert, definiu rear = 0 i inseriu l'element.
Retardar: La funció Dequeue s’utilitza per suprimir un element de la cua. A la cua circular, l'element sempre se suprimeix de la part frontal. A continuació es mostra la seqüència d’operació de cola en una cua circular.
Passos:
# 1) Comproveu si la cua circular és buida: comproveu si (frontal == - 1).
# 2) Si està buit, mostreu el missatge 'La cua està buida'. Si la cua no està buida, seguiu el pas 3.
# 3) Comproveu si (davant == posterior). Si és cert, definiu front = darrere = -1, comproveu si (frontal == mida-1), si és cert, definiu front = 0 i torneu l'element.
Il·lustració
En aquesta secció, veurem una il·lustració detallada d’afegir / eliminar elements a la cua circular.
com ordenar una matriu a Java
Penseu en la següent cua circular de 5 elements com es mostra a continuació:
A continuació, inserim l’element 1 a la cua.
A continuació, inserim un element amb el valor 3.
Quan inserim els elements per fer una cua plena, la representació serà la que es mostra a continuació.
Ara suprimim els dos elements, és a dir, l’element 1 i l’element 3 de la cua, tal com es mostra a continuació.
A continuació, inserim o col·loquem l'element 11 a la cua circular tal com es representa a continuació.
De nou, inserim l'element 13 a la cua circular. La cua es veurà com es mostra a continuació.
Veiem que a la cua circular movem o inserim elements en un cercle. Per tant, podem consumir tot l’espai de la cua fins que s’ompli.
Implementació
Implantem la cua circular amb 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< A la part superior es mostra la sortida de les operacions de cua circular. Primer, afegim els elements i, a continuació, retirem o eliminem dos elements. A continuació, inserim o posem en cua tres elements més a la cua circular. Veiem que, a diferència de la cua lineal, els elements s’afegeixen al final de la cua.
Implementació de la llista enllaçada
Analitzem ara la implementació de la llista enllaçada d’una cua circular. A continuació es mostra la implementació de la llista enllaçada de la cua circular en C ++. Tingueu en compte que fem ús de l’estructura per representar cada node. Les operacions són les mateixes que s’ha comentat abans, excepte que en aquest cas les hem de realitzar respecte als nodes de llista enllaçats.
La sortida mostra la cua circular després de l'operació de cola, cola i també després de la segona operació de cola.
#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: '< Sortida:
La següent implementació és un programa Java per demostrar cua circular mitjançant la llista enllaçada.
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); } } Sortida:
La sortida del programa anterior és similar al programa anterior.
Aplicacions
Analitzem algunes de les aplicacions de la cua circular.
- Programació de la CPU: El procés del sistema operatiu que requereix que es produeixi algun esdeveniment o que es completi algun altre procés per executar-se sovint es manté en una cua circular de manera que s’executin un darrere l’altre quan es compleixen totes les condicions o quan es produeixen tots els esdeveniments.
- Gestió de la memòria: L'ús de cues ordinàries malgasta l'espai de memòria, com ja s'ha esmentat a la discussió anterior. L’ús d’una cua circular per a la gestió de la memòria és beneficiós per a un ús òptim de la memòria.
- Sistema de senyal de trànsit controlat per ordinador: Sovint s’afegeixen senyals de trànsit informatitzats a una cua circular perquè es repeteixin després que hagi transcorregut l’interval de temps especificat.
Conclusió
Les cues circulars solucionen el principal desavantatge d'una cua normal en què no podem inserir elements quan el punter posterior es troba al final de la cua, fins i tot quan suprimim els elements i es buida l'espai. En una cua circular, els elements es disposen de manera circular, de manera que l’espai no es malgasta en absolut.
També hem vist les principals operacions de la cua circular. Les cues circulars són útils sobretot per a la planificació d’aplicacions i aplicacions com els sistemes de senyals de trànsit on els senyals brillen per torns.
com muntar fitxers .bin
Al nostre següent tutorial, coneixerem les cues de doble punt que simplement es diuen 'deque'.
=> Visiteu aquí per aprendre C ++ des de zero
Lectura recomanada
- Estructura de dades de la cua en C ++ amb il·lustració
- Estructura de dades de la cua de prioritat en C ++ amb il·lustració
- Estructura de dades de llistes enllaçades circulars en C ++ amb il·lustració
- Tutorial de Data Mart: tipus, exemples i implementació de Data Mart
- Estructura de dades de pila en C ++ amb il·lustració
- Exemples de mineria de dades: aplicacions més habituals de mineria de dades 2021
- Estructura de dades de l'arbre binari en C ++
- Cua de prioritat a STL
