Struktury danych to zbiór wartości danych, relacji między nimi oraz funkcji lub operacji, które można zastosować do danych. Obecnie dostępnych jest wiele struktur danych. Ale dzisiaj skupimy się na strukturach danych stosu. Będę omawiać następujące tematy:
- Dlaczego struktury danych?
- Rodzaje struktur danych
- Co to jest struktura danych stosu?
- Tworzenie struktury danych stosu
- Wepchnij elementy do stosu
- Pop Elements ze stosu
- Zastosowania struktury danych stosu
Dlaczego struktury danych?
Aby odpowiedzieć na to pytanie, musisz pomyśleć na dużym poziomie. Pomyśl, jak mapy Google pokazują Ci najlepszą trasę w zaledwie ułamek sekund, jak zwracają wynik wyszukiwania w mikrosekundach. Nie zajmuje się tylko 100 witrynami, obsługuje ponad miliard witryn i nadal pokazuje tak szybko wyniki.
Cóż, chociaż zastosowany algorytm odgrywa kluczową rolę, struktura danych lub używany kontener jest podstawą tego algorytmu. W każdej aplikacji organizowanie i przechowywanie danych w sposób lub w strukturze najlepiej dostosowanej do ich wykorzystania jest kluczem do skutecznego dostępu do danych i ich przetwarzania.
jak zrobić moc w java
Rodzaje struktur danych
Istnieją pewne standardowe struktury danych, których można użyć do wydajnej pracy z danymi. Możemy nawet dostosować je lub zbudować zupełnie nowe, aby pasowały do naszej aplikacji.
Co to jest struktura danych stosu?
Rozważ kilka przykładów z życia:
- Przesyłka cargo
- Talerze na tacy
- Stos monet
- Stos szuflad
- Manewrowanie pociągami na stacji kolejowej
Wszystkie te przykłady są zgodne z Last-In-First-Out strategia. Rozważ talerze na tacy. Kiedy chcesz wybrać talerz, musisz podnieść talerz od góry, podczas gdy gdy talerze były trzymane na tacy, muszą być w odwrotnej kolejności. Powyższe przykłady, które następują po Last-In-First-Out (LIFO) zasady są znane jako Stos .
Oprócz operacji uzupełniających mogę powiedzieć, że główne operacje możliwe na stosie to:
- Wepchnij lub włóż element na górę stosu
- Zdejmij lub zdejmij element ze szczytu stosu
Tworzenie struktury danych stosu
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- największy rozmiar to maksymalna liczba elementów oczekiwanych w stosie.
- Elementy stosu są przechowywane na liście Pythona.
- Top wskazuje najwyższy indeks stosu, który jest początkowo przyjmowany jako -1, aby oznaczyć pusty stos.
Początkowy stan stosu można zobaczyć na rysunku, gdzie max_size = 5
Wepchnij element do stosu
Teraz, jeśli chcesz wprowadzić lub wepchnąć element na stos, musisz o tym pamiętać
- Góra wskaże indeks, do którego zostanie wstawiony element.
- I żaden element nie zostanie wstawiony, gdy stos jest pełny, tj. Gdy max_size = top.
Więc jaki powinien być algorytm?
# zwraca maksymalny rozmiar stosu def get_max_size (self): return self .__ max_size # zwraca wartość bool niezależnie od tego, czy stos jest pełny, czy nie, True jeśli pełny i False w przeciwnym razie def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element na szczycie stosu def push (self, data): if (self.is_full ()): print ('stos jest już pełny') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Możesz użyć poniższej __str __ (), aby wydrukować elementy obiektu DS podczas debugowania def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elementów [indeks])) index- = 1 msg = '' .join (msg) msg = 'Stack data (Top to Bottom):' + msg return msgTeraz, kiedy wykonasz następujące czynności:
stack1 = Stos (4)
# Wepchnij wszystkie wymagane elementy.
stack1.push („A”)
stack1.push („B”)
stack1.push („C”)
stack1.push („E”)
print (stack1.is_full ())
drukuj (stos1)
Wynik:
stos jest już pełny
Prawdziwe
Dane stosu (od góry do dołu): D C B A
Pop Elements ze stosu
Teraz, po wstawieniu elementów do stosu, chcesz je wyskoczyć, więc musisz zadbać o następujące kwestie:
- Stos nie jest pusty, tj. Góra! = -1
- Kiedy usuwasz dane, góra musi wskazywać na poprzednią górę stosu.
Więc jaki będzie algorytm?
#returns wartość bool niezależnie od tego, czy stos jest pusty czy nie, True jeśli pusty i False w przeciwnym razie def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('nic do pop, już puste') else: a = self .__ elementy [self .__ top] self .__ top = self .__ top-1 return a #display wszystkie elementy stosu od góry do dołu def display (self): for i in range (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Teraz, biorąc pod uwagę wcześniej utworzony stos, spróbuj wyskoczyć elementy
print (stack1.pop ())
print (stack1.pop ())
drukuj (stos1)
stosuje się klauzulę unii
print (stack1.pop ())
print (stack1.pop ())
print (stack1.pop ())
Wynik:
re
do
co to jest scipy w Pythonie
Dane stosu (od góry do dołu): B A
b
DO
nic do wyskoczenia, już puste
Zastosowania struktury danych stosu
- Przykład 1:
Stos jest używany do implementacji algorytmu dopasowywania nawiasów do oceny wyrażeń arytmetycznych, a także do implementacji wywołań metod.
Odpowiedź brzmi: 5.
- Przykład 2:
Schowek w systemie Windows używa dwóch stosów do implementacji operacji cofnij-ponów (ctrl + z, ctrl + y). Pracowałbyś z edytorami tekstu Windows, takimi jak MS-Word, Notatnik itp. Oto tekst napisany w MS-Word. Obserwuj, jak zmienił się tekst po kliknięciu Ctrl-Z i Ctrl-Y.
Oto kod, który symuluje operację cofania i ponawiania. Przejrzyj kod i obserwuj, jak stos jest używany w tej implementacji.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('Stos jest pełny !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Stos jest pusty! ! ') else: data = self .__ elementy [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' Stos jest pusty ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Możesz użyć poniższej __str __ (), aby wydrukować elementy Obiekt DS podczas debugowania def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Dane stosu (od góry do dołu): '+ msg return ms g #function do zaimplementowania operacji remove lub backspace def remove (): global clipboard, undo_stack data = clipboard [len (schowek) -1] clipboard.remove (dane) undo_stack.push (dane) print ('Usuń:', schowek) # function do zaimplementowania operacji cofania def undo (): globalny schowek, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Brak danych do cofnięcia') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Cofnij:', schowek) # function do zaimplementowania operacji redo def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Brak danych to redo ') else: data = redo_stack.pop () if (danych nie ma w schowku): print (' Brak danych do ponownego wykonania ') redo_stack.push (dane) else: clipboard.remove (dane) undo_stack.push ( data) print ('Ponów:', schowek) schowek = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stos (len (schowek)) redo_stack = Stos (len (schowek)) usuń () cofnij () ponów ()Wynik:
Usuń: [„A”, „B”, „C”, „D”, „E”]
Cofnij: [„A”, „B”, „C”, „D”, „E”, „F”]
Ponów: [„A”, „B”, „C”, „D”, „E”]
Na tym kończymy artykuł dotyczący struktury danych stosu w języku Python. Jeśli pomyślnie zrozumiałeś i uruchomiłeś kody samodzielnie, nie jesteś już nowicjuszem w strukturze danych stosów.
Masz do nas pytanie? Wspomnij o tym w sekcji komentarzy w tym artykule, a my skontaktujemy się z Tobą tak szybko, jak to możliwe.
Aby uzyskać dogłębną wiedzę na temat języka Python i jego różnych aplikacji, możesz zarejestrować się na żywo z całodobowym wsparciem i dożywotnim dostępem.