Stosy i kolejki

Przegląd

Stosy i kolejki to popularne struktury danych w informatyce, które określają kolejność, w jakiej można dodawać i usuwać elementy. Za ich pomocą można kontrolować kolejność interakcji z danymi:

• Stos: kontener, do którego się wstawia i z którego usuwa się elementy według zasady FILO (first-in, last-out), np. wybór książki ze szczytu stosu książek do przeczytania.

• Kolejka: kontener, do którego się wstawia i z którego usuwa się elementy według zasady FIFO (first-in, first-out), np. obsługa kolejki klientów czekających na posiłek.

Mimo że podstawowy kod stosów i kolejek jest podobny, to każdy z tych elementów ma kluczowe cechy wyróżniające i mocne strony, które można wykorzystać, aby przyspieszyć działanie, zwiększyć wydajność i intuicyjność swojej gry.

Stosy

Stos można wyobrazić sobie jako stos naleśników. Przypuśćmy, że jesteś w restauracji na śniadaniu, a kelner podaje ci niekończący się stos naleśników. Aby zachować należytą uprzejmość, bierzesz tylko jednego naleśnika na raz i tylko z wierzchu stosu. Możesz poprosić kelnera, aby położył nowego naleśnika na górę stosu, a kiedy zgłodniejesz, możesz wypchnąć naleśnika z góry stosu na talerz, aby go zjeść. Jeśli chcesz zjeść konkretnego naleśnika ze środka stosu, musisz jeść kolejne naleśniki od góry, aż dotrzesz do tego, którego szukasz. Pierwszy dołożony naleśnik będzie ostatnim zabranym. To sprawia, że stos jest strukturą danych typu FILO, czyli first-in, last-out.

Kiedy stosować?

Stosy są przydatne, gdy konieczne jest cofnięcie się lub zapamiętanie kolejności wykonywanych czynności. Może to być funkcja cofania, łańcuch zdarzeń lub seria wyborów. Przykładowo, może masz robota, który musi pokonać labirynt z rozgałęziającymi się ścieżkami. Gdy robot natrafi na rozwidlenie w labiryncie, wybiera ścieżkę i umieszcza ten wybór na stosie. Gdy trafi na ślepy zaułek, cofa się przez stos, odrzucając wybory, aż znajdzie nową ścieżkę, którą może podążać.

Implementacja w Verse

Interfejs API Verse nie ma wbudowanej implementacji stosów, jednak można ją samodzielnie utworzyć.

Elementy stosu można reprezentować za pomocą dowolnej uporządkowanej struktury danych, takiej jak tablica lub lista powiązana. W tym przykładzie użyjesz tablicy, ponieważ zapewnia ona łatwy dostęp do szczytu stosu.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Tablica Elements przechowuje w stosie obiekty, które są typu t. Oznacza to, że możesz inicjować stos dowolnym typem elementu, np. int, float, stack itd. Użycie type jako argumentu do klasy stosu jest przykładem [typu parametrycznego](parametric-types-in-verse).

Zdefiniujmy najpierw kilka funkcji pomocniczych. Musisz wiedzieć, gdzie znajduje się wierzchołek stosu, aby można było układać na nim elementy (Push()) i wyciągać je z niego (Pop()). W tym celu potrzebne są trzy funkcje, Size(), IsEmpty() oraz Peek().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

Funkcja Size() po prostu zwraca wartość Length tablicy Elements. Funkcja IsEmpty() wywołuje funkcję Size() i ma specyfikator <transacts>, co oznacza, że zakończy się niepowodzeniem, jeśli Size() nie jest równe 0.

Funkcja Peek() zwraca element ze szczytu indeksu (Length - 1) tablicy elementów. Funkcja ta ma specyfikatory <decides><transacts>, ponieważ dostęp do tablicy może zakończyć się niepowodzeniem, jeśli tablica jest pusta.

Aby utworzyć instancję stosu, można użyć funkcji konstruktora. Konstruktor to specjalna funkcja, która tworzy instancję klasy, z którą jest związana. Konstruktor ustawia wartości początkowe dla obiektu i umożliwia dostęp do wartości Elements i przypisanie jej do początkowej tablicy elementów.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Wypychanie i wyciąganie

Aby dodawać elementy do stosu i usuwać je z niego, należy albo wypchnąć (push) nowy element na szczyt stosu, albo wyciągnąć (pop) go z wierzchołka.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

Funkcja Push() pobiera element, który chcesz umieścić na wierzchu stosu i zwraca nowy stos z elementem na wierzchu. Zwracanie nowego stosu zamiast modyfikowania bieżącego stosu jest przykładem programowania funkcjonalnego i zmniejsza ryzyko efektów ubocznych.

Aby zaimplementować funkcję Pop(), musisz najpierw znaleźć element na szczycie stosu, używając Peek(). Następnie musisz usunąć element na wierzchu (używając funkcji RemoveElement[]), a także zwrócić nowy stos bez elementu. Możesz użyć krotki, aby zwrócić jednocześnie nowy stos i usunięty element. Ze względu na wyrażenia zawodne dla dostępu do tablicy i wywołania Peek(), Pop() musi mieć specyfikatory <decides><transacts>.

Complete Code

Poniżej zaprezentowano kompletny kod klasy stosu.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

Kolejki

Kolejkę można sobie wyobrazić jako przenośnik taśmowy sushi. Przypuśćmy, że jesteś w restauracji sushi, która dostarcza ci talerze z sushi pojedynczo za pomocą przenośnika taśmowego, a talerze docierają do ciebie w kolejności, w jakiej zostały zamówione. Możesz wziąć talerz z początku kolejki, aby go odebrać i zjeść, ale możesz odebrać tylko jeden talerz na raz. Kiedy chcesz zamówić nowy talerz, prosisz szefa kuchni o przesunięcie talerza na koniec kolejki. Jeśli w kolejce znajdują się już inne talerze z sushi, musisz pobierać talerze z przodu kolejki, aż dotrzesz do talerza z tyłu. Pierwszy dołożony talerz z sushi będzie pierwszym zabranym. Taka kolejka jest strukturą danych typu FIFO, czyli first-in, first-out.

Kiedy stosować?

Kolejki przydają się, gdy trzeba przetwarzać dane w oparciu o czas ich nadejścia. Może to być obsługa klientów w punkcie drive-thru, kolejkowanie połączeń w call center lub zadawanie graczowi kolejki pytań podczas wywiadu. Jeśli na przykład chcesz utworzyć poczekalnię dla graczy, którzy wykonują zadanie lub przechodzą przez przygodę pojedynczo, możesz użyć kolejki, aby uporządkować graczy według kolejności przybycia.

Implementacja w Verse

Interfejs API Verse nie ma wbudowanej implementacji kolejek, jednak można ją samodzielnie utworzyć.

Podobnie jak stosy, elementy kolejki można reprezentować za pomocą dowolnej uporządkowanej struktury danych, takiej jak tablica lub lista powiązana. W tym przykładzie użyjesz tablicy, ponieważ zapewnia ona łatwy dostęp zarówno do początku, jak i końca kolejki. Aby zapoznać się z implementacją kolejki przy użyciu listy powiązanej, sprawdź ten fragment kodu.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Tablica Elements przechowuje w kolejce obiekty typu t. Oznacza to, że możesz inicjować kolejkę dowolnym typem elementu, np. int, float, queue itd. Użycie type jako argumentu do klasy stosu jest przykładem [typu parametrycznego](parametric-types-in-verse).

Podobnie jak w przypadku stosów, kolejki potrzebują kilku funkcji pomocniczych. Musisz wiedzieć, gdzie znajduje się przód i tył kolejki, aby można było wykonać funkcje Enqueue() i Dequeue(). Warto również znać rozmiar kolejki i wiedzieć, czy jest ona pusta. Zdefiniujesz to w czterech funkcjach: Size(), IsEmpty(), Front() i Back().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

Funkcja Size() zwraca wartość Length tablicy Elements. Funkcja IsEmpty() wywołuje funkcję Size() i ma specyfikator <transacts>, co oznacza, że zakończy się niepowodzeniem, jeśli Size() nie jest równe 0.

Funkcje Front() i Rear() zwracają element z przodu (indeks 0) i z tyłu indeksu (Length - 1) tablicy elementów. Obie te funkcje mają specyfikatory <decides><transacts>, ponieważ dostęp do tablicy może zakończyć się niepowodzeniem, jeśli tablica jest pusta.

Podobnie jak stack, klasa queue również musi używać funkcji konstruktora, aby przypisać tablicę Elements. Funkcja konstruktora umożliwia dostęp do wartości Elements i przypisanie jej do początkowej tablicy elementów.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Kolejkowanie i usuwanie z kolejki

Aby dodawać elementy do kolejki i usuwać je z niej, należy albo ustawić nowy element z tyłu kolejki, albo usunąć element z przodu kolejki.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

Funkcja Enqueue() pobiera element, który ma zostać wstawiony do kolejki, i zwraca nową kolejkę z nowym elementem z tyłu. Zwracanie nowej kolejki zamiast modyfikowania bieżącej kolejki jest przykładem programowania funkcjonalnego i zmniejsza ryzyko efektów ubocznych.

W przypadku funkcji Dequeue() należy usunąć i zwrócić element znajdujący się na początku kolejki, a także zwrócić nową kolejkę z usuniętym pierwszym elementem (używając funkcji RemoveElement[]). Ze względu na wyrażenia zawodne dla dostępu do tablicy i wywołania Front(), Dequeue() musi mieć specyfikatory <decides><transacts>.

Complete Code

Kompletny kod klasy kolejki znajduje się poniżej.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

Praca własna

Jest wiele sposobów na iterację i ulepszanie stosów i kolejek, dlatego warto zapoznać się z różnymi sposobami dodawania funkcjonalności. Oto kilka pomysłów na dobry początek:

• Czy potrafisz przekształcić kolejkę w kolejkę okrężną, w której ostatni element jest połączony z pierwszym elementem, a kolejka ciągle się zapętla?

• A co z kolejką z pierwszeństwem, w której obiekty są uporządkowane zarówno na podstawie czasu wejścia do kolejki, jak i innej wartości?

• Czy potrafisz stworzyć gry wykorzystujące stos, takie jak Wieże Hanoi? A co z grą restauracyjną, w której klienci muszą czekać w kolejce?