Στοίβα C++ STL με Παράδειγμα

Με: Μπέντζαμιν Γουόκερ Μπέντζαμιν Γουόκερ
Hours Ενημερώθηκε

Τι είναι το std::stack;

Μια στοίβα είναι μια δομή δεδομένων που λειτουργεί με βάση την τεχνική LIFO (Last In First Out). Η στοίβα std:: επιτρέπει την προσθήκη και αφαίρεση στοιχείων μόνο από το ένα άκρο.

Η κλάση std::stack είναι ένας προσαρμογέας κοντέινερ. Τα αντικείμενα κοντέινερ διατηρούν δεδομένα παρόμοιου τύπου δεδομένων. Μπορείτε να δημιουργήσετε μια στοίβα από διάφορα δοχεία ακολουθίας. Εάν δεν παρέχεται κοντέινερ, το κοντέινερ θα χρησιμοποιηθεί από προεπιλογή. Οι προσαρμογείς κοντέινερ δεν υποστηρίζουν επαναλήπτες, επομένως δεν μπορούν να χρησιμοποιηθούν για χειρισμό δεδομένων.

Σύνταξη στοίβας

Για να δημιουργήσουμε μια στοίβα, πρέπει να συμπεριλάβουμε το αρχείο κεφαλίδας στον κώδικά μας. Στη συνέχεια χρησιμοποιούμε αυτή τη σύνταξη για να ορίσουμε το std::stack:

template <class Type, class Container = deque<Type> > class stack;
  • Χαρακτηριστικά – είναι ο τύπος του στοιχείου που περιέχεται στο std::stack. Μπορεί να ισχύει οποιοδήποτε C++ τύπο ή ακόμα και τύπο που ορίζεται από το χρήστη.
  • Δοχείο – είναι ο τύπος του υποκείμενου αντικειμένου κοντέινερ.

Τύποι μελών

Ακολουθούν οι τύποι μελών στοίβας:

  • value_type- Η πρώτη παράμετρος προτύπου, T. Δηλώνει τους τύπους στοιχείων.
  • container_type- Η δεύτερη παράμετρος προτύπου, Container. Υποδηλώνει τον τύπο του υποκείμενου δοχείου.
  • size_type- Ανυπόγραφο ακέραιο τύπο.

Operaθέσεις στο Stack

A C++ Η στοίβα υποστηρίζει τις ακόλουθες βασικές λειτουργίες:

  • push – Προσθέτει/σπρώχνει ένα αντικείμενο στη στοίβα.
  • pop – Αφαιρεί/βγάζει ένα στοιχείο από τη στοίβα.
  • peek – Επιστρέφει το επάνω στοιχείο της στοίβας χωρίς να το αφαιρέσετε.
  • isFull – Ελέγχει εάν μια στοίβα είναι γεμάτη.
  • isEmpty – Ελέγχει εάν μια στοίβα είναι άδεια.

Υλοποίηση στοίβας

Υλοποίηση στοίβας

Βήμα 1) Αρχικά έχουμε μια άδεια στοίβα. Η κορυφή μιας άδειας στοίβας έχει οριστεί σε -1.

Βήμα 2) Στη συνέχεια, έχουμε σπρώξει το στοιχείο 5 στη στοίβα. Η κορυφή της στοίβας θα δείχνει στο στοιχείο 5.

Βήμα 3) Στη συνέχεια, έχουμε σπρώξει το στοιχείο 50 στη στοίβα. Η κορυφή της στοίβας μετατοπίζεται και δείχνει στο στοιχείο 50.

Βήμα 4) Στη συνέχεια, εκτελέσαμε μια λειτουργία pop, αφαιρώντας το επάνω στοιχείο από τη στοίβα. Το στοιχείο 50 βγαίνει από τη στοίβα. Η κορυφή της στοίβας δείχνει τώρα στο στοιχείο 5.

push() και pop()

Οι συναρτήσεις stack::push() προσθέτουν νέο στοιχείο στην κορυφή της στοίβας. Το μέγεθος της στοίβας αυξάνεται κατά 1 μετά την εισαγωγή. Η συνάρτηση παίρνει αυτή τη σύνταξη:

stack.push(value)

Η τιμή είναι το στοιχείο που πρέπει να εισαχθεί στη στοίβα.

Η συνάρτηση stack:: pop() αφαιρεί το επάνω στοιχείο της στοίβας. Αυτό είναι το νεότερο στοιχείο της στοίβας. Το μέγεθος της στοίβας μειώνεται κατά 1 μετά την αφαίρεση. Εδώ είναι η σύνταξη της συνάρτησης:

stack.pop()

Η συνάρτηση δεν λαμβάνει παραμέτρους.

Παράδειγμα 1:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

Παραγωγή:

push() και pop()

Εδώ είναι ένα στιγμιότυπο οθόνης του κώδικα:

push() και pop()

Επεξήγηση κώδικα:

  1. Συμπεριλάβετε το αρχείο κεφαλίδας iostream στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  2. Συμπεριλάβετε το αρχείο κεφαλίδας στοίβας στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  3. Συμπεριλάβετε τον χώρο ονομάτων std στον κώδικά μας για να χρησιμοποιήσετε τις κλάσεις του χωρίς να τον καλέσετε.
  4. Καλέστε τη συνάρτηση main(). Η λογική του προγράμματος πρέπει να προστεθεί σε αυτήν τη συνάρτηση.
  5. Δημιουργήστε μια στοίβα st για να αποθηκεύσετε ακέραιες τιμές.
  6. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε την τιμή 10 στη στοίβα.
  7. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε την τιμή 20 στη στοίβα.
  8. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε την τιμή 30 στη στοίβα.
  9. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε την τιμή 40 στη στοίβα.
  10. Χρησιμοποιήστε τη συνάρτηση pop() για να αφαιρέσετε το επάνω στοιχείο από τη στοίβα, δηλαδή 40. Το επάνω στοιχείο γίνεται τώρα 30.
  11. Χρησιμοποιήστε τη συνάρτηση pop() για να αφαιρέσετε το επάνω στοιχείο από τη στοίβα, δηλαδή 30. Το επάνω στοιχείο γίνεται τώρα 20.
  12. Χρησιμοποιήστε έναν βρόχο while και τη συνάρτηση vala() για να ελέγξετε αν η στοίβα ΔΕΝ είναι άδεια. το ! ΔΕΝ είναι ο χειριστής.
  13. Εκτύπωση του τρέχοντος περιεχομένου της στοίβας στην κονσόλα.
  14. Καλέστε τη συνάρτηση pop() στη στοίβα.
  15. Τέλος του σώματος του βρόχου while.
  16. Τέλος του σώματος της συνάρτησης main().

κενό(), μέγεθος(), κορυφή()

Οι στοίβες έχουν ενσωματωμένες λειτουργίες που μπορείτε να χρησιμοποιήσετε για να παίξετε με τη στοίβα και τις τιμές της. Αυτά περιλαμβάνουν:

  • vala()- ελέγχει εάν μια στοίβα είναι άδεια ή όχι.
  • size()- επιστρέφει το μέγεθος της στοίβας, δηλαδή τον αριθμό των στοιχείων σε μια στοίβα.
  • top()- έχει πρόσβαση στο στοιχείο στοίβας στην κορυφή.

ΣΧΕΤΙΚΑ ΑΡΘΡΑ

Παράδειγμα 2:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

Παραγωγή:

κενή(),μέγεθος(),κορυφή()

Εδώ είναι ένα στιγμιότυπο οθόνης του κώδικα:

κενή(),μέγεθος(),κορυφή()

Επεξήγηση κώδικα:

  1. Συμπεριλάβετε το αρχείο κεφαλίδας iostream στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  2. Συμπεριλάβετε το αρχείο κεφαλίδας στοίβας στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  3. Συμπεριλάβετε τον χώρο ονομάτων std στο πρόγραμμά μας για να χρησιμοποιήσετε τις κλάσεις του χωρίς να τον καλέσετε.
  4. Δημιουργήστε τη συνάρτηση createStack που μπορούμε να χρησιμοποιήσουμε για να δημιουργήσουμε τη στοίβα mystack. Η στοίβα θα περιέχει ένα σύνολο ακεραίων.
  5. Η αρχή του σώματος της συνάρτησης createStack.
  6. Δημιουργήστε ένα στιγμιότυπο του τύπου δεδομένων mystack και δίνοντάς του το όνομα ms.
  7. Χρησιμοποιήστε τον βρόχο while και τη συνάρτηση vala() για να ελέγξετε αν η στοίβα είναι άδεια.
  8. Η αρχή του σώματος του βρόχου while.
  9. Χρησιμοποιήστε τη συνάρτηση top() που είναι αποθηκευμένη στο επάνω μέρος της στοίβας. Ο χαρακτήρας \t θα δημιουργήσει μια νέα καρτέλα.
  10. Χρησιμοποιήστε τη συνάρτηση pop() για να διαγράψετε το στοιχείο στην κορυφή της στοίβας.
  11. Τέλος του σώματος του βρόχου while.
  12. Εκτυπώστε μια κενή γραμμή στην κονσόλα.
  13. Τέλος του σώματος της συνάρτησης createStack.
  14. Καλέστε τη συνάρτηση main(). Η λογική του προγράμματος πρέπει να προστεθεί στο σώμα της συνάρτησης main().
  15. Η αρχή του σώματος της συνάρτησης main().
  16. Δημιουργήστε ένα αντικείμενο στοίβας st.
  17. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε το στοιχείο 32 στη στοίβα.
  18. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε το στοιχείο 21 στη στοίβα.
  19. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε το στοιχείο 39 στη στοίβα.
  20. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε το στοιχείο 89 στη στοίβα.
  21. Χρησιμοποιήστε τη συνάρτηση push() για να εισαγάγετε το στοιχείο 25 στη στοίβα.
  22. Εκτυπώστε λίγο κείμενο στην κονσόλα.
  23. Καλέστε τη συνάρτηση createStack για να εκτελέσετε τις παραπάνω λειτουργίες εισαγωγής στη στοίβα.
  24. Εκτυπώστε το μέγεθος της στοίβας στην κονσόλα μαζί με άλλο κείμενο.
  25. Εκτυπώστε το στοιχείο στο επάνω μέρος της στοίβας στην κονσόλα.
  26. Εκτυπώστε λίγο κείμενο στην κονσόλα.
  27. Διαγράψτε το στοιχείο στην κορυφή της στοίβας. Στη συνέχεια θα επιστρέψει τα στοιχεία που παραμένουν στη στοίβα.
  28. Καλέστε τη συνάρτηση createStack για να εκτελέσετε τις παραπάνω λειτουργίες.
  29. Το πρόγραμμα πρέπει να επιστρέψει τιμή μετά την επιτυχή ολοκλήρωση.
  30. Τέλος του σώματος της συνάρτησης main().

emplace() και swap()

Αυτές είναι άλλες ενσωματωμένες λειτουργίες στοίβας:

  • emplace()- κατασκευάζει και στη συνέχεια εισάγει νέο στοιχείο στην κορυφή της στοίβας.
  • swap()- ανταλλάσσει τα περιεχόμενα της στοίβας με τα περιεχόμενα μιας άλλης στοίβας.

Παράδειγμα 3:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

Παραγωγή:

emplace()& swap()

Εδώ είναι ένα στιγμιότυπο οθόνης του κώδικα:

emplace()& swap()

Επεξήγηση κώδικα:

  1. Συμπεριλάβετε το αρχείο κεφαλίδας iostream στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  2. Συμπεριλάβετε το αρχείο κεφαλίδας στοίβας στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  3. Συμπεριλάβετε το αρχείο κεφαλίδας cstdlib στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  4. Συμπεριλάβετε τον χώρο ονομάτων std στον κώδικά μας για να χρησιμοποιήσετε τις κλάσεις του χωρίς να τον καλέσετε.
  5. Καλέστε τη συνάρτηση main(). Η λογική του προγράμματος θα προστεθεί στο σώμα αυτής της συνάρτησης.
  6. Δηλώστε μια στοίβα με το όνομα st1 για αποθήκευση ακέραιων τιμών.
  7. Δηλώστε μια στοίβα με το όνομα st2 για αποθήκευση ακέραιων τιμών.
  8. Χρησιμοποιήστε τη συνάρτηση emplace() για να εισαγάγετε τον ακέραιο αριθμό 12 στη στοίβα με το όνομα st1.
  9. Χρησιμοποιήστε τη συνάρτηση emplace() για να εισαγάγετε τον ακέραιο αριθμό 19 στη στοίβα με το όνομα st1.
  10. Χρησιμοποιήστε τη συνάρτηση emplace() για να εισαγάγετε τον ακέραιο αριθμό 20 στη στοίβα με το όνομα st2.
  11. Χρησιμοποιήστε τη συνάρτηση emplace() για να εισαγάγετε τον ακέραιο αριθμό 23 στη στοίβα με το όνομα st2.
  12. Χρησιμοποιήστε τη συνάρτηση swap() για να ανταλλάξετε τα περιεχόμενα των δύο στοίβων, st1 και st2. Τα περιεχόμενα της στοίβας st1 θα πρέπει να μετακινηθούν στη στοίβα st2. Τα περιεχόμενα της στοίβας st2 θα πρέπει να μετακινηθούν στη στοίβα st1.
  13. Εκτυπώστε λίγο κείμενο στην κονσόλα.
  14. Χρησιμοποιήστε τη δήλωση while και τη συνάρτηση vala() για να ελέγξετε αν η στοίβα st1 δεν είναι άδεια.
  15. Εκτυπώστε τα περιεχόμενα της στοίβας st1 στην κονσόλα. Το " " προσθέτει χώρο μεταξύ των στοιχείων στοίβας όταν τα εκτυπώνετε στην κονσόλα.
  16. Εκτελέστε τη συνάρτηση pop() στη στοίβα st1 για να αφαιρέσετε το επάνω στοιχείο.
  17. Τέλος του σώματος της δήλωσης while.
  18. Εκτυπώστε λίγο κείμενο στην κονσόλα. Το endl είναι α C++ λέξη-κλειδί για την τελική γραμμή. Μετακινεί τον κέρσορα του ποντικιού στην επόμενη γραμμή για να ξεκινήσει η εκτύπωση από εκεί.
  19. Χρησιμοποιήστε τη δήλωση while και τη συνάρτηση vala() για να ελέγξετε αν η στοίβα st2 δεν είναι άδεια.
  20. Εκτυπώστε τα περιεχόμενα της στοίβας st2 στην κονσόλα. Το " " προσθέτει χώρο μεταξύ των στοιχείων στοίβας όταν τα εκτυπώνετε στην κονσόλα.
  21. Εκτελέστε τη συνάρτηση pop() στη στοίβα st2 για να αφαιρέσετε το επάνω στοιχείο.
  22. Τέλος του σώματος της δήλωσης while.
  23. Τέλος του σώματος της συνάρτησης main().

Στοίβα σε STL

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

stack<T> st;

Η παραπάνω σύνταξη δηλώνει μια στοίβα st σε στοιχεία του τύπου δεδομένων T.

Παράδειγμα 4:

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

Παραγωγή:

Στοίβα σε STL

Εδώ είναι ένα στιγμιότυπο οθόνης του κώδικα:

Στοίβα σε STL

Επεξήγηση κώδικα:

  1. Συμπεριλάβετε το αρχείο κεφαλίδας iostream στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  2. Συμπεριλάβετε το αρχείο κεφαλίδας στοίβας στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  3. Συμπεριλάβετε το αρχείο κεφαλίδας cstdlib στον κώδικά μας για να χρησιμοποιήσετε τις λειτουργίες του.
  4. Συμπεριλάβετε τον χώρο ονομάτων std στον κώδικά μας για να χρησιμοποιήσετε τις κλάσεις του χωρίς να τον καλέσετε.
  5. Καλέστε τη συνάρτηση main(). Η λογική του προγράμματος πρέπει να προστεθεί στο σώμα αυτής της συνάρτησης.
  6. Δηλώστε μια στοίβα st για να αποθηκεύσετε ακέραια δεδομένα.
  7. Προσθέστε το στοιχείο 12 στη στοίβα.
  8. Προσθέστε το στοιχείο 19 στη στοίβα.
  9. Προσθέστε το στοιχείο 20 στη στοίβα.
  10. Εκτυπώστε το στοιχείο στο επάνω μέρος της στοίβας στην κονσόλα.
  11. Εκτυπώστε το μέγεθος της στοίβας στην κονσόλα.
  12. Τέλος του σώματος της συνάρτησης main().

Σύνοψη

  • Μια στοίβα είναι μια δομή δεδομένων που λειτουργεί με βάση την τεχνική LIFO (Last In First Out).
  • Το std::stack επιτρέπει μόνο την προσθήκη και την αφαίρεση στοιχείων από το ένα άκρο.
  • Η κλάση std::stack είναι ένας προσαρμογέας κοντέινερ, που περιέχει στοιχεία παρόμοιου τύπου δεδομένων.
  • Μια στοίβα μπορεί να δημιουργηθεί από διάφορα δοχεία ακολουθίας.
  • Εάν δεν παρέχετε ένα κοντέινερ, το κοντέινερ deque θα χρησιμοποιηθεί από προεπιλογή.
  • Η συνάρτηση push() είναι για την εισαγωγή στοιχείων στη στοίβα.
  • Η συνάρτηση pop() είναι για την αφαίρεση του επάνω στοιχείου από το βήμα.
  • Η συνάρτηση άδεια() είναι για τον έλεγχο εάν μια στοίβα είναι άδεια ή όχι.

Μπορεί να σας αρέσει: