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.

Rz8yv1nQfvMZg

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.

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.

RYVejcJGTw53w

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.

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 $n$ elementów. Indeks wskazujący szczyt jest przechowywany jako zmienna indeks_szczytu. Tablicę indeksujemy od wartości $0$.

funkcja dodaj_na_stos(a):
	jeżeli indeks_szczytu >= n wykonaj:
		wypisz("Przepełnienie stosu")
	w przeciwnym razie wykonaj:
		stos[indeks_szczytu] ← a
		indeks_szczytu ← indeks_szczytu + 1

funkcja usun_ze_stosu():
	jeżeli indeks_szczytu = 0 wykonaj:
		wypisz("Stos jest już pusty")
	w przeciwnym razie wykonaj:
		indeks_szczytu ← indeks_szczytu - 1

funkcja odczytaj_ze_stosu():
	zwróć stos[indeks_szczytu - 1]

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++P6mSvmmsbDynamiczne struktury danych w języku C++,

• Dynamiczne struktury danych w języku JavaPMA5KQsuoDynamiczne struktury danych w języku Java,

• Dynamiczne struktury danych w języku PythonPLwXvlJgeDynamiczne struktury danych w języku Python.

Kolejka

Każdy z nas miał do czynienia z kolejkąkolejkakolejką 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 danychPfksScRhODynamiczne struktury danych.

RsOWIlobQN3lA

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

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.

R14sBe9QsU485

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.

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 $n$ 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 $n-1$. Zmienną indeks_koniec inicjalizujemy z kolei wartością o jeden mniejszą, czyli $n-2$. Tablicę indeksujemy od wartości $0$.

Funkcja dodaj_do_kolejki(a):
	jeżeli indeks_koniec = indeks_poczatek wykonaj:
		wypisz("Kolejka jest pełna")
	w przeciwnym razie wykonaj:
		kolejka[indeks_koniec] ← a
		indeks_koniec ← indeks_koniec - 1
        
		jeżeli indeks_koniec < 0:
			indeks_koniec ← n - 1

Funkcja usun_z_kolejki():
	jeżeli indeks_koniec = (indeks_poczatek - 1)
		LUB indeks_poczatek = 0 ORAZ indeks_koniec = n - 1:
		wypisz("Kolejka jest pusta")
	w przeciwnym razie:
		indeks_poczatek ← indeks_poczatek - 1
        
		jeżeli indeks_poczatek < 0:
			indeks_poczatek ← n - 1

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 $n$, lecz $n-1$ 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.

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++P6mSvmmsbDynamiczne struktury danych w języku C++,

• Dynamiczne struktury danych w języku JavaPMA5KQsuoDynamiczne struktury danych w języku Java,

• Dynamiczne struktury danych w języku PythonPLwXvlJgeDynamiczne struktury danych w języku Python.

Słownik