Μενού

Στοίβες και ουρές στο STL

stacks queues stl

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Μάθετε την Εφαρμογή Στοίβας και Ουρών στο STL με Παραδείγματα.

Οι στοίβες και οι ουρές είναι δύο εμπορευματοκιβώτια στο STL που έχουν πολύ βασικό χαρακτήρα. Είναι τα απλούστερα εμπορευματοκιβώτια που έχουν ευρείες εφαρμογές στον προγραμματισμό λογισμικού.

Σε αυτό το σεμινάριο, θα δούμε μια λεπτομερή εφαρμογή και των δύο αυτών κοντέινερ στο STL. Θα εξετάσουμε επίσης τις διάφορες λειτουργίες που υποστηρίζονται από στοίβα και ουρά με παραδείγματα.

=> Παρακολουθήστε την απλή σειρά εκπαίδευσης C ++ εδώ.

STACKS AND QUEUES στο STL

Τι θα μάθετε:

Στοίβες

Το δοχείο στοίβας στο STL είναι ένας τύπος προσαρμογέα κοντέινερ. Χρησιμοποιείται για την αναπαραγωγή μιας δομής δεδομένων στοίβας στο C ++. Το δοχείο στοίβας είναι ένα σύνολο στοιχείων στα οποία τα στοιχεία εισάγονται στο ένα άκρο και διαγράφονται επίσης στο ίδιο άκρο.

Αυτό το κοινό σημείο προσθήκης και διαγραφής είναι γνωστό ως 'Κορυφή της στοίβας'.

Η εικονική αναπαράσταση της στοίβας φαίνεται παρακάτω.

σωρός

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

Δεδομένου ότι η προσθήκη και η διαγραφή συμβαίνουν στο ίδιο άκρο, μπορούμε να πούμε ότι το κοντέινερ στοίβας είναι είδος εργασίας LIFO (last in, first out). Αυτό σημαίνει ότι το στοιχείο που προστέθηκε πρώτο θα είναι το τελευταίο που θα διαγραφεί.

Για να υλοποιήσουμε το stack container, πρέπει να συμπεριλάβουμε την κεφαλίδα στο πρόγραμμά μας.

#include

Η σύνταξη γενικής δήλωσης για κοντέινερ στοίβας είναι:

stack stackName;

Λειτουργίες στοίβας

Στη συνέχεια, ας συζητήσουμε τις διάφορες λειτουργίες που υποστηρίζει το κοντέινερ στο STL.

  • Σπρώξτε : η λειτουργία ώθησης χρησιμοποιείται για την εισαγωγή ενός στοιχείου στη στοίβα. Αυτή η λειτουργία προσθέτει πάντα στοιχεία στο πάνω μέρος της στοίβας.

Σκεφτείτε μια κενή στοίβα mystack τύπου ακέραιου .

μυστικό

Στη συνέχεια, ας προσθέσουμε το στοιχείο 1 στη στοίβα.

προσθέστε το στοιχείο 1 στη στοίβα

Στη συνέχεια, προσθέτουμε το στοιχείο 3 στη στοίβα.

προσθέστε το στοιχείο 3 στη στοίβα

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

  • κρότος : η λειτουργία pop χρησιμοποιείται για την αφαίρεση ενός στοιχείου από τη στοίβα. Το στοιχείο που αφαιρείται είναι αυτό που επισημαίνεται από την κορυφή της στοίβας. Ως αποτέλεσμα της λειτουργίας pop, το μέγεθος της στοίβας μειώνεται κατά 1.

Ας δούμε πώς φαίνεται η λειτουργία pop:

Εξετάστε το stack mystack όπως παραπάνω στο οποίο έχουμε ήδη προωθήσει 2 στοιχεία.

mystack2

Τώρα ας καλέσουμε τη συνάρτηση pop (). Όταν εκτελείται αυτή η κλήση, το στοιχείο στο επάνω μέρος της στοίβας αφαιρείται και το «Κορυφή» δείχνει το επόμενο στοιχείο όπως φαίνεται παρακάτω.

Το στοιχείο «3» καταργείται η λειτουργία ποπ

Εάν καλέσουμε ξανά το pop (), τότε το επόμενο στοιχείο (σε αυτήν την περίπτωση 1) θα αφαιρεθεί με αποτέλεσμα μια κενή στοίβα.

Το στοιχείο «1» αφαιρείται - λειτουργία στοίβας

πώς να γράψετε μια καλή δοκιμαστική θήκη
  • μπλουζα : Επιστρέφει το ανώτατο στοιχείο της στοίβας.
  • αδειάζω : Ελέγχει εάν η στοίβα είναι άδεια ή όχι.
  • Μέγεθος: Επιστρέφει το μέγεθος της στοίβας, δηλαδή τον αριθμό των στοιχείων στη στοίβα.

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

#include #include using namespace std; void printStack(stack stk) { while (!stk.empty()) { cout << ' ' << stk.top(); stk.pop(); } cout << ' '; } int main () { stack oddstk; oddstk.push(1); oddstk.push(3); oddstk.push(5); oddstk.push(7); oddstk.push(9); cout << 'The stack is : '; printStack(oddstk); cout << ' Size of stack: ' << oddstk.size(); cout << ' Top of stack: ' << oddstk.top(); cout << ' oddstk.pop() : '; oddstk.pop(); printStack(oddstk); cout<<' Another pop(): '; oddstk.pop(); printStack(oddstk); return 0; }

έξοδος υλοποίησης στοίβας

Το παραπάνω παράδειγμα δείχνει ξεκάθαρα τη λειτουργία ώθησης που δημιουργεί μια στοίβα. Εμφανίζει επίσης τη στοίβα μετά από δύο διαδοχικές ποπ λειτουργίες.

Έτσι έχουμε δει στοίβα και τις λειτουργίες του στο STL. Επιπλέον, σε αυτό το σεμινάριο, θα δούμε τη λεπτομερή εφαρμογή ενός ακόμη απλού κοντέινερ STL που είναι το 'Queue'.

Ουρά

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

Στοιχεία προστίθενται στην ουρά στο πίσω μέρος ενώ διαγράφονται από το μπροστινό μέρος της ουράς. Σε γενικές γραμμές, η ουρά χρησιμοποιεί τύπο ρύθμισης FIFO (First in, First Out).

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

#include

Η γενική σύνταξη για δήλωση της ουράς είναι:

ουρά queue_name;

Δηλώνουμε το κοντέινερ ουράς ως εξής:

Queue myqueue;

Λειτουργίες ουράς

Τώρα, θα δούμε τις διάφορες λειτουργίες που υποστηρίζονται από την ουρά.

  • Σπρώξτε: Η συνάρτηση «push» προσθέτει το στοιχείο στο τέλος της ουράς, δηλαδή στο πίσω μέρος της ουράς.
  • κρότος: Η συνάρτηση «pop» αφαιρεί το πρώτο στοιχείο της ουράς, δηλαδή το στοιχείο στο μπροστινό μέρος της ουράς.

Ας κατανοήσουμε τις λειτουργίες push και pop της ουράς.

Σκεφτείτε μια κενή ουρά που δηλώνεται πάνω από το myqueue. Τώρα σπρώχνουμε ένα ζυγό νούμερο 2 στην ουρά με τη λειτουργία

myqueue.push (2);

Τώρα η ουρά θα μοιάζει με:

myqueue.pop ();

Στη συνέχεια, προσθέτουμε το '4' στην ουρά με την κλήση 'myqueue.push (4)'.

Τώρα η ουρά φαίνεται όπως φαίνεται παρακάτω:

myqueue.push (4)

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

Τώρα ας ανοίξουμε τη λειτουργία στο myqueue.

myqueue.pop ();

myqueue.pop ();

Όπως βλέπουμε, όταν καλείται pop (), το στοιχείο στο μπροστινό μέρος της ουράς αφαιρείται. Αυτό σημαίνει ότι το πρώτο στοιχείο που εισάγεται στην ουρά είναι το πρώτο στοιχείο που βρίσκεται εκτός της ουράς.

  • εμπρός: Αυτή η συνάρτηση επιστρέφει μια αναφορά στο πρώτο στοιχείο της ουράς.
  • πίσω: Το Back επιστρέφει μια αναφορά στο τελευταίο στοιχείο στην ουρά.
  • αδειάζω: Ελέγχει εάν η ουρά είναι κενή.
  • Μέγεθος: Επιστρέφει το μέγεθος της ουράς, δηλαδή τον αριθμό των στοιχείων στην ουρά.

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

#include #include using namespace std; void printQueue(queue myqueue) { queue secqueue = myqueue; while (!secqueue.empty()) { cout << ' ' << secqueue.front(); secqueue.pop(); } cout << ' '; } int main() { queue myqueue; myqueue.push(2); myqueue.push(4); myqueue.push(6); myqueue.push(8); cout << 'The queue myqueue is : '; printQueue(myqueue); cout << ' myqueue.size() : ' << myqueue.size(); cout << ' myqueue.front() : ' << myqueue.front(); cout << ' myqueue.back() : ' << myqueue.back(); cout << ' myqueue.pop() : '; myqueue.pop(); printQueue(myqueue); return 0; }

Παραγωγή:

Η ουρά myqueue είναι: 2 4 6 8

myqueue.size (): 4

myqueue.front (): 2

myqueue.back (): 8

ποιο είναι το καλύτερο λογισμικό απομάκρυνσης ιών

myqueue.pop (): 4 6 8

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

εμπορευματοκιβώτιο ουράς

συμπέρασμα

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

Στο επερχόμενο σεμινάριό μας, θα συζητήσουμε περισσότερα για την ουρά προτεραιότητας στο STL !!

=> Επισκεφθείτε εδώ για να μάθετε C ++ από το μηδέν.

Συνιστώμενη ανάγνωση

^