stack data structure c with illustration
βασικές ερωτήσεις συνέντευξης java με απαντήσεις
Όλα όσα πρέπει να γνωρίζετε για το Stack In C ++.
Το Stack είναι μια βασική δομή δεδομένων που χρησιμοποιείται για την αποθήκευση στοιχείων με γραμμικό τρόπο.
Ακολουθεί η στοίβα LIFO (τελευταία, πρώτη έξοδος) σειρά ή προσέγγιση στην οποία εκτελούνται οι εργασίες. Αυτό σημαίνει ότι το στοιχείο που προστέθηκε τελευταία στη στοίβα θα είναι το πρώτο στοιχείο που θα αφαιρεθεί από τη στοίβα.
=> Επισκεφθείτε εδώ για να δείτε ολόκληρη τη σειρά προπόνησης C ++ για όλους.
Τι θα μάθετε:
- Στοίβα σε C ++
Στοίβα σε C ++
Μια στοίβα είναι παρόμοια με τη στοίβα πραγματικής ζωής ή ένα σωρό πράγματα που στοιβάζουμε το ένα πάνω από το άλλο.
Δίνεται παρακάτω μια εικονική αναπαράσταση του Stack.
Όπως φαίνεται παραπάνω, υπάρχει ένας σωρός από πλάκες που στοιβάζονται το ένα πάνω στο άλλο. Εάν θέλουμε να προσθέσουμε ένα άλλο στοιχείο σε αυτό, τότε το προσθέτουμε στην κορυφή της στοίβας, όπως φαίνεται στην παραπάνω εικόνα (αριστερή πλευρά). Αυτή η λειτουργία προσθήκης ενός αντικειμένου στη στοίβα ονομάζεται ' Σπρώξτε '.
Στη δεξιά πλευρά, έχουμε δείξει μια αντίθετη λειτουργία, δηλαδή αφαιρούμε ένα στοιχείο από τη στοίβα. Αυτό γίνεται επίσης από το ίδιο άκρο, δηλαδή από την κορυφή της στοίβας. Αυτή η λειτουργία ονομάζεται ' Κρότος '.
Όπως φαίνεται στο παραπάνω σχήμα, βλέπουμε ότι το push και το pop πραγματοποιούνται από το ίδιο άκρο. Αυτό κάνει τη στοίβα να ακολουθεί τη σειρά LIFO. Η θέση ή το τέλος από το οποίο τα στοιχεία ωθούνται ή ξεδιπλώνονται προς / από τη στοίβα ονομάζεται ' Κορυφή της στοίβας '.
Αρχικά, όταν δεν υπάρχουν στοιχεία στη στοίβα, το πάνω μέρος της στοίβας έχει οριστεί σε -1. Όταν προσθέτουμε ένα στοιχείο στη στοίβα, το πάνω μέρος της στοίβας αυξάνεται κατά 1 υποδεικνύοντας ότι το στοιχείο έχει προστεθεί. Σε αντίθεση με αυτό, το πάνω μέρος της στοίβας μειώνεται κατά 1 όταν ένα στοιχείο βγαίνει από τη στοίβα.
Στη συνέχεια, θα δούμε μερικές από τις βασικές λειτουργίες της δομής δεδομένων στοίβας που θα απαιτήσουμε κατά την εφαρμογή της στοίβας.
Βασικές λειτουργίες
Ακολουθούν οι βασικές λειτουργίες που υποστηρίζονται από τη στοίβα.
- ώθηση - Προσθέτει ή ωθεί ένα στοιχείο στη στοίβα.
- ποπ - Αφαιρεί ή αναδύει ένα στοιχείο από τη στοίβα.
- ματιά - Παίρνει το κορυφαίο στοιχείο της στοίβας αλλά δεν την αφαιρεί.
- είναι γεμάτο - Δοκιμάζει εάν η στοίβα είναι γεμάτη.
- είναι άδειο - Ελέγχει εάν η στοίβα είναι άδεια.
Απεικόνιση
Η παραπάνω εικόνα δείχνει την ακολουθία των λειτουργιών που εκτελούνται στη στοίβα. Αρχικά, η στοίβα είναι κενή. Για μια κενή στοίβα, η κορυφή της στοίβας έχει οριστεί σε -1.
Στη συνέχεια, ωθούμε το στοιχείο 10 στη στοίβα. Βλέπουμε ότι η κορυφή της στοίβας δείχνει τώρα στο στοιχείο 10.
Στη συνέχεια, εκτελούμε μια άλλη λειτουργία ώθησης με το στοιχείο 20, με αποτέλεσμα η κορυφή της στοίβας να δείχνει τώρα στο 20. Αυτή η κατάσταση είναι η τρίτη εικόνα.
Τώρα στο τελευταίο σχήμα, εκτελούμε μια λειτουργία pop (). Ως αποτέλεσμα της λειτουργίας pop, το στοιχείο που δείχνει στην κορυφή της στοίβας αφαιρείται από τη στοίβα. Ως εκ τούτου, στο σχήμα, βλέπουμε ότι το στοιχείο 20 αφαιρείται από τη στοίβα. Έτσι, η κορυφή της στοίβας δείχνει τώρα στο 10.
Με αυτόν τον τρόπο, μπορούμε εύκολα να καταλάβουμε την προσέγγιση LIFO που χρησιμοποιείται από το stack.
Εκτέλεση
# 1) Χρήση συστοιχιών
Ακολουθεί η εφαρμογή C ++ της στοίβας με χρήση συστοιχιών:
#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack(MAX); //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack(++top) = item; cout< Παραγωγή:
Η στοίβα ώθησης
δύο
4
6
Το Stack Pop:
6
4
δύο
Στην έξοδο, μπορούμε να δούμε ότι τα στοιχεία ωθούνται στη στοίβα με μια σειρά και βγαίνουν από τη στοίβα με την αντίστροφη σειρά. Αυτό δείχνει την προσέγγιση LIFO (Last in, First out) για το stack.
Για την υλοποίηση του παραπάνω πίνακα της στοίβας, μπορούμε να συμπεράνουμε ότι αυτό είναι πολύ εύκολο να εφαρμοστεί καθώς δεν υπάρχουν δείκτες. Αλλά ταυτόχρονα, το μέγεθος της στοίβας είναι στατικό και η στοίβα δεν μπορεί να αναπτυχθεί ή να συρρικνωθεί δυναμικά.
Στη συνέχεια, θα εφαρμόσουμε τη στοίβα χρησιμοποιώντας πίνακες στη γλώσσα προγραμματισμού Java.
class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack() = new int(MAX); boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack(++top) = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack(top--); return item; } } } //Main class code class Main { public static void main(String args()) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } } Παραγωγή:
Στοίβα στοίβας:
1
3
5
Στοίβα ποπ:
5
3
1
Η λογική υλοποίησης είναι ίδια με την εφαρμογή C ++. Η έξοδος δείχνει την τεχνική LIFO να πιέζει και να βγαίνει έξω από τα στοιχεία προς / από τη στοίβα.
Όπως έχει ήδη αναφερθεί, η εφαρμογή στοίβας με χρήση συστοιχιών είναι η απλούστερη εφαρμογή, αλλά είναι στατικού χαρακτήρα, καθώς δεν μπορούμε να αναπτύξουμε ή να συρρικνώσουμε δυναμικά τη στοίβα.
# 2) Χρήση συνδεδεμένης λίστας
Στη συνέχεια, εφαρμόζουμε λειτουργίες στοίβας χρησιμοποιώντας μια συνδεδεμένη λίστα τόσο στο C ++ όσο και στο Java. Πρώτον, θα δείξουμε την εφαρμογή C ++.
πού χρησιμοποιείται σήμερα το c ++
#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'< Παραγωγή:
Στοίβα στοίβας:
100
200
300
Το κορυφαίο στοιχείο είναι 300
Στοίβα ποπ:
300
200
100
Το κορυφαίο στοιχείο είναι -1
Στη συνέχεια, παρουσιάζουμε την εφαρμογή Java της στοίβας χρησιμοποιώντας μια συνδεδεμένη λίστα.
class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String() args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } } Παραγωγή:
Στοίβα στοίβας:
100
200
300
Το κορυφαίο στοιχείο είναι 300
Στοίβα ποπ:
300
200
100
Η στοίβα είναι άδεια
Το κορυφαίο στοιχείο είναι -2147483648
Μόλις είδαμε εφαρμογές C ++ και Java για μια στοίβα χρησιμοποιώντας συνδεδεμένες λίστες. Αντιπροσωπεύουμε κάθε καταχώριση στοίβας ως κόμβο της συνδεδεμένης λίστας. Το πιο σημαντικό πλεονέκτημα αυτής της εφαρμογής είναι ότι είναι δυναμική. Αυτό σημαίνει ότι μπορούμε να αυξήσουμε ή να συρρικνώσουμε το μέγεθος στοίβας σύμφωνα με τις απαιτήσεις μας.
Αυτό σε αντίθεση με την περίπτωση υλοποίησης στοίβας με συστοιχίες στις οποίες πρέπει να δηλώσουμε το μέγεθος εκ των προτέρων και δεν μπορούμε να το αλλάξουμε δυναμικά.
Το μειονέκτημα αυτής της εφαρμογής είναι ότι καθώς χρησιμοποιούμε δείκτες παντού, καταλαμβάνει λίγο πολύ χώρο σε σύγκριση με την υλοποίηση πίνακα.
Εφαρμογές του Stack
Ας συζητήσουμε μερικές από τις εφαρμογές της δομής δεδομένων στοίβας. Η δομή δεδομένων στοίβας χρησιμοποιείται σε μια σειρά εφαρμογών στον προγραμματισμό λογισμικού κυρίως λόγω της απλότητας και της ευκολίας εφαρμογής.
Θα περιγράψουμε εν συντομία μερικές από τις εφαρμογές της στοίβας παρακάτω:
# 1) Επιδείξεις σε εκφράσεις μετά την επιδιόρθωση
Οποιαδήποτε γενική αριθμητική έκφραση έχει τη μορφή operand1 OP τελεστής 2 .
Με βάση τη θέση του χειριστή OP, έχουμε τους ακόλουθους τύπους εκφράσεων:
- Εμπήγω - Η γενική μορφή της έκφρασης infix είναι « operand1 OP τελεστής 2 '. Αυτή είναι η βασική μορφή της έκφρασης και χρησιμοποιούμε συνεχώς στα μαθηματικά.
- Πρόθεμα - Όταν ένας τελεστής τοποθετείται πριν από τους τελεστές, είναι μια έκφραση προθέματος. Η γενική μορφή της έκφρασης infix είναι « OP τελεστής1 τελεστής2 '.
- Postfix - Στις εκφράσεις μετά την επιδιόρθωση, οι τελεστές γράφονται πρώτα και ακολουθεί ο χειριστής. Έχει τη μορφή 'operand1 operand2 OP'.
Εξετάστε την έκφραση «a + b * c ' . Ο μεταγλωττιστής σαρώνει την έκφραση είτε από αριστερά προς δεξιά είτε από δεξιά προς αριστερά. Φροντίζοντας την υπεροχή του χειριστή και τη συσχέτιση, θα σαρώσει πρώτα την έκφραση για να αξιολογήσει την έκφραση b * c. Στη συνέχεια, θα πρέπει ξανά να σαρώσει την έκφραση για να προσθέσει το αποτέλεσμα του b * c στο a.
Καθώς οι εκφράσεις γίνονται όλο και πιο περίπλοκες, αυτό το είδος προσέγγισης της σάρωσης της έκφρασης ξανά και ξανά καθίσταται αναποτελεσματική.
Προκειμένου να ξεπεραστεί αυτή η αναποτελεσματικότητα, μετατρέπουμε την έκφραση σε postfix ή πρόθεμα έτσι ώστε να μπορούν να αξιολογηθούν εύκολα χρησιμοποιώντας μια δομή δεδομένων στοίβας.
# 2) Ανάλυση / αξιολόγηση έκφρασης
Χρησιμοποιώντας στοίβα, μπορούμε επίσης να πραγματοποιήσουμε πραγματική αξιολόγηση έκφρασης. Σε αυτό, η έκφραση σαρώνεται αριστερά προς τα δεξιά και οι τελεστές ωθούνται στη στοίβα.
Κάθε φορά που αντιμετωπίζεται ένας χειριστής, οι τελεστές εμφανίζονται και η λειτουργία εκτελείται. Το αποτέλεσμα της λειτουργίας ωθείται ξανά στη στοίβα. Αυτός ο τρόπος με τον οποίο η έκφραση αξιολογείται χρησιμοποιώντας στοίβα και το τελικό αποτέλεσμα της έκφρασης είναι συνήθως η τρέχουσα κορυφή της στοίβας.
# 3) Διασχίσεις δέντρων
Η δομή των δέντρων δεδομένων μπορεί να διασχίσει για να επισκεφτεί κάθε κόμβο με πολλούς τρόπους και ανάλογα με το πότε ο ριζικός κόμβος έχει επισκεφθεί.
- inOrder εγκάρσια
- προπαραγγελία διέλευσης
- μετά την παραγγελία
Για να διασχίσουμε αποτελεσματικά το δέντρο, χρησιμοποιούμε τη δομή δεδομένων στοίβας προκειμένου να ωθήσουμε τους ενδιάμεσους κόμβους στη στοίβα έτσι ώστε να διατηρούμε τη σειρά της διέλευσης.
# 4) Αλγόριθμοι ταξινόμησης
Οι αλγόριθμοι ταξινόμησης όπως η γρήγορη ταξινόμηση μπορούν να γίνουν πιο αποτελεσματικοί χρησιμοποιώντας τις δομές δεδομένων στοίβας.
# 5) Πύργοι του Ανόι
Αυτό είναι ένα κλασικό πρόβλημα που περιλαμβάνει n αριθμό δίσκων και τρεις πύργους και το πρόβλημα αφορά τη μετακίνηση των δίσκων από τον ένα πύργο στον άλλο με τον τρίτο πύργο να χρησιμοποιείται ως ενδιάμεσος.
Αυτό το πρόβλημα μπορεί να αντιμετωπιστεί αποτελεσματικά χρησιμοποιώντας τη στοίβα καθώς πιέζουμε τους δίσκους να μετακινηθούν στη στοίβα καθώς η στοίβα βασικά λειτουργεί ως πύργος που χρησιμοποιείται για την κίνηση των δίσκων.
συμπέρασμα
Η στοίβα είναι η απλούστερη δομή δεδομένων και ευκολότερη εφαρμογή ως πρόγραμμα. Χρησιμοποίησε την προσέγγιση LIFO (last in, first out) που σημαίνει ότι το στοιχείο που εισήχθη τελευταίο είναι αυτό που αφαιρείται πρώτα. Αυτό συμβαίνει επειδή η στοίβα χρησιμοποιεί μόνο ένα άκρο για να προσθέσει (push) και να αφαιρέσει (pop) στοιχεία.
Η δομή δεδομένων στοίβας έχει πολλές χρήσεις στον προγραμματισμό λογισμικού. Το σημαντικότερο μεταξύ αυτών είναι οι αξιολογήσεις έκφρασης. Η αξιολόγηση έκφρασης περιλαμβάνει επίσης τη μετατροπή της έκφρασης από infix σε postfix ή πρόθεμα. Περιλαμβάνει επίσης την αξιολόγηση της έκφρασης για να παράγει το τελικό αποτέλεσμα.
Σε αυτό το σεμινάριο, έχουμε δει την απεικόνιση και την εφαρμογή της στοίβας, καθώς και τις διάφορες λειτουργίες της.
Στο επερχόμενο σεμινάριό μας, θα μάθουμε λεπτομερώς για τη δομή δεδομένων ουράς.
=> Επισκεφθείτε εδώ για το πλήρες μάθημα C ++ από ειδικούς.
Συνιστώμενη ανάγνωση
- Δομή δεδομένων ουράς σε C ++ με απεικόνιση
- Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Δομή δεδομένων συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση
- Διπλά συνδεδεμένη δομή δεδομένων λίστας σε C ++ με απεικόνιση
- Εισαγωγή στις δομές δεδομένων στο C ++
- Παράμετρος δεδομένων JMeter με χρήση μεταβλητών καθορισμένων από τον χρήστη
- 10+ καλύτερα εργαλεία συλλογής δεδομένων με στρατηγικές συλλογής δεδομένων