c circular queue data structure
Acest tutorial despre structura de date a cozii circulare C ++ explică ce este coada circulară, care sunt operațiunile de bază împreună cu implementarea și aplicațiile:
O coadă circulară este o extensie a cozii de bază despre care am discutat mai devreme. Este, de asemenea, cunoscut sub numele de „Ring buffer”.
Ce este coada circulară în C ++?
O coadă circulară este o structură de date liniară care este utilizată pentru a stoca elemente de date. Efectuează operațiuni urmând abordarea FIFO (First In, First Out) și ultima poziție din coadă este conectată înapoi la prima poziție pentru a forma un cerc.
=> Căutați întreaga serie de formare C ++ aici
Ce veți învăța:
Coadă circulară în C ++
Următoarea diagramă arată o coadă circulară.
Imaginea de mai sus prezintă o structură circulară de date de mărimea 10. Primele șase elemente sunt deja în coadă și vedem că prima poziție și ultima poziție sunt unite. Datorită acestui aranjament, spațiul nu se pierde, așa cum se întâmplă într-o coadă liniară.
aplicații pentru a spiona un alt telefon
Într-o coadă liniară după ce coada este plină, ștergem elementele de la un alt capăt, iar starea cozii este încă afișată ca plină și nu putem insera mai multe elemente.
În coada circulară, când coada este plină și când scoatem elemente din față, deoarece ultimele și primele poziții sunt conectate, putem insera elementele din spate, care au fost eliberate, ștergând elementul.
În secțiunea următoare, vom afla despre operațiunile de bază ale cozii circulare.
Operațiuni de bază
Unele dintre operațiile de bază ale cozii circulare sunt după cum urmează:
Față: Returnează poziția frontală în coada circulară.
Spate: Returnează poziția din spate în coada circulară.
Strângeți: Enqueue (valoare) este folosit pentru a insera un element în coada circulară. Elementul este întotdeauna inserat în partea din spate a cozii.
Urmăm următoarea secvență de pași pentru a insera un element nou în coada circulară.
# 1) Verificați dacă coada circulară este plină: test ((spate == SIZE-1 && front == 0) || (spate == front-1)), unde „SIZE” este dimensiunea cozii circulare.
#Două) Dacă coada circulară este plină, atunci se afișează un mesaj ca „Coada este plină”. Dacă coada nu este plină, verificați dacă (spate == SIZE - 1 && față! = 0). Dacă este adevărat, atunci setați spatele = 0 și introduceți elementul.
Stoarceți: Funcția Dequeue este utilizată pentru a șterge un element din coadă. În coada circulară, elementul este întotdeauna șters din partea frontală. Dat mai jos este secvența pentru operația de coadă într-o coadă circulară.
Pași:
# 1) Verificați dacă coada circulară este goală: verificați dacă (față == - 1).
#Două) Dacă este gol, afișați mesajul „Coada este goală”. Dacă coada nu este goală, efectuați pasul 3.
# 3) Verificați dacă (față == spate). Dacă este adevărat, atunci setați față = spate = -1 altfel verificați dacă (față == dimensiune-1), dacă este adevărat, setați față = 0 și returnați elementul.
Ilustrare
În această secțiune, vom trece printr-o ilustrare detaliată a adăugării / eliminării elementelor în coada circulară.
Luați în considerare următoarea coadă circulară de 5 elemente, așa cum se arată mai jos:
Apoi, inserăm elementul 1 în coadă.
Apoi, inserăm un element cu valoarea 3.
char la șir c ++
Când inserăm elementele pentru a face o coadă plină, reprezentarea va fi așa cum se arată mai jos.
Acum ștergem cele două elemente, adică elementul 1 și elementul 3 din coadă așa cum se arată mai jos.
Apoi, inserăm sau scoatem coada elementului 11 în coada circulară, așa cum este reprezentat mai jos.
Din nou, să introducem elementul 13 în coada circulară. Coada va arăta așa cum se arată mai jos.
Vedem că în coada circulară mișcăm sau inserăm elemente într-un cerc. Prin urmare, putem consuma întregul spațiu al cozii până devine plin.
Implementare
Să implementăm coada circulară folosind 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< Mai sus este prezentată ieșirea operațiilor de coadă circulare. Mai întâi, adăugăm elementele și apoi scoatem sau eliminăm două elemente. Apoi, introducem sau stoarcem încă trei elemente în coada circulară. Vedem că, spre deosebire de coada liniară, elementele sunt adăugate la sfârșitul cozii.
Implementarea listei legate
Să discutăm acum implementarea listei legate de o coadă circulară. Dat mai jos este implementarea listei legate a cozii circulare în C ++. Rețineți că folosim struct pentru a reprezenta fiecare nod. Operațiunile sunt aceleași cu cele discutate anterior, cu excepția faptului că, în acest caz, trebuie să le efectuăm cu privire la nodurile listei legate.
Ieșirea arată coada circulară după operația de coadă, dequeue și, de asemenea, după a doua operație de coadă.
#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: '< Ieșire:
Următoarea implementare este un program Java pentru a demonstra coada circulară utilizând lista legată.
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); } } Ieșire:
Rezultatul programului de mai sus este similar cu programul anterior.
Aplicații
Să discutăm câteva dintre aplicațiile cozii circulare.
- Programare CPU: Procesul sistemului de operare care necesită un anumit eveniment sau pentru finalizarea altor procese pentru executare este adesea menținut într-o coadă circulară, astfel încât să se execute unul după altul atunci când sunt îndeplinite toate condițiile sau când apar toate evenimentele.
- Gestionarea memoriei: Utilizarea cozilor obișnuite risipește spațiul de memorie așa cum sa menționat deja în discuția noastră de mai sus. Utilizarea unei cozi circulare pentru gestionarea memoriei este benefică pentru utilizarea optimă a memoriei.
- Sistem de semnal de trafic controlat de computer: Semnalele de trafic computerizate sunt adesea adăugate la o coadă circulară, astfel încât să se repete după ce a trecut intervalul de timp specificat.
Concluzie
Cozile circulare remediază dezavantajul major al unei cozi normale în care nu putem insera elemente atunci când indicatorul din spate se află la sfârșitul cozii chiar și atunci când ștergem elementele și spațiul este golit. Într-o coadă circulară, elementele sunt aranjate într-un mod circular, astfel încât spațiul să nu fie irosit deloc.
De asemenea, am văzut operațiunile majore ale cozii circulare. Cozile circulare sunt de cele mai multe ori utile în scopuri de programare și aplicații precum sistemele de semnalizare a traficului în care semnalele strălucesc pe rând.
cum să testezi stiloul pe un site web
În următorul nostru tutorial, vom afla despre cozile cu două capete care sunt pur și simplu numite „deque”.
=> Vizitați aici pentru a afla C ++ de la zero
Lectură recomandată
- Structura datelor în coadă în C ++ cu ilustrație
- Structura de date a cozii prioritare în C ++ cu ilustrație
- Structură de date cu listă circulară legată în C ++ cu ilustrație
- Tutorial Data Mart - Tipuri, exemple și implementarea Data Mart
- Stivați structura datelor în C ++ cu ilustrație
- Exemple de minerit de date: cele mai frecvente aplicații ale mineritului de date 2021
- Structura de date a arborelui binar în C ++
- Coadă prioritară în STL
