Struktury danych/Stosy

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Stos

Zastosowanie

Stos jest dobrym rozwiązaniem, gdy gromadząc jakieś dane przeprowadzamy operacje najpierw na tych najnowszych (ostatnio dodanych), a gdy te nie są nam już potrzebne, to zabieramy się za te nieco starsze.

Dobrym przykładem jest tu stos talerzy, ułożonych jeden na drugim, które - załóżmy - przypadło nam zmywać. W pierwszej kolejności zabierzemy się za talerz na samej górze. Gdy już go wyczyścimy to odłożymy na bok i weźmiemy następny - tak do ostatniego który jest na samym dnie stosu.

Opis

Zważywszy na kolejność dodawania i usuwania elementów ze stosu, struktura ta określana jest jako LIFO (ang. Last In First Out - Ostatni na wejściu, Pierwszy na wyjściu).

Schemat
(element 1 dodany został jako pierwszy, następnie dodano 2, 3 .. n

Stos

• PUSH(d:Data) - wrzuca nowy element d na szczyt stosu
• POP() - zdejmuje element ze szczytu stosu zwracając jego wartość

Implementacja

Do implementacji stosu o stałym rozmiarze n wystarczy n-elementowa tablica i jedna zmienna, która będzie przetrzymywać aktualną liczbę elementów.

Dodatkowe informacje

• Przykładowe implementacje stosu w różnych językach programowania

Ćwiczenia

Podstawowe

Ćwiczenie 1: Zaimplementuj stos korzystając z :

• Struktur wskaźnikowych
• Tablicy

Ćwiczenie 2: Korzystając ze stosu napisz program, który w wyniku będzie zwracać odwrócone słowa podawane na standardowe wejście. Zastanów się nad złożonością pamięciową tego rozwiązania, w zestawieniu z rozwiązaniem "naiwnym" korzystającym z dodatkowej tablicy na nowy łańcuch znakowy.

Zaawansowane

Ćwiczenie 1: Napisz program, który korzystając ze stosu będzie zamieniał zwykłe wyrażenia matematyczne zapisane infiksowo (np. 3+4*5^(2+3)) na zapis w Odwrotnej Notacji Polskiej, przy czym za operatory przyjmujemy: zmiana znaku na przeciwny ~, dodawanie +, odejmowanie -, mnożenie *, dzielenie /, podnoszenie do potęgi ^.

Ćwiczenie 2: Rozszerz powyższy program o inne funkcje matematyczne : log, funkcje trygonometryczne, pierwiastkowanie. Napisz program, który z ONP będzie przechodził z powrotem na "zwykłą notację" infiksową. Dodatkowo Dodaj możliwość ewaluowania tych funkcji.

Ćwiczenie 3: Napisz program, który będzie implementować 2 stosy za pomocą jednej struktury.

Podpowiedzi
Zaaw.Ćw 3 : Możesz skorzystać z deque