c circular queue data structure
Ovaj vodič za strukturu podataka kružnog reda za C ++ objašnjava što je kružni red, koje su osnovne operacije uz implementaciju i aplikacije:
Kružni red je produžetak osnovnog reda o kojem smo ranije razgovarali. Poznat je i pod nazivom 'Ring buffer'.
Što je kružni red u C ++-u?
Kružni red je linearna struktura podataka koja se koristi za pohranu podataka. Izvodi operacije slijedeći pristup FIFO (First In, First Out), a posljednja pozicija u redu je spojena natrag na prvu poziciju da formira krug.
=> Ovdje potražite cijelu seriju treninga za C ++
Što ćete naučiti:
Kružni red u C ++
Sljedeći dijagram prikazuje kružni red.
Gornja slika prikazuje kružnu strukturu podataka veličine 10. Prvih šest elemenata već je u redu i vidimo da su prvi i zadnji položaj spojeni. Zbog ovog rasporeda prostor se ne gubi, kao što se događa u linearnom redu.
najbolji youtube u mp3 pretvarač za mac
U linearnom redu nakon što se red napuni, brišemo elemente s drugog kraja, a status reda i dalje se prikazuje kao pun i ne možemo umetnuti više elemenata.
U kružni red, kada je red pun, i kad uklonimo elemente sprijeda budući da su povezani zadnji i prvi položaj, možemo umetnuti elemente straga koji je ispražnjen brisanjem elementa.
U sljedećem odjeljku naučit ćemo o osnovnim operacijama kružnog reda.
Osnovne operacije
Neke od osnovnih operacija kružnog reda su kako slijedi:
Ispred: Vraća prednji položaj u kružnom redu.
Stražnji dio: Vraća stražnji položaj u kružnom redu.
Stanje u red: Enqueue (vrijednost) koristi se za umetanje elementa u kružni red. Element se uvijek umetne na stražnji kraj reda.
Slijedimo sljedeći slijed koraka za umetanje novog elementa u kružni red.
# 1) Provjerite je li kružni red pun: test ((straga == VELIČINA-1 && sprijeda == 0) || (straga == sprijeda-1)), gdje je 'VELIČINA' veličina kružnog reda.
#dva) Ako je kružni red pun, tada se prikazuje poruka 'Red je pun'. Ako red tada nije pun, provjerite je li (straga == VELIČINA - 1 && sprijeda! = 0). Ako je točno, postavite stražnji = 0 i umetnite element.
Dequeue: Dequeue funkcija koristi se za brisanje elementa iz reda. U kružnom redu element se uvijek briše s prednjeg kraja. Dolje je dan redoslijed za uklanjanje iz reda u kružnom redu.
Koraci:
# 1) Provjerite je li kružni red prazan: provjerite je li (sprijeda == - 1).
#dva) Ako je prazno, prikažite poruku 'Red čekanja je prazan'. Ako red nije prazan, izvedite korak 3.
# 3) Provjerite je li (sprijeda == straga). Ako je točno, postavite front = stražnji = -1, inače provjerite je li (front == size-1), ako je točno postavite front = 0 i vratite element.
Ilustracija
U ovom ćemo odjeljku proći detaljnu ilustraciju dodavanja / uklanjanja elemenata u kružnom redu.
Razmotrite sljedeći kružni red od 5 elemenata kao što je prikazano dolje:
Dalje, stavimo stavku 1 u red čekanja.
Zatim umetnemo stavku s vrijednošću 3.
Kada umetnemo elemente kako bismo red ispunili, prikaz će biti kao što je prikazano u nastavku.
Sada brišemo dva elementa, tj. Stavku 1 i stavku 3 iz reda, kako je prikazano u nastavku.
Dalje, umetnemo ili stavimo element 11 u kružni red kako je prikazano u nastavku.
najbolji besplatni DVD ripper za Windows 10
Ponovno umetnimo element 13 u kružni red. Red če izgledati kao što je prikazano u nastavku.
Vidimo da u kružnom redu premještamo ili ubacujemo elemente u krug. Stoga možemo potrošiti čitav prostor reda dok se ne napuni.
Provedba
Primijenimo kružni red koristeći 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< Iznad je prikazan rezultat operacija kružnog reda. Prvo dodamo elemente, a zatim dva elementa uklanjamo iz reda ili uklanjamo iz njih. Zatim u kružni red umetnemo ili stavimo u red još tri elementa. Vidimo da se za razliku od linearnog reda elementi dodaju na kraju reda.
Implementacija povezanog popisa
Razgovarajmo sada o provedbi povezanog popisa kružnog reda. Dolje je dato povezano povezivanje popisa kružnog reda u C ++. Imajte na umu da za predstavljanje svakog čvora koristimo struct. Operacije su iste kao što je prethodno spomenuto, osim što ih u ovom slučaju moramo izvesti s obzirom na povezane čvorove popisa.
Izlaz prikazuje kružni red nakon operacije enqueue, dequeue i također nakon druge operacije enqueue.
#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: '< Izlaz:
Sljedeća je implementacija Java program za demonstraciju kružnog reda pomoću povezanog popisa.
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); } } Izlaz:
Rezultat gornjeg programa sličan je prethodnom programu.
Prijave
Razgovarajmo o nekim primjenama kružnog reda.
- CPU zakazivanje: Proces operativnog sustava koji zahtijeva da se dogodi neki događaj ili da bi neki drugi procesi trebali biti dovršen za izvršenje, često se održava u kružnom redu tako da se izvršavaju jedan za drugim kada su ispunjeni svi uvjeti ili kada se dogode svi događaji.
- Upravljanje memorijom: Korištenje uobičajenih redova troši prostor memorije kao što je već spomenuto u našoj gornjoj raspravi. Korištenje kružnog reda za upravljanje memorijom korisno je za optimalno korištenje memorije.
- Računalno upravljani sustav prometnih signala: Kompjuterizirani prometni signali često se dodaju u kružni red tako da se ponavljaju nakon isteka navedenog vremenskog intervala.
Zaključak
Kružni redovi popravljaju glavni nedostatak normalnog reda u kojem ne možemo umetnuti elemente kada je stražnji pokazivač na kraju reda, čak i kada elemente brišemo i prostor se isprazni. U kružnom redu elementi su poredani kružno, tako da se prostor uopće ne troši.
Također smo vidjeli glavne operacije kružnog reda. Kružni redovi uglavnom su korisni u svrhe raspoređivanja i za aplikacije poput sustava prometne signalizacije gdje signali svijetle u zavojima.
pitanja i odgovori za intervju za selen za iskusne
U sljedećem uputstvu naučit ćemo o dvostrukim redovima koji se jednostavno nazivaju 'deque'.
=> Posjetite ovdje da biste C ++ naučili od nule
Preporučena literatura
- Struktura podataka u redu čekanja u C ++ s ilustracijom
- Struktura podataka prioritetnog reda u C ++ s ilustracijom
- Kružno povezana struktura podataka popisa na C ++ s ilustracijom
- Data Mart Tutorial - Vrste, primjeri i provedba Data Mart
- Složite strukturu podataka u C ++ s ilustracijom
- Primjeri rudarenja podataka: Najčešća primjena rudarenja podataka 2021
- Struktura podataka binarnog stabla u C ++
- Redoslijed prioriteta u STL-u
