wprowadzenie
struktury danych porządkują pamięć masową w komputerach, abyśmy mogli sprawnie uzyskiwać dostęp do danych i je zmieniać. Stosy i kolejki to jedne z najwcześniejszych struktur danych zdefiniowanych w informatyce.
proste do nauczenia się i łatwe do wdrożenia, ich zastosowania są powszechne i najprawdopodobniej znajdziesz je w swoim oprogramowaniu do różnych zadań.
często stosy i kolejki są implementowane z tablicą lub połączoną listą. Będziemy polegać na strukturze danychList, aby pomieścić zarówno stosy, jak i kolejki.
Jak działają?
stosuj
stosy, jak sama nazwa wskazuje, postępuj zgodnie z zasadą Last-in-First-Out (LIFO). Tak jak układanie monet jeden na drugim, ostatnią monetą, którą umieścimy na górze, jest ta, która jest pierwszą, która zostanie później usunięta ze stosu.
aby zaimplementować stos, potrzebujemy więc dwóch prostych operacji:
-
push– dodaje element do góry stosu:
-
pop– usuwa element u góry stosu:
Kolejka
kolejki, jak sama nazwa wskazuje, postępują zgodnie z zasadą first-in-first-out (FIFO). Jakby czekając w kolejce po bilety do kina, pierwszy, który stanie w kolejce, to pierwszy, który kupi bilet i cieszy się filmem.
aby zaimplementować kolejkę, potrzebujemy więc dwóch prostych operacji:
-
enqueue– dodaje element na koniec kolejki:
-
dequeue– usuwa element na początku kolejki:
stosy i kolejki za pomocą list
wbudowana w PythonaList struktura danych jest dostarczana w pakiecie z metodami do symulacji operacji stosu i kolejki.
rozważmy stos liter:
możemy użyć tych samych funkcji do implementacji kolejki. Funkcjapop opcjonalnie pobiera indeks elementu, który chcemy pobrać jako argument.
możemy więc użyćpop z pierwszym indeksem listy tj.0, aby uzyskać zachowanie podobne do kolejki.
rozważmy „kolejkę” owoców:
ponownie, tutaj używamyappend Ipop operacji listy, aby symulować podstawowe operacje kolejki.
stosy i kolejki z biblioteką Deque
Python madeque (wymawiane 'deck’) bibliotekę, która zapewnia sekwencję z wydajnymi metodami pracy jako stos lub Kolejka.
deque jest skrótem od Double Ended Queue – uogólnionej kolejki, która może pobrać pierwszy lub ostatni zapisany element:
Jeśli chcesz dowiedzieć się więcej o bibliotecedeque I innych typach kolekcji udostępnianych przez Pythona, możesz przeczytać nasz artykuł Wprowadzenie do modułu Kolekcje Pythona.
bardziej rygorystyczne implementacje w Pythonie
Jeśli Twój kod potrzebuje stosu i podaszList, nic nie powstrzyma programisty przed wywołanieminsertremove lub innych funkcji listy, które wpłyną na kolejność stosu! To zasadniczo rujnuje sens definiowania stosu, ponieważ nie działa on już tak, jak powinien.
są chwile, kiedy chcemy się upewnić, że tylko prawidłowe operacje mogą być wykonywane na naszych danych.
możemy tworzyć klasy, które eksponują Tylko niezbędne metody dla każdej struktury danych.
aby to zrobić, stwórzmy nowy plik o nazwie stack_queue.py I zdefiniujmy dwie klasy:
Programiści korzystający z naszego StackI Queue są teraz zachęcani do używania dostarczonych metod do manipulowania danymi.
przykłady
wyobraź sobie, że jesteś programistą pracującym nad zupełnie nowym edytorem tekstu. Masz za zadanie utworzyć funkcję cofania-pozwalającą użytkownikom śledzić ich działania do początku sesji.
stos idealnie pasuje do tego scenariusza. Możemy nagrać każdą akcję, którą użytkownik podejmie, naciskając ją na stos. Gdy użytkownik chce cofnąć akcję, usuwa ją ze stosu. Możemy szybko zasymulować tę funkcję w następujący sposób:
kolejki mają również szerokie zastosowanie w programowaniu. Pomyśl o grach takich jak Street Fighter lub Super Smash Brothers. Gracze w tych grach mogą wykonywać specjalne ruchy, naciskając kombinację przycisków. Te kombinacje przycisków mogą być przechowywane w kolejce.
teraz wyobraź sobie, że jesteś programistą pracującym nad nową grą walki. W grze za każdym razem, gdy naciśnięty jest przycisk, uruchamiane jest Zdarzenie wejściowe. Tester zauważył, że jeśli przyciski zostaną naciśnięte zbyt szybko, gra przetworzy tylko pierwszy i specjalne ruchy nie będą działać!
możesz to naprawić kolejką. Możemy sprawdzić wszystkie zdarzenia wejściowe, gdy wejdą. W ten sposób nie ma znaczenia, czy zdarzenia wejściowe pochodzą z małą ilością czasu między nimi, wszystkie będą przechowywane i dostępne do przetwarzania. Kiedy przetwarzamy ruchy, możemy je usunąć. Specjalny ruch można opracować w następujący sposób:
wniosek
stosy i kolejki są prostymi strukturami danych, które pozwalają nam przechowywać i pobierać dane sekwencyjnie. W stosie ostatni element, który wprowadzimy, jest pierwszym, który wyjdzie. W kolejce, pierwszy element, który Wprowadzamy jest pierwszym wyjściem.
możemy dodawać elementy do stosu za pomocą operacjipush I pobierać elementy za pomocą operacjipop. W kolejkach dodajemy elementy za pomocą operacjienqueue I pobieramy elementy za pomocą operacjidequeue.
w Pythonie możemy zaimplementować stosy i kolejki za pomocą wbudowanej struktury danych List. Python posiada również bibliotekędeque, która może efektywnie dostarczać operacje stosu i kolejki w jednym obiekcie. Wreszcie, stworzyliśmy nasze klasy stosu i kolejki, aby ściślej kontrolować nasze dane.
istnieje wiele rzeczywistych przypadków użycia stosów i kolejek, zrozumienie ich pozwala nam rozwiązać wiele problemów z przechowywaniem danych w łatwy i skuteczny sposób.