c circular queue data structure
Αυτό το σεμινάριο για τη δομή δεδομένων κυκλικής ουράς C ++ εξηγεί τι είναι η κυκλική ουρά, ποιες είναι οι βασικές λειτουργίες μαζί με την εφαρμογή και τις εφαρμογές:
Μια κυκλική ουρά είναι μια επέκταση της βασικής ουράς που έχουμε συζητήσει νωρίτερα. Είναι επίσης γνωστό ως 'Ring buffer'.
Τι είναι η κυκλική ουρά στο C ++;
Η κυκλική ουρά είναι μια γραμμική δομή δεδομένων που χρησιμοποιείται για την αποθήκευση στοιχείων δεδομένων. Εκτελεί λειτουργίες ακολουθώντας την προσέγγιση FIFO (First In, First Out) και η τελευταία θέση στην ουρά συνδέεται πίσω στην πρώτη θέση για να σχηματίσει έναν κύκλο.
=> Αναζητήστε ολόκληρη τη σειρά προπόνησης C ++ εδώ
Τι θα μάθετε:
Κυκλική ουρά σε C ++
Το παρακάτω διάγραμμα δείχνει μια κυκλική ουρά.
Η παραπάνω εικόνα δείχνει μια κυκλική δομή δεδομένων μεγέθους 10. Τα έξι πρώτα στοιχεία βρίσκονται ήδη στην ουρά και βλέπουμε ότι η πρώτη θέση και η τελευταία θέση ενώνονται. Λόγω αυτής της διευθέτησης, ο χώρος δεν σπαταλά όπως συμβαίνει σε μια γραμμική ουρά.
πώς να ανοίξετε το αρχείο .java
Σε μια γραμμική ουρά αφού είναι γεμάτη η ουρά, διαγράφουμε τα στοιχεία από άλλο άκρο και η κατάσταση της ουράς εξακολουθεί να εμφανίζεται ως πλήρης και δεν μπορούμε να εισαγάγουμε περισσότερα στοιχεία.
Στην κυκλική ουρά, όταν η ουρά είναι γεμάτη, και όταν αφαιρούμε στοιχεία από το μέτωπο από τη σύνδεση της τελευταίας και της πρώτης θέσης, μπορούμε να εισάγουμε τα στοιχεία στο πίσω μέρος που αδειάστηκαν διαγράφοντας το στοιχείο.
Στην επόμενη ενότητα, θα μάθουμε για τις βασικές λειτουργίες της κυκλικής ουράς.
Βασικές λειτουργίες
Μερικές από τις βασικές λειτουργίες της κυκλικής ουράς είναι οι εξής:
Εμπρός: Επιστρέφει την μπροστινή θέση στην κυκλική ουρά.
Οπισθεν: Επιστρέφει την πίσω θέση στην κυκλική ουρά.
Enqueue: Το Enqueue (τιμή) χρησιμοποιείται για την εισαγωγή ενός στοιχείου στην κυκλική ουρά. Το στοιχείο εισάγεται πάντα στο πίσω άκρο της ουράς.
Ακολουθούμε την παρακάτω ακολουθία βημάτων για να εισαγάγουμε ένα νέο στοιχείο στην κυκλική ουρά.
# 1) Ελέγξτε εάν η κυκλική ουρά είναι πλήρης: δοκιμή ((πίσω == SIZE-1 && front == 0) || (πίσω == εμπρός-1)), όπου το 'SIZE' είναι το μέγεθος της κυκλικής ουράς.
#δύο) Εάν η κυκλική ουρά είναι γεμάτη τότε εμφανίζει ένα μήνυμα ως 'Η ουρά είναι πλήρης'. Εάν η ουρά δεν είναι πλήρης τότε, ελέγξτε αν (πίσω == ΜΕΓΕΘΟΣ - 1 && μπροστά! = 0). Εάν είναι αλήθεια, ορίστε πίσω = 0 και εισάγετε στοιχείο.
Dequeue: Η λειτουργία Dequeue χρησιμοποιείται για τη διαγραφή ενός στοιχείου από την ουρά. Στην κυκλική ουρά, το στοιχείο διαγράφεται πάντα από το μπροστινό μέρος. Δίνεται παρακάτω η ακολουθία λειτουργίας dequeue σε κυκλική ουρά.
Βήματα:
# 1) Ελέγξτε εάν η κυκλική ουρά είναι άδεια: ελέγξτε αν (μπροστά == - 1).
#δύο) Εάν είναι κενό, εμφανίστε το μήνυμα 'Η ουρά είναι άδεια'. Εάν η ουρά δεν είναι κενή, εκτελέστε το βήμα 3.
# 3) Ελέγξτε εάν (μπροστά == πίσω). Εάν είναι αλήθεια, ορίστε μπροστά = πίσω = -1 αλλιώς ελέγξτε αν (εμπρός == μέγεθος-1), εάν είναι αλήθεια, ορίστε μπροστά = 0 και επιστρέψτε το στοιχείο.
Απεικόνιση
Σε αυτήν την ενότητα, θα εξετάσουμε μια λεπτομερή απεικόνιση της προσθήκης / αφαίρεσης στοιχείων στην κυκλική ουρά.
Εξετάστε την ακόλουθη κυκλική ουρά 5 στοιχείων όπως φαίνεται παρακάτω:
πώς να φτιάξετε ένα makefile c ++
Στη συνέχεια, εισάγουμε το στοιχείο 1 στην ουρά.
Στη συνέχεια, εισάγουμε ένα στοιχείο με τιμή 3.
Όταν εισάγουμε τα στοιχεία για να κάνουμε μια ουρά γεμάτη, η αναπαράσταση θα είναι όπως φαίνεται παρακάτω.
Τώρα διαγράφουμε τα δύο στοιχεία, δηλαδή το στοιχείο 1 και το στοιχείο 3 από την ουρά όπως φαίνεται παρακάτω.
Στη συνέχεια, εισάγουμε ή τοποθετούμε το στοιχείο 11 στην κυκλική ουρά όπως φαίνεται παρακάτω.
Και πάλι ας εισάγουμε το στοιχείο 13 στην κυκλική ουρά. Η ουρά θα φαίνεται όπως φαίνεται παρακάτω.
Βλέπουμε ότι στην κυκλική ουρά μετακινούμε ή εισάγουμε στοιχεία σε έναν κύκλο. Ως εκ τούτου μπορούμε να καταναλώσουμε ολόκληρο το χώρο της ουράς μέχρι να γεμίσει.
Εκτέλεση
Ας εφαρμόσουμε την κυκλική ουρά χρησιμοποιώντας το 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< Πάνω που φαίνεται είναι η έξοδος των κυκλικών ουρών. Κατ 'αρχάς, προσθέτουμε τα στοιχεία και στη συνέχεια dequeue ή αφαιρούμε δύο στοιχεία. Στη συνέχεια, εισάγουμε ή τοποθετούμε τρία ακόμη στοιχεία στην κυκλική ουρά. Βλέπουμε ότι σε αντίθεση με τη γραμμική ουρά, τα στοιχεία προστίθενται στο τέλος της ουράς.
Εφαρμογή συνδεδεμένης λίστας
Ας συζητήσουμε τώρα την εφαρμογή της συνδεδεμένης λίστας μιας κυκλικής ουράς τώρα. Παρακάτω δίνεται η συνδεδεμένη λίστα υλοποίησης της κυκλικής ουράς στο C ++. Σημειώστε ότι χρησιμοποιούμε το struct για να αντιπροσωπεύουμε κάθε κόμβο. Οι λειτουργίες είναι οι ίδιες όπως συζητήθηκαν προηγουμένως, εκτός από το ότι σε αυτήν την περίπτωση, πρέπει να τις εκτελέσουμε σε σχέση με τους συνδεδεμένους κόμβους λίστας.
Η έξοδος δείχνει την κυκλική ουρά μετά τη λειτουργία enqueue, το dequeue και επίσης μετά τη δεύτερη λειτουργία 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: '< Παραγωγή:
Η επόμενη εφαρμογή είναι ένα πρόγραμμα Java για την επίδειξη κυκλικής ουράς χρησιμοποιώντας τη συνδεδεμένη λίστα.
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); } } Παραγωγή:
Η έξοδος του παραπάνω προγράμματος είναι παρόμοια με το προηγούμενο πρόγραμμα.
Εφαρμογές
Ας συζητήσουμε μερικές από τις εφαρμογές της κυκλικής ουράς.
- Προγραμματισμός CPU: Η διαδικασία του λειτουργικού συστήματος που απαιτεί την πραγματοποίηση κάποιου συμβάντος ή την ολοκλήρωση ορισμένων άλλων διαδικασιών, εκτελείται συχνά σε κυκλική ουρά έτσι ώστε να εκτελούνται το ένα μετά το άλλο όταν πληρούνται όλες οι συνθήκες ή όταν συμβαίνουν όλα τα συμβάντα.
- Διαχείριση μνήμης: Η χρήση συνηθισμένων ουρών σπαταλά χώρο μνήμης όπως ήδη αναφέρθηκε στην παραπάνω συζήτησή μας. Η χρήση κυκλικής ουράς για διαχείριση μνήμης είναι επωφελής για τη βέλτιστη χρήση της μνήμης.
- Σύστημα σήματος κυκλοφορίας ελεγχόμενο από υπολογιστή: Τα ηλεκτρονικά σήματα κυκλοφορίας συχνά προστίθενται σε μια κυκλική ουρά έτσι ώστε να επαναλαμβάνονται μετά την παρέλευση του καθορισμένου χρονικού διαστήματος.
συμπέρασμα
Οι κυκλικές ουρές διορθώνουν το μεγαλύτερο μειονέκτημα μιας κανονικής ουράς όπου δεν μπορούμε να εισάγουμε στοιχεία όταν ο πίσω δείκτης βρίσκεται στο τέλος της ουράς ακόμα και όταν διαγράφουμε τα στοιχεία και ο χώρος αδειάζεται. Σε μια κυκλική ουρά, τα στοιχεία είναι διατεταγμένα με κυκλικό τρόπο, έτσι ώστε ο χώρος να μην χάνεται καθόλου.
Έχουμε δει επίσης τις μεγάλες λειτουργίες της κυκλικής ουράς. Οι κυκλικές ουρές είναι ως επί το πλείστον χρήσιμες για σκοπούς προγραμματισμού και εφαρμογές όπως συστήματα σημάτων κυκλοφορίας όπου τα σήματα ανάβουν με σειρά.
ποιο είναι το κλειδί ασφαλείας του δικτύου σας
Στο επόμενο σεμινάριό μας, θα μάθουμε για τις ουρές διπλού άκρου που ονομάζονται απλά «deque».
=> Επισκεφθείτε εδώ για να μάθετε C ++ από το μηδέν
Συνιστώμενη ανάγνωση
- Δομή δεδομένων ουράς σε C ++ με απεικόνιση
- Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση
- Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Tutorial Data Mart - Τύποι, παραδείγματα & υλοποίηση του Data Mart
- Δομή δεδομένων στοίβας σε C ++ με απεικόνιση
- Παραδείγματα εξόρυξης δεδομένων: Οι πιο κοινές εφαρμογές της εξόρυξης δεδομένων 2021
- Δομή Δυαδικών Δέντρων Στο C ++
- Ουρά προτεραιότητας στο STL
