Przeczytaj
Stos
Koncepcja tej struktury dynamicznej jest bardzo prosta: stos przypomina wieżę budowaną z klocków. Nowe elementy układamy na szczycie.
W przypadku stosu mamy dostęp tylko do elementu ostatnio dodanego (umieszczonego najwyżej). Nie mamy do dyspozycji mechanizmu indeksowania, który pozwala odwołać się do pozostałych elementów. Możemy jedynie sprawdzić wartość znajdującą się na samym szczycie.
Podobnie dzieje się w przypadku usuwania elementów ze stosu. Możemy zdjąć z niego tylko element znajdujący się na szczycie.
![Zasady dodawania i usuwania elementów ze stosu. Na ilustracji znajduje się prostokąt po lewej stronie, od którego wychodzi strzałka do prostokątów poniżej z podpisem dodaj. Po prawej stronie znajduje się prostokąt, do którego idzie strzałka z prostokąta poniżej z podpisem usuń. Poniżej znajdują się cztery puste prostokąty ustawione jeden na drugim.](https://static.zpe.gov.pl/portal/f/res-minimized/Rz8yv1nQfvMZg/1665413467/1nvvo4orKajwwwE7C39kOFr0EpcWSzqR.png)
Bardzo ważną cechą opisanej struktury jest to, że element dodany do niej jako pierwszy, zostanie usunięty jako ostatni. Stos nazywamy strukturą typu LIFO (z ang. Last In First Out, czyli „ostatni na wejściu, pierwszy na wyjściu”).
Implementacja stosu z zastosowaniem tablicy
Stos jest strukturą dynamiczną – jego rozmiar może się zmieniać w trakcie działania programu. Dla ułatwienia zrozumienia stosu zaimplementujemy go na statycznej tablicy. Musimy jedynie zastanowić się, jaki maksymalny rozmiar powinien mieć budowany stos.
Do poprawnego działania stosu potrzebujemy tylko jednej zmiennej, która będzie przechowywała indeks szczytu stosu. Przy dodawaniu nowego elementu zwiększymy wartość zmiennej o jeden, a przy usuwaniu będziemy ją zmniejszać. Pierwszym („najniższym”) elementem stosu będzie pierwszy element przechowywany w tablicy.
![Działanie stosu przy użyciu jednej zmiennej. Na ilustracji znajduje się tablica podpisana jako: zawartość. Tablica ta zawiera liczby: 8, 4, 3, nad czwartym polem widnieje podpis: szczyt stosu. Reszta pól jest pusta. Każde pole posiada swój indeks od 0 do 5, podpisany pod kolejnymi polami stosu.](https://static.zpe.gov.pl/portal/f/res-minimized/RYVejcJGTw53w/1665413467/MooVqpV5RyHQ4WgvNfWUL5zRHCaDhhAM.png)
Przeanalizujmy funkcje odpowiedzialne za dodawanie i usuwanie elementów stosu zapisane za pomocą pseudokodu. Zakładamy, że stos jest reprezentowany przez tablicę stos
o rozmiarze elementów. Indeks wskazujący szczyt jest przechowywany jako zmienna indeks_szczytu
. Tablicę indeksujemy od wartości .
W zaprezentowanym programie bardzo ważne jest, że elementy nie są faktycznie usuwane z tablicy. Wystarczy jedynie zmniejszyć indeks przechowywany w zmiennej indeks_szczytu
, ponieważ przy dodawaniu następnego elementu wartość komórki zostaje nadpisana. Jest to bardzo duże ułatwienie podczas implementowania struktury.
Przykładowe zastosowania stosu
Stos jest wykorzystywany powszechnie w przypadku programów pisanych w językach wysokiego poziomu. Używa się go do przechowywania adresów pamięci i zmiennych, a także jako miejsce do zapisywania zawartości rejestrów procesora.
Implementacja stosu w wybranych językach programowania
Implementację stosu w wybranych językach programowania znajdziesz w następujących e‑materiałach:
Dynamiczne struktury danych w języku C++Dynamiczne struktury danych w języku C++,
Dynamiczne struktury danych w języku JavaDynamiczne struktury danych w języku Java,
Dynamiczne struktury danych w języku PythonDynamiczne struktury danych w języku Python.
Kolejka
Każdy z nas miał do czynienia z kolejkąkolejką w sklepie. Zasada jej działania jest dosyć prosta: osoba, która znajduje się przed nami, pojawiła się wcześniej, a więc zostanie wcześniej obsłużona. Tak samo działa struktura danych zwana kolejką.
Kolejka jest przeciwieństwem stosu, jeśli chodzi o sposób dodawania i usuwania elementów. Nazywamy ją strukturą typu FIFO (z ang. First In First Out, czyli „pierwszy na wejściu, pierwszy na wyjściu”). Nowy element jest dodawany na końcu kolejki. Natomiast jako pierwszy usuwany jest element z początku kolejki.
Kolejka może być wykorzystana np. w teorii grafów w algorytmie przeszukiwania grafu wszerz. Więcej informacji na jej temat znajdziesz w e‑materiale Dynamiczne struktury danychDynamiczne struktury danych.
![Schemat kolejki. Na ilustracja znajdują się prostokąty, od pierwszego wychodzi strzałka dodaj do prostokąta podpisanego jako KONIEC. Dwa kolejne prostokąty są puste. Następny prostokąt podpisany jest jako: POCZĄTEK. Wychodzi od niego strzałka z podpisem usuń skierowana na osobny prostokąt umieszczony pod kolejką.](https://static.zpe.gov.pl/portal/f/res-minimized/RsOWIlobQN3lA/1665413467/2A2EG7YgIDZc29zAKzzx10Ht2tGOVHov.png)
Tak jak w przypadku stosu, nie możemy użyć indeksowania, aby odwołać się do dowolnych elementów składających się na kolejkę. Jesteśmy w stanie tylko odczytać wartości znajdujące się na jej początku.
Implementacja kolejki z zastosowaniem tablicy
Kolejka także jest strukturą dynamiczną, lecz możemy ją zaimplementować, używając statycznej tablicy. Jedynym ograniczeniem jest maksymalna liczba przechowywanych w kolejce elementów.
Aby kolejka działała poprawnie, konieczne jest użycie dwóch zmiennych. Jedna z nich będzie wskazywała początek kolejki, natomiast druga jej koniec.
![Ilustracja przedstawia tablicę podpisaną jako zawartość. Po polu podpisanym jako koniec kolejki znajdują się liczby: 4, 5, 8. W kolejnym polu znajduje się strzałka z podpisem: początek kolejki. Każde z pól posiada swój indeks od 0 do 7 podpisany poniżej tablicy.](https://static.zpe.gov.pl/portal/f/res-minimized/R14sBe9QsU485/1665413467/p8DhCji0alndW0qAjrR16HYCKVLCE9mk.png)
Poniżej znajdują się zapisane za pomocą pseudokodu funkcje wykorzystywane podczas dodawania i usuwania elementów kolejki. Zakładamy, że kolejka jest reprezentowana przez tablicę kolejka
o rozmiarze elementów. Indeksy początku oraz końca kolejki są przechowywane w postaci zmiennych indeks_poczatek
oraz indeks_koniec
. Początkowa wartość indeks_poczatek
wynosi . Zmienną indeks_koniec
inicjalizujemy z kolei wartością o jeden mniejszą, czyli . Tablicę indeksujemy od wartości .
Przedstawiony za pomocą pseudokodu program może wydawać się skomplikowany, ponieważ zawiera dużo instrukcji warunkowych. Odpowiadają one za przesuwanie indeksów wskazujących krańce kolejki z początku na koniec tablicy. Dzięki temu nigdy nie wychodzimy poza zakres tablicy w wyniku modyfikacji indeksów.
Dodatkowo indeks_poczatek
zawsze wskazuje indeks komórki tablicy za pierwszym elementem. Jest to pewne ułatwienie, które pomaga stwierdzić, kiedy kolejka jest pełna, a kiedy pusta. Jego wadą jest to, że kolejka może przechowywać nie , lecz elementów. Aby dokładniej zrozumieć, dlaczego tak się dzieje, pomocne mogą okazać się aplety dostępne w sekcji „Aplet”, których zadaniem jest wizualizowanie działania kolejki.
Istnieje również wariant kolejki nazywany kolejką priorytetową. Charakteryzuje się ona tym, że elementy znajdujące się w kolejce są zawsze posortowane. W rezultacie na początku kolejki zawsze znajduje się najmniejszy bądź największy element.
Implementacja kolejki w wybranych językach programowania
Implementację kolejki w wybranych językach programowania znajdziesz w następujących e‑materiałach:
Dynamiczne struktury danych w języku C++Dynamiczne struktury danych w języku C++,
Dynamiczne struktury danych w języku JavaDynamiczne struktury danych w języku Java,
Dynamiczne struktury danych w języku PythonDynamiczne struktury danych w języku Python.
Słownik
technika programowania, w której funkcja wywołuje samą siebie aż do napotkania przypadku podstawowego
struktura danych, w której informacje są pobierane ze szczytu i na niego odkładane; struktura typu LIFO (Last In, First Out – ostatni na wejściu, pierwszy na wyjściu)
liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do przetwarzania; struktura typu FIFO (First In, First Out; pierwszy na wejściu, pierwszy na wyjściu)