Σε αυτό το σεμινάριο, θα μάθετε για τη δομή δεδομένων στοίβας και την εφαρμογή της σε Python, Java και C / C ++.
Μια στοίβα είναι μια χρήσιμη δομή δεδομένων στον προγραμματισμό. Είναι σαν ένα σωρό πιάτων που διατηρούνται το ένα πάνω στο άλλο.
![](https://cdn.wiki-base.com/4858191/stack_data_structure_and_implementation_in_python-_java_and_cc.png.webp)
Σκεφτείτε τα πράγματα που μπορείτε να κάνετε με ένα τέτοιο σωρό πιάτων
- Βάλτε ένα νέο πιάτο πάνω
- Αφαιρέστε την επάνω πλάκα
Εάν θέλετε την πλάκα στο κάτω μέρος, πρέπει πρώτα να αφαιρέσετε όλες τις πλάκες από πάνω. Μια τέτοια ρύθμιση ονομάζεται Last In First Out - το τελευταίο στοιχείο που είναι το πρώτο στοιχείο που βγαίνει.
LIFO Αρχή της στοίβας
Σε όρους προγραμματισμού, η τοποθέτηση ενός στοιχείου στην κορυφή της στοίβας ονομάζεται push και η αφαίρεση ενός στοιχείου ονομάζεται pop .
![](https://cdn.wiki-base.com/4858191/stack_data_structure_and_implementation_in_python-_java_and_cc_2.png.webp)
Στην παραπάνω εικόνα, αν και το στοιχείο 2 διατηρήθηκε τελευταίο, καταργήθηκε πρώτα - επομένως ακολουθεί την αρχή Last In First Out (LIFO) .
Μπορούμε να εφαρμόσουμε μια στοίβα σε οποιαδήποτε γλώσσα προγραμματισμού όπως C, C ++, Java, Python ή C #, αλλά η προδιαγραφή είναι σχεδόν η ίδια.
Βασικές λειτουργίες του Stack
Μια στοίβα είναι ένα αντικείμενο (ένας αφηρημένος τύπος δεδομένων - ADT) που επιτρέπει τις ακόλουθες λειτουργίες:
- Push : Προσθέστε ένα στοιχείο στην κορυφή μιας στοίβας
- Pop : Αφαιρέστε ένα στοιχείο από την κορυφή μιας στοίβας
- IsEmpty : Ελέγξτε εάν η στοίβα είναι κενή
- IsFull : Ελέγξτε εάν η στοίβα είναι πλήρης
- Peek : Λάβετε την τιμή του κορυφαίου στοιχείου χωρίς να το αφαιρέσετε
Εργασία της δομής δεδομένων στοίβας
Οι λειτουργίες λειτουργούν ως εξής:
- Ένας δείκτης που ονομάζεται TOP χρησιμοποιείται για να παρακολουθεί το κορυφαίο στοιχείο στη στοίβα.
- Κατά την προετοιμασία της στοίβας, ορίζουμε την τιμή της σε -1, ώστε να μπορούμε να ελέγξουμε εάν η στοίβα είναι κενή συγκρίνοντας
TOP == -1
. - Πατώντας ένα στοιχείο, αυξάνουμε την τιμή του TOP και τοποθετούμε το νέο στοιχείο στη θέση που δείχνει το TOP.
- Κατά την εμφάνιση ενός στοιχείου, επιστρέφουμε το στοιχείο που επισημαίνεται από το TOP και μειώνουμε την αξία του.
- Πριν το σπρώξουμε, ελέγχουμε αν η στοίβα είναι ήδη γεμάτη
- Πριν από την εμφάνιση, ελέγχουμε εάν η στοίβα είναι ήδη άδεια
![](https://cdn.wiki-base.com/4858191/stack_data_structure_and_implementation_in_python-_java_and_cc_3.png.webp)
Εφαρμογές στοίβας σε Python, Java, C και C ++
Η πιο κοινή εφαρμογή στοίβας είναι η χρήση συστοιχιών, αλλά μπορεί επίσης να εφαρμοστεί χρησιμοποιώντας λίστες.
Python Java C C + # Stack implementation in python # Creating a stack def create_stack(): stack = () return stack # Creating an empty stack def check_empty(stack): return len(stack) == 0 # Adding items into the stack def push(stack, item): stack.append(item) print("pushed item: " + item) # Removing an element from the stack def pop(stack): if (check_empty(stack)): return "stack is empty" return stack.pop() stack = create_stack() push(stack, str(1)) push(stack, str(2)) push(stack, str(3)) push(stack, str(4)) print("popped item: " + pop(stack)) print("stack after popping an element: " + str(stack))
// Stack implementation in Java class Stack ( private int arr(); private int top; private int capacity; // Creating a stack Stack(int size) ( arr = new int(size); capacity = size; top = -1; ) // Add elements into stack public void push(int x) ( if (isFull()) ( System.out.println("OverFlowProgram Terminated"); System.exit(1); ) System.out.println("Inserting " + x); arr(++top) = x; ) // Remove element from stack public int pop() ( if (isEmpty()) ( System.out.println("STACK EMPTY"); System.exit(1); ) return arr(top--); ) // Utility function to return the size of the stack public int size() ( return top + 1; ) // Check if the stack is empty public Boolean isEmpty() ( return top == -1; ) // Check if the stack is full public Boolean isFull() ( return top == capacity - 1; ) public void printStack() ( for (int i = 0; i <= top; i++) ( System.out.println(arr(i)); ) ) public static void main(String() args) ( Stack stack = new Stack(5); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.pop(); System.out.println("After popping out"); stack.printStack(); ) )
// Stack implementation in C #include #include #define MAX 10 int count = 0; // Creating a stack struct stack ( int items(MAX); int top; ); typedef struct stack st; void createEmptyStack(st *s) ( s->top = -1; ) // Check if the stack is full int isfull(st *s) ( if (s->top == MAX - 1) return 1; else return 0; ) // Check if the stack is empty int isempty(st *s) ( if (s->top == -1) return 1; else return 0; ) // Add elements into stack void push(st *s, int newitem) ( if (isfull(s)) ( printf("STACK FULL"); ) else ( s->top++; s->items(s->top) = newitem; ) count++; ) // Remove element from stack void pop(st *s) ( if (isempty(s)) ( printf(" STACK EMPTY "); ) else ( printf("Item popped= %d", s->items(s->top)); s->top--; ) count--; printf(""); ) // Print elements of stack void printStack(st *s) ( printf("Stack: "); for (int i = 0; i items(i)); ) printf(""); ) // Driver code int main() ( int ch; st *s = (st *)malloc(sizeof(st)); createEmptyStack(s); push(s, 1); push(s, 2); push(s, 3); push(s, 4); printStack(s); pop(s); printf("After popping out"); printStack(s); )
// Stack implementation in C++ #include #include using namespace std; #define MAX 10 int size = 0; // Creating a stack struct stack ( int items(MAX); int top; ); typedef struct stack st; void createEmptyStack(st *s) ( s->top = -1; ) // Check if the stack is full int isfull(st *s) ( if (s->top == MAX - 1) return 1; else return 0; ) // Check if the stack is empty int isempty(st *s) ( if (s->top == -1) return 1; else return 0; ) // Add elements into stack void push(st *s, int newitem) ( if (isfull(s)) ( printf("STACK FULL"); ) else ( s->top++; s->items(s->top) = newitem; ) size++; ) // Remove element from stack void pop(st *s) ( if (isempty(s)) ( printf(" STACK EMPTY "); ) else ( printf("Item popped= %d", s->items(s->top)); s->top--; ) size--; cout << endl; ) // Print elements of stack void printStack(st *s) ( printf("Stack: "); for (int i = 0; i < size; i++) ( cout
Stack Time Complexity
For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1)
.
Applications of Stack Data Structure
Although stack is a simple data structure to implement, it is very powerful. The most common uses of a stack are:
- To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
- In compilers - Compilers use the stack to calculate the value of expressions like
2 + 4 / 5 * (7 - 9)
by converting the expression to prefix or postfix form.
- In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.