Πώς να χρησιμοποιήσετε την ουρά C ++

Εισαγωγή

Μια ουρά είναι μια συλλογή στοιχείων, όπου το πρώτο στοιχείο που προστίθεται στη λίστα, πρέπει να είναι το πρώτο στοιχείο που θα αφαιρεθεί στη συνέχεια. Έτσι καθώς τα αντικείμενα προστίθενται στη συλλογή, μεγαλώνει σε μέγεθος, δηλαδή μεγαλώνει σε μήκος. Κάθε φορά που πρόκειται να αφαιρεθεί κάποιο στοιχείο, πρέπει να είναι το πρώτο που προστίθεται. Εάν τα στοιχεία αφαιρούνται συνεχώς, τότε το επόμενο που αφαιρείται, είναι το δεύτερο στοιχείο. το τρίτο αφαιρείται μετά και ούτω καθεξής.

Αφού αφαιρεθεί το πρώτο στοιχείο της αρχικής λίστας, το δεύτερο γίνεται το πρώτο στοιχείο. Αφού αφαιρεθεί το δεύτερο στοιχείο, το τρίτο γίνεται το πρώτο και ούτω καθεξής.

Ένα καλό πραγματικό παράδειγμα ουράς είναι όταν οι άνθρωποι παρατάσσονται στη σειρά για να περιμένουν για υπηρεσία ή για καλό. Το πρώτο άτομο εξυπηρετείται πρώτο πριν από το τελευταίο. Ωστόσο, η ουρά που συζητήθηκε σε αυτό το σεμινάριο είναι η ουρά λογισμικού, όπως έχει σχεδιαστεί σε C ++.

FIFO

Το FIFO σημαίνει First-In, First-Out. Είναι ένας άλλος τρόπος εκτίμησης της ουράς. Αυτό σημαίνει ότι, το πρώτο στοιχείο που μπαίνει στη λίστα, είναι το πρώτο στοιχείο που πρέπει να αφαιρεθεί, όποτε πρόκειται να πραγματοποιηθεί αφαίρεση. Η αρχή της λίστας ονομάζεται κεφαλή ή εμπρός. το τέλος της λίστας ονομάζεται πίσω ή ουρά.

Βασικές Λειτουργίες

Μια ουρά λογισμικού πρέπει να έχει τουλάχιστον τις ακόλουθες λειτουργίες:

Σπρώξτε

Αυτή η λειτουργία, προσθέτει ένα νέο στοιχείο στο πίσω μέρος της ουράς. Αυτή η λειτουργία ονομάζεται επίσημα, enqueue.

μετατόπιση

Αυτή η λειτουργία αφαιρεί το πρώτο στοιχείο της ουράς και το δεύτερο στοιχείο γίνεται το νέο πρώτο στοιχείο. Αυτή η λειτουργία ονομάζεται επίσημα dequeue. Ονομάζεται pop στο C ++.

Αυτό το άρθρο εξηγεί πώς να χρησιμοποιήσετε τη δομή δεδομένων ουράς C ++. Θα πρέπει να γνωρίζετε δείκτες και αναφορές C ++ για να κατανοήσετε το υπόλοιπο αυτού του άρθρου.

Τάξη και Αντικείμενα

Μια κλάση είναι ένα σύνολο μεταβλητών και συναρτήσεων που λειτουργούν μαζί, όπου οι μεταβλητές δεν έχουν τιμές εκχωρημένες. Όταν εκχωρούνται τιμές στις μεταβλητές, η κλάση γίνεται αντικείμενο. Διαφορετικές τιμές που δίνονται στην ίδια κλάση οδηγούν σε διαφορετικά αντικείμενα. δηλαδή, διαφορετικά αντικείμενα έχουν την ίδια κλάση με διαφορετικές τιμές. Η δημιουργία ενός αντικειμένου από μια κλάση λέγεται ότι δημιουργεί το αντικείμενο.

Το όνομα, ουρά, είναι μια τάξη. Ένα αντικείμενο που δημιουργήθηκε από την κλάση ουράς έχει ένα όνομα προγραμματιστή που έχει επιλεγεί.

Μια συνάρτηση που ανήκει σε μια κλάση είναι απαραίτητη για την παρουσίαση ενός αντικειμένου από την κλάση. Στο C ++, αυτή η συνάρτηση έχει το ίδιο όνομα με το όνομα της κλάσης. Τα αντικείμενα που δημιουργήθηκαν (ενδεικτικά) από την τάξη έχουν διαφορετικά ονόματα που τους δόθηκαν από τον προγραμματιστή.

Η δημιουργία ενός αντικειμένου από την κλάση σημαίνει την κατασκευή του αντικειμένου. σημαίνει επίσης ενσάρκωση.

Ένα πρόγραμμα C ++ που χρησιμοποιεί την κλάση ουράς, ξεκινά με τις ακόλουθες γραμμές στο επάνω μέρος του αρχείου:

Η πρώτη γραμμή είναι για είσοδο/έξοδο. Η δεύτερη γραμμή είναι να επιτρέψει στο πρόγραμμα να χρησιμοποιήσει όλες τις δυνατότητες της κλάσης ουράς. Η τρίτη γραμμή επιτρέπει στο πρόγραμμα να χρησιμοποιεί τα ονόματα στον τυπικό χώρο ονομάτων.

Υπερφόρτωση μιας λειτουργίας

Όταν δύο ή περισσότερες διαφορετικές υπογραφές συνάρτησης έχουν το ίδιο όνομα, αυτό το όνομα λέγεται ότι είναι υπερφορτωμένο. Όταν καλείται μία συνάρτηση, ο αριθμός και ο τύπος των ορισμάτων, καθορίζουν ποια συνάρτηση εκτελείται στην πραγματικότητα.

Κατασκευή

Η ακόλουθη δήλωση δημιουργεί μια ουρά με όνομα, que του τύπου int.

Η ουρά είναι κενή. Η δήλωση ξεκινά με τη δεσμευμένη λέξη, ουρά ακολουθούμενη από γωνιακές αγκύλες με τον τύπο δεδομένων. Στη συνέχεια, έχετε το όνομα του προγραμματιστή για την ουρά.

Κατασκευή με Λίστα αρχικοποίησης

Ο ακόλουθος ορισμός δείχνει πώς μπορείτε να δημιουργήσετε μια ουρά με λίστα αρχικοποίησης:

Καταστροφή ουράς

Για να καταστρέψετε μια ουρά, απλώς αφήστε την να ξεφύγει από το πεδίο εφαρμογής.

Πρόσβαση στο στοιχείο ουράς

ώθηση (τιμή)

Μια ουρά είναι μια λίστα First-In-First-Out. Έτσι, κάθε τιμή προστίθεται από το πίσω μέρος. Το ακόλουθο τμήμα κώδικα δημιουργεί μια κενή ουρά, μετά την οποία προστίθενται πέντε τιμές float από το πίσω μέρος:

μέγεθος () const

Αυτό επιστρέφει τον αριθμό των στοιχείων στην ουρά. Ο παρακάτω κώδικας απεικονίζει:

Η έξοδος είναι 5.

εμπρός()

Αυτό επιστρέφει μια αναφορά στο πρώτο στοιχείο της ουράς, χωρίς να αφαιρεθεί το στοιχείο. Η έξοδος του ακόλουθου κώδικα είναι 1.1.

Το στοιχείο δεν αφαιρείται από την ουρά.

εμπρός () const

Όταν προηγείται η κατασκευή της ουράς με const, η παράσταση front () const εκτελείται αντί για front (). Χρησιμοποιείται, για παράδειγμα, στον ακόλουθο κώδικα.

Επιστρέφεται μια σταθερή αναφορά. Το στοιχείο δεν αφαιρείται από το διάνυσμα. Τα στοιχεία ουράς δεν μπορούν να αλλάξουν.

πίσω()

Αυτό επιστρέφει μια αναφορά στο τελευταίο στοιχείο της ουράς, χωρίς να αφαιρεθεί το στοιχείο. Η έξοδος του ακόλουθου κώδικα είναι 5.5.

πίσω () const

Όταν προηγείται η κατασκευή της ουράς με const, η έκφραση back () const εκτελείται αντί για back (). Χρησιμοποιείται, για παράδειγμα, στον ακόλουθο κώδικα.

Επιστρέφεται μια σταθερή αναφορά. Το στοιχείο δεν αφαιρείται από την ουρά. Με το προηγούμενο const για την κατασκευή της ουράς, τα στοιχεία στην ουρά δεν μπορούν να αλλάξουν.

Χωρητικότητα ουράς

μέγεθος () const

- βλέπε παραπάνω

κενό () const

Αυτό επιστρέφει 1 για true αν δεν υπάρχουν στοιχεία στην ουρά ή 0 για false αν η ουρά είναι κενή. Ο παρακάτω κώδικας το δείχνει αυτό:

Η έξοδος είναι:

Τροποποιητές ουράς

ποπ ()

Μια ουρά είναι FIFO, οπότε κάθε στοιχείο που πρέπει να αφαιρεθεί πρέπει να αφαιρεθεί από το επάνω μέρος (κεφαλή) της ουράς. Αυτή η συνάρτηση μέλους αφαιρεί το πρώτο στοιχείο χωρίς να το επιστρέψει. Ο παρακάτω κώδικας το δείχνει αυτό:

Η έξοδος είναι:

a.swap (β)

Δύο ουρές μπορούν να αλλάξουν, όπως απεικονίζεται σε αυτό το τμήμα κώδικα:

Η έξοδος είναι:

Πρώτο στοιχείο και μέγεθος que1: 10, 2

Πρώτο στοιχείο και μέγεθος que2: 1.1, 5

Σημειώστε ότι το μήκος μιας ουράς αυξάνεται εάν είναι απαραίτητο. Επίσης, οι τιμές που δεν είχαν αντικαταστάσεις, αντικαθίστανται από κάποια προεπιλεγμένη τιμή. Οι τύποι δεδομένων πρέπει να είναι του ίδιου τύπου.

Equality and Relational Operators for Queues

Για τους συνηθισμένους χαρακτήρες σε C ++, με αύξουσα σειρά, οι αριθμοί έρχονται πριν από κεφαλαία γράμματα, τα οποία έρχονται πριν από πεζά γράμματα. Ο χαρακτήρας χώρου έρχεται πριν από το μηδέν και όλοι τους.

Χειριστές Ισότητας

Επιστρέφει 1 για true και 0 για false.

Ο == Τελεστής

Επιστρέφει 1 εάν οι δύο ουρές έχουν το ίδιο μέγεθος και τα αντίστοιχα στοιχεία είναι ίσα. αλλιώς επιστρέφει 0. Παράδειγμα:

Η έξοδος είναι: 0.

Ο! = Τελεστής

- αντίθετα από τα παραπάνω. Παράδειγμα:

Η έξοδος είναι: 1.

Σχετικοί χειριστές

Επιστρέφει 1 για true και 0 για false.

ο