Wprowadzenie

Struktury danych organizują przechowywanie danych w komputerach tak, abyśmy mieli do nich efektywny dostęp i mogli je zmieniać. Stosy i kolejki są jednymi z najwcześniejszych struktur danych zdefiniowanych w informatyce.

Łatwe do nauczenia się i łatwe do wdrożenia, ich zastosowania są powszechne i najprawdopodobniej znajdziesz je w swoim oprogramowaniu do różnych zadań.

Powszechnie stosy i kolejki są implementowane za pomocą tablicy lub listy połączonej. Będziemy polegać na strukturze danych List, aby pomieścić zarówno stosy, jak i kolejki.

Jak one działają?

Stos

Stosy, jak sama nazwa wskazuje, przestrzegają zasady Last-in-First-Out (LIFO). Tak jak w przypadku układania monet jedna na drugiej, ostatnia moneta, którą kładziemy na wierzchu jest tą, która jako pierwsza zostanie później usunięta ze stosu.

Do implementacji stosu potrzebujemy zatem dwóch prostych operacji:

• push – dodaje element na wierzchołek stosu:

• pop – usuwa element znajdujący się na szczycie stosu:

Queue

Kolejki, jak sama nazwa wskazuje, działają zgodnie z zasadą First-in-First-Out (FIFO). Tak jak w przypadku czekania w kolejce po bilety do kina, ten kto pierwszy stanie w kolejce, ten pierwszy kupi bilet i będzie mógł cieszyć się filmem.

Do implementacji kolejki potrzebujemy zatem dwóch prostych operacji:

• enqueue – dodaje element na koniec kolejki:

• dequeue – usuwa element znajdujący się na początku kolejki:

Stosy i kolejki przy użyciu list

Wbudowana Liststruktura danych Pythona jest wyposażona w metody symulujące zarówno operacje na stosach, jak i kolejkach.

Rozważmy stos listów:

Możemy użyć tych samych funkcji do zaimplementowania kolejki. Funkcja pop 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żywamy operacji append i pop listy, aby zasymulować podstawowe operacje kolejki.

Stacks and Queues with the Deque Library

Python ma bibliotekę deque (wymawianą jako „deck”), która zapewnia sekwencję z wydajnymi metodami do pracy jako stos lub kolejka.

deque to skrót od Double Ended Queue – uogólniona kolejka, która może uzyskać pierwszy lub ostatni element, który jest przechowywany:

Jeśli chcesz dowiedzieć się więcej o bibliotece deque i innych typach kolekcji udostępnianych przez Pythona, możesz przeczytać nasz artykuł Wprowadzenie do modułu kolekcji Pythona.

Wdrożenia stricterów w Pythonie

Jeśli Twój kod potrzebuje stosu i udostępniasz List, nic nie powstrzymuje programisty przed wywołaniem insert, remove lub innych funkcji listy, które wpłyną na kolejność Twojego stosu! To zasadniczo rujnuje sens definiowania stosu, ponieważ nie działa on już tak, jak powinien.

Są chwile, kiedy chcielibyśmy zapewnić, ż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ć, utwórzmy nowy plik o nazwie stack_queue.py i zdefiniujmy dwie klasy:

Programiści korzystający z naszych Stack i Queue są teraz zachęcani do korzystania z dostarczonych metod, aby zamiast tego manipulować danymi.

Przykłady

Wyobraź sobie, że jesteś programistą pracującym nad zupełnie nowym edytorem tekstu. Twoim zadaniem jest stworzenie funkcji cofania – pozwalającej użytkownikom na cofanie swoich działań do początku sesji.

Stos jest idealnym rozwiązaniem dla tego scenariusza. Możemy rejestrować każdą akcję użytkownika, przesuwając ją na stos. Kiedy użytkownik będzie chciał cofnąć akcję, wyskakuje ona ze stosu. Możemy szybko zasymulować tę funkcję w ten sposób:

Kolejki mają również szerokie zastosowanie w programowaniu. Pomyśl o grach takich jak Street Fighter czy 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.

Wyobraź sobie teraz, że jesteś programistą pracującym nad nową grą walki. W twojej grze za każdym razem, gdy przycisk jest wciśnięty, wywoływane jest zdarzenie wejściowe. Tester zauważył, że jeśli przyciski są wciskane zbyt szybko, gra przetwarza tylko pierwszy z nich i specjalne ruchy nie będą działać!

Możesz to naprawić za pomocą kolejki. Możemy zapisywać wszystkie zdarzenia wejściowe w kolejce, gdy tylko się pojawią. W ten sposób nie będzie miało znaczenia, czy zdarzenia wejściowe przychodzą z niewielką przerwą między nimi, wszystkie będą przechowywane i dostępne do przetworzenia. Kiedy przetwarzamy ruchy, możemy je odrzucić. Specjalny ruch może być opracowany w ten 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 wprowadzamy jest pierwszym, który wychodzi. W kolejce pierwszy element, który wprowadzimy, jest pierwszym, który wyjdzie.

Do stosu możemy dodawać elementy za pomocą operacji push, a pobierać elementy za pomocą operacji pop. W przypadku kolejek dodajemy elementy za pomocą operacji enqueue i pobieramy elementy za pomocą operacji dequeue.

W Pythonie możemy zaimplementować stosy i kolejki po prostu za pomocą wbudowanej struktury danych List. Python posiada również bibliotekę deque, która może efektywnie zapewnić operacje stosu i kolejki w jednym obiekcie. Wreszcie, stworzyliśmy nasze klasy stosu i kolejki dla ściślejszej kontroli naszych danych.

Istnieje wiele przypadków użycia w świecie rzeczywistym dla stosów i kolejek, zrozumienie ich pozwala nam rozwiązać wiele problemów związanych z przechowywaniem danych w łatwy i skuteczny sposób.

.