Κατανόηση της υλοποίησης Stack στην Python

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

Ας μάθουμε για τη στοίβα και την υλοποίησή της στην Python.

Τι είναι μια Στοίβα;

Μια στοίβα είναι παρόμοια με το σωρό από βιβλία, καρέκλες κ.λπ., στην πραγματική ζωή. Και ακολουθεί την αρχή Last-in/First-out (LIFO). Είναι η απλούστερη δομή δεδομένων. Ας δούμε το σενάριο με ένα πραγματικό παράδειγμα.

Ας πούμε ότι έχουμε ένα σωρό βιβλία ως εξής.

Όταν θέλουμε το τρίτο βιβλίο από την κορυφή τότε, πρέπει να αφαιρέσουμε τα δύο πρώτα βιβλία από την κορυφή για να βγάλουμε το τρίτο βιβλίο. Εδώ, το κορυφαίο βιβλίο πηγαίνει τελευταίο στο σωρό και έρχεται πρώτο στη στοίβα. Η στοίβα δομής δεδομένων ακολουθεί την ίδια αρχή Last-in/First-out (LIFO) στον προγραμματισμό.

Λειτουργίες στο Stack

Υπάρχουν κυρίως δύο λειτουργίες σε μια στοίβα

1. push (δεδομένα)

Προσθέτει ή ωθεί τα δεδομένα στη στοίβα.

2. pop()

Αφαιρεί ή βγάζει το ανώτατο στοιχείο από τη στοίβα.

Δείτε τις παρακάτω εικόνες των λειτουργιών push και pop.

Θα γράψουμε μερικές βοηθητικές συναρτήσεις που μας βοηθούν να λάβουμε περισσότερες πληροφορίες για τη στοίβα.

Ας τους δούμε.

κρυφοκοίταγμα()

Επιστρέφει το ανώτατο στοιχείο από τη στοίβα.

είναι άδειο()

Επιστρέφει είτε η στοίβα είναι άδεια είτε όχι.

Αρκετές εννοιολογικές πτυχές της δομής δεδομένων στοίβας. Ας μεταβούμε στην υλοποίηση χωρίς περαιτέρω καθυστέρηση.

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

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

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

Ας τα δούμε όλα ένα προς ένα.

#1. Λίστα

Θα υλοποιήσουμε τη στοίβα χρησιμοποιώντας τη λίστα σε μια τάξη. Ας δούμε τη βήμα προς βήμα υλοποίηση της στοίβας.

Βήμα 1: Γράψτε μια τάξη που ονομάζεται Stack.

class Stack:
	pass

Βήμα 2: Πρέπει να διατηρήσουμε τα δεδομένα σε μια λίστα. Ας προσθέσουμε μια κενή λίστα στην κλάση Stack με στοιχεία ονόματος.

class Stack:
	def __init__(self):
		self.elements = []

Βήμα 3: Για να ωθήσουμε τα στοιχεία στη στοίβα, χρειαζόμαστε μια μέθοδο. Ας γράψουμε μια μέθοδο push που λαμβάνει δεδομένα ως όρισμα και τα προσαρτούμε στη λίστα στοιχείων.

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, data):
		self.elements.append(data)
		return data

Βήμα 4: Ομοίως, ας γράψουμε τη μέθοδο pop που βγάζει το ανώτατο στοιχείο από τη στοίβα. Μπορούμε να χρησιμοποιήσουμε τη μέθοδο pop του τύπου δεδομένων λίστας.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

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

Βήμα 5: Μπορούμε να πάρουμε το ανώτατο στοιχείο από τη στοίβα χρησιμοποιώντας τον αρνητικό δείκτη. Το στοιχείο κωδικού [-1] επιστρέφει το τελευταίο της λίστας. Είναι το κορυφαίο στοιχείο της στοίβας στην περίπτωσή μας.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

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

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

Ολοκληρώσαμε την υλοποίηση της στοίβας χρησιμοποιώντας τον τύπο δεδομένων λίστας.

Ω! περίμενε μόλις το εφαρμόσαμε. Όμως, δεν είδα πώς να το χρησιμοποιήσω. Πώς να το χρησιμοποιήσετε τότε;

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

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

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

• Ελέγξτε εάν η στοίβα είναι άδεια ή όχι χρησιμοποιώντας τη μέθοδο is_empty. Θα πρέπει να επιστρέψει True.
• Σπρώξτε τους αριθμούς 1, 2, 3, 4, 5 στη στοίβα χρησιμοποιώντας τη μέθοδο ώθησης.
• Η μέθοδος is_empty θα πρέπει να επιστρέψει False. Ελεγξέ το.
• Εκτυπώστε το επάνω στοιχείο χρησιμοποιώντας τη μέθοδο peek.
• Βγάλτε το στοιχείο από τη στοίβα χρησιμοποιώντας τη μέθοδο pop.
• Ελέγξτε το στοιχείο peek. Θα πρέπει να επιστρέψει το στοιχείο 4.
• Τώρα, βγάλτε όλα τα στοιχεία από τη στοίβα.
• Η μέθοδος is_empty θα πρέπει να επιστρέψει True. Ελεγξέ το.

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

Έγραψες τον κωδικό; Όχι, μην ανησυχείτε, ελέγξτε τον παρακάτω κωδικό.

class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
    
    def pop(self): 
        return self.elements.pop() 
        
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()
    
    ## checking is_empty method -> true
    print(stack.is_empty())

    ## pushing the elements
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## again checking is_empty method -> false
    print(stack.is_empty())

    ## printing the topmost element of the stack -> 5
    print(stack.peek())

    ## popping the topmost element -> 5
    stack.pop()

    ## checking the topmost element using peek method -> 4
    print(stack.peek())

    ## popping all the elements
    stack.pop()
    stack.pop() 
    stack.pop() 
    stack.pop() 

    ## checking the is_empty method for the last time -> true
    print(stack.is_empty())

Ούρα! ολοκληρώσαμε την υλοποίηση της στοίβας από την αρχή χρησιμοποιώντας τον τύπο δεδομένων λίστας. Θα δείτε την έξοδο όπως αναφέρεται παρακάτω εάν εκτελέσετε τον παραπάνω κώδικα.

True
False
5
4
True

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

Μπορείτε επίσης να δείτε αυτά τα σχετικά άρθρα της λίστας.

Ας δούμε το ενσωματωμένο deque από την ενσωματωμένη μονάδα συλλογών που μπορεί να λειτουργήσει ως στοίβα.

#2. ντεκ από συλλογές

Υλοποιείται ως διπλή ουρά. Δεδομένου ότι υποστηρίζει την προσθήκη και αφαίρεση στοιχείων και από τα δύο άκρα. Ως εκ τούτου, μπορούμε να το χρησιμοποιήσουμε ως στοίβα. Μπορούμε να το κάνουμε να ακολουθεί την αρχή LIFO της στοίβας.

Υλοποιείται χρησιμοποιώντας άλλες δομές δεδομένων που ονομάζονται λίστα διπλής σύνδεσης. Έτσι η απόδοση της εισαγωγής και διαγραφής στοιχείων είναι συνεπής. Η πρόσβαση σε στοιχεία από τη μεσαία συνδεδεμένη λίστα χρειάστηκε O(n) χρόνο. Μπορούμε να το χρησιμοποιήσουμε ως στοίβα καθώς δεν υπάρχει ανάγκη πρόσβασης στα μεσαία στοιχεία από τη στοίβα.

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

• append(data) – χρησιμοποιείται για την προώθηση των δεδομένων στη στοίβα
• pop() – χρησιμοποιείται για την αφαίρεση του ανώτατου στοιχείου από τη στοίβα

Δεν υπάρχουν εναλλακτικές μέθοδοι για peek και is_empty. Μπορούμε να εκτυπώσουμε ολόκληρη τη στοίβα στη θέση της μεθόδου peek. Στη συνέχεια, μπορούμε να χρησιμοποιήσουμε τη μέθοδο len για να ελέγξουμε αν η στοίβα είναι άδεια ή όχι.

Ας υλοποιήσουμε τη στοίβα χρησιμοποιώντας deque από τη λειτουργική μονάδα συλλογών.

from collections import deque

## creating deque object
stack = deque()

## checking whether stack is empty or not -> true
print(len(stack) == 0)

## pushing the elements
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## again checking whether stack is empty or not -> false
print(len(stack) == 0)

## printing the stack
print(stack)

## popping the topmost element -> 5
stack.pop()

## printing the stack
print(stack)

## popping all the elements
stack.pop()
stack.pop() 
stack.pop() 
stack.pop() 

## checking the whether stack is empty or not for the last time -> true
print(len(stack) == 0)

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

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

Μέχρι τώρα, έχουμε δει δύο τρόπους υλοποίησης της στοίβας. Υπάρχουν άλλοι τρόποι υλοποίησης μιας στοίβας; Ναι! Ας δούμε τον τελικό τρόπο υλοποίησης μιας στοίβας σε αυτό το σεμινάριο.

#3. LifoQueue

Το ίδιο το όνομα LifoQueue λέει ότι ακολουθεί την αρχή LIFO. Ως εκ τούτου, μπορούμε να το χρησιμοποιήσουμε ως στοίβα χωρίς καμία αμφιβολία. Είναι από την ενσωματωμένη ουρά λειτουργιών. Το LifoQueue παρέχει μερικές εύχρηστες μεθόδους που είναι χρήσιμες στην υλοποίηση της στοίβας. Ας τους δούμε

• put(data) – προσθέτει ή ωθεί τα δεδομένα στην ουρά
• get() – αφαιρεί ή βγάζει το ανώτατο στοιχείο από την ουρά
• vala() – επιστρέφει αν η στοίβα είναι άδεια ή όχι
• qsize() – επιστρέφει το μήκος της ουράς

Ας υλοποιήσουμε τη στοίβα χρησιμοποιώντας το LifoQueue από τη μονάδα ουράς.

from queue import LifoQueue

## creating LifoQueue object
stack = LifoQueue()

## checking whether stack is empty or not -> true
print(stack.empty())

## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## again checking whether stack is empty or not -> false
print(stack.empty())

## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())

## checking the stack size
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## checking the whether stack is empty or not for the last time -> true
print(stack.empty())

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

True
False
5
4
3
Size 2
2
1
True

Εφαρμογή Stack

Τώρα, έχετε επαρκείς γνώσεις σχετικά με τις στοίβες για να τις εφαρμόσετε σε προβλήματα προγραμματισμού. Ας δούμε ένα πρόβλημα και ας το λύσουμε χρησιμοποιώντας μια στοίβα.

Δίνεται μια έκφραση, γράψτε ένα πρόγραμμα για να ελέγξετε εάν οι παρενθέσεις, οι αγκύλες, οι αγκύλες είναι σωστά ισορροπημένες ή όχι.

Ας δούμε μερικά παραδείγματα.

Εισαγωγή: “[{}]([])”

Έξοδος: Ισορροπημένο

Εισαγωγή: «{[}]([])”

Έξοδος: Μη Ισορροπημένο

Μπορούμε να χρησιμοποιήσουμε τη στοίβα για να λύσουμε το παραπάνω πρόβλημα. Ας δούμε τα βήματα για την επίλυση του προβλήματος.

• Δημιουργήστε μια στοίβα για να αποθηκεύσετε τους χαρακτήρες.
• Εάν το μήκος της έκφρασης είναι περιττό, τότε η έκφραση δεν είναι ισορροπημένη
• Επαναλάβετε μέσα από τη δεδομένη έκφραση.
  • Εάν ο τρέχων χαρακτήρας είναι η αρχική αγκύλη από ( ή { ή [, then push it to stack.
  • Else if the current character is a closing bracket ) or } or ]μετά βγείτε από τη στοίβα.
  • Εάν ο αναδυόμενος χαρακτήρας ταιριάζει με την αρχική αγκύλη, συνεχίστε αλλιώς οι αγκύλες δεν είναι ισορροπημένες.
• Μετά την επανάληψη, εάν η στοίβα είναι άδεια, τότε η εξίσωση είναι Balanced διαφορετικά η εξίσωση είναι Not Balanced.

Μπορούμε να χρησιμοποιήσουμε τον τύπο δεδομένων συνόλου για έλεγχο αντιστοίχισης παρενθέσεων.

## stack
class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
        
    def pop(self): 
        return self.elements.pop() 
    
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False
    
    ## for checking
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## stack initialization
    stack = Stack()
    
    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not        
        if bracket in opening_brackets:
            ## adding to the stack 
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()
        
            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")
    
    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

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

συμπέρασμα

Ναι! Ολοκληρώσατε το σεμινάριο. Ελπίζω να απολαύσατε το σεμινάριο όσο και εγώ κατά τη δημιουργία του. Αυτό είναι για το φροντιστήριο.

Καλή κωδικοποίηση 🙂 👨‍💻