Το κυκλικό buffer ή το Circular queue είναι η προηγμένη έκδοση της κανονικής ουράς όπου ο τελευταίος δείκτης και ο δείκτης ουράς συνδέονται σε μια κυκλική δομή. Το κυκλικό buffer στη C++ ακολουθεί δύο μεθόδους: enqueue() και dequeue(). Εκτελούμε τη λειτουργία κυκλικής προσωρινής αποθήκευσης ή κυκλικής ουράς με βάση αυτές τις μεθόδους.
- Η μέθοδος enqueue() ελέγχει εάν το buffer έχει γεμιστεί. Διαφορετικά, βεβαιωθείτε ότι ο τελικός δείκτης είναι ο τελευταίος. Εάν ναι, ορίστε την τιμή της ουράς σε 0. Εάν όχι, αυξήστε την τιμή της ουράς κατά την τιμή σε αυτόν τον δείκτη.
- Η συνάρτηση dequeue() παίρνει την τιμή από το μπροστινό ευρετήριο στην κυκλική ουρά. Εάν η ουρά είναι άδεια, ένα μήνυμα θα εμφανίσει αυτήν την άδεια ουρά. Διαφορετικά, παίρνει την τελευταία τιμή και τη διαγράφει από την ουρά.
Πρόγραμμα για την υλοποίηση ενός κυκλικού buffer σε C++
Ακολουθώντας τις δύο παραπάνω μεθόδους, υλοποιούμε το κυκλικό buffer στη C++. Ας εξετάσουμε όλα τα βήματα για την υλοποίηση της κυκλικής ουράς στη C++.
#include
χρησιμοποιώντας namespace std?
δομή MyQueue
{
ενθ κεφάλι , ουρά ;
int Qsize;
ενθ * NewArr;
MyQueue ( int αρ ) {
κεφάλι = ουρά = -1 ;
Qsize = μέγεθος;
NewArr = νέος ενθ [ μικρό ] ;
}
void enQueue ( int val ) ;
int deQueue ( ) ;
void showQueue ( ) ;
} ;
Ξεκινώντας με τον κώδικα, δημιουργούμε πρώτα τη δομή 'MyQueue' για να αρχικοποιήσουμε τις μεταβλητές head and tail. Η μεταβλητή head αντιπροσωπεύει τους μπροστινούς δείκτες και η ουρά αντιπροσωπεύει τους πίσω δείκτες μιας συστοιχίας. Μετά από αυτό, ορίζεται το μέγεθος της κυκλικής ουράς, που συμβολίζεται με τη μεταβλητή 'Qsize'.
Στη συνέχεια, ορίζουμε τον δυναμικά εκχωρημένο πίνακα του 'NewArr' που αποθηκεύει τις τιμές της κυκλικής ουράς. Στη συνέχεια, καλούμε την MyQueue() που είναι κατασκευαστής και περνάμε την παράμετρο “sz” για το κυκλικό μέγεθος ουράς. Μέσα στον κατασκευαστή MyQueue(), εκχωρούμε την τιμή '-1' στους δείκτες κεφαλής και ουράς. Αυτή η αρνητική τιμή υποδεικνύει ότι η ουρά είναι άδεια τώρα. Προχωρώντας μπροστά, εκχωρούμε την τιμή 'sz' που αντιπροσωπεύει το μέγεθος της κυκλικής ουράς. Η κυκλική ουρά 'NewArr' ορίζεται με μια νέα λέξη-κλειδί για τη δημιουργία του πίνακα ακεραίων εντός του καθορισμένου μεγέθους 'sz'.
Στη συνέχεια, ορίζουμε τις συναρτήσεις enQueue() και dequeue(). Η enqueue() εισάγει τις τιμές στην καθορισμένη κυκλική ουρά από την ουρά. Ωστόσο, τα στοιχεία στην κεφαλή της κυκλικής ουράς εξαλείφονται από τη συνάρτηση dequeue(). Η συνάρτηση μέλους showQueue() εμφανίζει τις τιμές της κυκλικής ουράς.
Βήμα 1: Δημιουργήστε μια συνάρτηση για την εισαγωγή των στοιχείων σε μια κυκλική προσωρινή μνήμη
Στο προηγούμενο βήμα, ορίσαμε μια κλάση όπου αρχικοποιούνται τα ιδιωτικά μέλη και οι συναρτήσεις ιδιωτικού μέλους ορίζονται για να υλοποιήσουν την κυκλική ουρά. Τώρα, ορίζουμε τη συνάρτηση να δημιουργεί την κυκλική ουρά και εισάγουμε τις τιμές μέσα στην κυκλική ουρά χρησιμοποιώντας τον αλγόριθμο.
void MyQueue::enQueue ( int val ){
αν ( ( κεφάλι == 0 && ουρά == Q μέγεθος - 1 ) || ( ουρά == ( κεφάλι - 1 ) % ( Qsize - 1 ) ) )
{
cout << ' \n Η ουρά είναι γεμάτη' ;
ΕΠΙΣΤΡΟΦΗ ;
}
αλλού αν ( κεφάλι == - 1 )
{
κεφάλι = ουρά = 0 ;
NewArr [ ουρά ] = val;
}
αλλού αν ( ουρά == Q μέγεθος - 1 && κεφάλι ! = 0 )
{
ουρά = 0 ;
NewArr [ ουρά ] = val;
}
αλλού {
ουρά ++;
NewArr [ ουρά ] = val;
}
}
Εδώ, καλούμε τη συνάρτηση 'enqueue()' από την κλάση 'MyQueue' για να εισαγάγουμε το στοιχείο στην κυκλική ουρά αν η ουρά είναι κενή ή υπορροή. Η συνάρτηση 'enqueue()' μεταβιβάζεται με την παράμετρο 'val' και εισάγεται η τιμή από την ουρά της κυκλικής ουράς. Θέτουμε τη συνθήκη 'if-else' για να εισαγάγουμε τις τιμές στην κυκλική ουρά για αυτό. Η πρώτη δήλωση 'αν' που είναι 'if ((κεφαλή == 0 && ουρά == Qsize – 1) || (ουρά == (κεφαλή – 1) % (Qsize – 1))' ελέγχει δύο συνθήκες εάν η κεφαλή είναι στην αρχική θέση και η ουρά είναι στην τελική θέση της κυκλικής ουράς. Στη συνέχεια, ελέγχει εάν η ουρά βρίσκεται σε μία θέση στο πίσω μέρος της θέσης του κεφαλιού. Εάν πληρούται κάποια από αυτές τις προϋποθέσεις, η ουρά δεν είναι κενή και η προτροπή δημιουργεί το μήνυμα.
Στη συνέχεια, έχουμε τη συνθήκη 'else-if' που προσδιορίζει εάν η ουρά είναι κενή. Εάν ναι, η τιμή εισάγεται στην ουρά. Καθώς η κεφαλή διατηρείται ίση με -1, αυτό δείχνει ότι η ουρά είναι άδεια και η τιμή πρέπει να εισαχθεί στην κυκλική ουρά. Για αυτό, ορίσαμε το κεφάλι και την ουρά ίσα με 0. Στη συνέχεια, εισάγουμε την τιμή από τη θέση ουράς στην κυκλική ουρά 'NewArr'.
Στη συνέχεια, έχουμε την τρίτη συνθήκη «άλλο-αν» που ελέγχει αν η ουρά βρίσκεται στην τελευταία θέση της ουράς και η κεφαλή δεν είναι η αρχική θέση της ουράς. Αυτή η συνθήκη ισχύει όταν η ουρά φτάνει στο τέλος και η αρχική θέση έχει ακόμα χώρο. Για αυτό, πρέπει να θέσουμε το κεφάλι στο 0 και το στοιχείο προστίθεται από τη θέση της ουράς. Τέλος, αν δεν πληρούνται όλες οι δεδομένες προϋποθέσεις, η ουρά δεν είναι ούτε άδεια ούτε γεμάτη. Για αυτήν την περίπτωση, αυξάνουμε την ουρά κατά 1 και η τιμή προστίθεται από τη νέα θέση ουράς.
Βήμα 2: Δημιουργήστε μια συνάρτηση για να διαγράψετε τα στοιχεία από το κυκλικό buffer
Ρυθμίσαμε τον προηγούμενο κώδικα να δημιουργεί και να εισάγει τα στοιχεία στην κυκλική ουρά χρησιμοποιώντας τη συνάρτηση enqueue(). Τώρα, ορίζουμε την υλοποίηση της αφαίρεσης των στοιχείων από το κυκλικό buffer εάν υπερχειλίσει.
int MyQueue::deQueue ( ){
αν ( κεφάλι == - 1 )
{
cout << ' \n Η ουρά είναι δωρεάν' ;
ΕΠΙΣΤΡΟΦΗ INT_MIN;
}
int MyData = NewArr [ κεφάλι ] ;
NewArr [ κεφάλι ] = -1 ;
αν ( κεφάλι == ουρά )
{
κεφάλι = -1 ;
ουρά = -1 ;
}
αλλού αν ( κεφάλι == Q μέγεθος - 1 )
κεφάλι = 0 ;
αλλού
κεφάλι ++;
ΕΠΙΣΤΡΟΦΗ Τα δεδομένα μου;
}
Στον δεδομένο κώδικα, καλούμε τη συνάρτηση dequeue() από την κλάση 'Myqueue' για να αφαιρέσουμε το στοιχείο από το αρχικό ευρετήριο. Έτσι, έχουμε τη δήλωση 'if' που ελέγχει εάν η ουρά είναι κενή. Η κεφαλή ορίζεται με την τιμή '-1' που αντιπροσωπεύει την κενή ουρά. Δημιουργείται το μήνυμα ότι η ουρά είναι κενή και στη συνέχεια επιστρέφει το INT_MIN που είναι η σταθερή ελάχιστη τιμή για ένα int. Η δήλωση 'if' καθορίζει εάν η ουρά δεν είναι κατειλημμένη. Για αυτό, ορίζουμε τη μεταβλητή 'MyData' και ορίζουμε την τιμή του στοιχείου στην κεφαλή της ουράς. Στη συνέχεια, θέτουμε την κεφαλή στη θέση -1 που δείχνει ότι αυτή η τιμή έχει αφαιρεθεί από την ουρά. Μετά από αυτό, ελέγχουμε αν το κεφάλι και η ουρά είναι ίσα ή όχι. Εάν και τα δύο είναι ίσα, εκχωρούμε την τιμή '-1' και στα δύο, αντιπροσωπεύοντας την κενή κυκλική ουρά. Τέλος, ελέγχουμε αν η dequeue() λειτουργεί εάν η κεφαλή βρίσκεται στον τελευταίο δείκτη της ουράς. Για αυτό, το ορίζουμε με την τιμή '0' που εμφανίζεται στην αρχή του πίνακα. Εάν καμία από τις δεδομένες συνθήκες δεν είναι αληθής, η τιμή της κεφαλής αυξάνεται και το στοιχείο που έχει αφαιρεθεί επιστρέφεται.
Βήμα 3: Δημιουργήστε μια συνάρτηση για την εμφάνιση των στοιχείων του κυκλικού buffer
Σε αυτήν την ενότητα, καλούμε τη συνάρτηση showQueue() για να εμφανίσουμε τα στοιχεία της κυκλικής ουράς 'NewArr'.
void MyQueue::showQueue ( ){
αν ( κεφάλι == - 1 )
{
cout << ' \n Η ουρά είναι δωρεάν' ;
ΕΠΙΣΤΡΟΦΗ ;
}
cout << ' \n Στοιχεία κυκλικής ουράς: ' ;
αν ( ουρά > = κεφάλι )
{
Για ( int i = κεφάλι ; Εγώ < = ουρά ; i++ )
cout << NewArr [ Εγώ ] << '' ;
}
αλλού
{
Για ( int i = κεφάλι ; Εγώ < Qsize; i++ )
cout << NewArr [ Εγώ ] << '' ;
Για ( int i = 0 ; Εγώ < = ουρά ; i++ )
cout << NewArr [ Εγώ ] << '' ;
}
}
Η κατάσταση κενού της ουράς επαληθεύεται πρώτα. Εάν η ουρά είναι ελεύθερη, εμφανίζεται μια ένδειξη ότι η κυκλική ουρά είναι ελεύθερη. Διαφορετικά, η συνάρτηση θα εμφανίσει τα στοιχεία της κυκλικής ουράς. Για αυτό, ορίζουμε τη δήλωση «αν» όπου έχουμε την ουρά που είναι μεγαλύτερη ή ίση με το κεφάλι. Αυτή η συνθήκη έχει ρυθμιστεί για να χειρίζεται την περίπτωση όταν η κυκλική ουρά δεν έχει ολοκληρωθεί.
Για αυτήν την περίπτωση, χρησιμοποιούμε τον βρόχο «για» για να επαναλάβουμε από την κορυφή μέχρι την ουρά και να εκτυπώσουμε τις τιμές της κυκλικής ουράς. Η επόμενη περίπτωση είναι όπου ολοκληρώνεται η κυκλική ουρά. Για αυτό, ελέγχουμε χρησιμοποιώντας τη συνθήκη «αν» όπου η ουρά είναι μικρότερη από το κεφάλι. Στη συνέχεια, πρέπει να χρησιμοποιήσουμε δύο βρόχους όπου ο πρώτος επαναλαμβάνεται από το κεφάλι μέχρι το τέλος της ουράς και ο δεύτερος επαναλαμβάνεται από την αρχή της ουράς.
Βήμα 4: Δημιουργήστε τη συνάρτηση Main() του προγράμματος Circular Queue
Τέλος, δημιουργούμε τη συνάρτηση main() του προγράμματος όπου εισάγουμε πέντε ακέραιους αριθμούς στην κυκλική ουρά και εμφανίζουμε τους ακέραιους αριθμούς της ουράς. Μετά από αυτό, δείχνουμε τους διαγραμμένους ακέραιους αριθμούς από την κυκλική ουρά καλώντας τη συνάρτηση dequeue(). Αφού αφαιρέσουμε μερικά στοιχεία, γεμίζουμε ξανά την ουρά εισάγοντας τα νέα στοιχεία χρησιμοποιώντας τη συνάρτηση enqueue().
int main ( ){
MyQueue αυτό ( 5 ) ;
// Εισαγωγή στοιχείων σε Κυκλική ουρά
que.enΟυρά ( έντεκα ) ;
que.enΟυρά ( 12 ) ;
que.enΟυρά ( 13 ) ;
que.enΟυρά ( 14 ) ;
que.enΟυρά ( δεκαπέντε ) ;
// Παρουσιάζονται στοιχεία εμφάνισης σε Κυκλική ουρά
que.showΟυρά ( ) ;
// Διαγραφή στοιχείων από την κυκλική ουρά
cout << ' \n Διαγραμμένο στοιχείο = ' << que.deQueue ( ) ;
cout << ' \n Διαγραμμένο στοιχείο = ' << que.deQueue ( ) ;
que.showΟυρά ( ) ;
que.enΟυρά ( 16 ) ;
que.enΟυρά ( 17 ) ;
que.enΟυρά ( 18 ) ;
que.showΟυρά ( ) ;
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Παραγωγή:
Τα αποτελέσματα της υλοποίησης της κυκλικής ουράς εμφανίζονται στην οθόνη προτροπής C++.
συμπέρασμα
Συμπερασματικά, το θέμα του κυκλικού buffer εξηγείται σε βάθος σε αυτό το άρθρο. Δημιουργήσαμε πρώτα το κυκλικό buffer, μετά εξηγήσαμε πώς να διαγράψουμε από την κυκλική ουρά και μετά εμφανίσαμε τα στοιχεία του κυκλικού σε C++.