Struktury danych/Stosy

Z Wikibooks, biblioteki wolnych podręczników.
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[edytuj]

Zastosowanie[edytuj]

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[edytuj]

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[edytuj]

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[edytuj]

Ćwiczenia[edytuj]

Podstawowe[edytuj]

Ć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[edytuj]

Ć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.