Stos

Stos to dynamiczna, liniowa strukturastrukturastruktura danych typu LIFO (ang. Last‑In, First‑Out –ostatni na wejściu, pierwszy na wyjściu), czyli taka, w której operacje wykonuje się tylko na najnowszym elemencie zwanym wierzchołkiem. Oznacza to, że kolejny element można dodać jedynie na wierzch stosu, jak również usunąć element można tylko z wierzchu stosu.

Strukturę tę najprościej jest wyobrazić sobie np. jako stos książek ułożonych jedna na drugiej – kolejne publikacje możemy umieszczać wyłącznie na wierzchu. Nie mamy bezpośredniego dostępu do książek, które znajdują się poniżej leżącej na samym szczycie, ponieważ wyciągnięcie którejś z nich może zburzyć ich układ. Aby dostać się do interesującej nas książki, musimy ściągnąć kolejno wszystkie pozycje znajdujące się nad nią, zaczynając od wierzchołka stosu.

W najprostszej postaci stos może być realizowany w formie tablicy o stałym rozmiarze, jednak nie zapewnia to możliwości zapisywania nieznanej z góry liczby elementów, co może prowadzić do błędu przepełnienia stosuprzepełnienie stosuprzepełnienia stosu. Drugim rozwiązaniem może być użycie tablicy dynamicznej, ale wtedy dopasowywanie rozmiaru tablicy do liczby elementów jest operacją nieefektywną o złożoności czasowej $O(n)$. Elementami stosu nie muszą być jednak komórki tablicy – mogą to być tworzone i usuwane w zależności od potrzeb struktury reprezentujące węzły. Wtedy każdy węzeł zawiera odkładaną na stos wartość oraz dowiązanie do kolejnego węzła w postaci wskaźnikawskaźnikwskaźnika lub referencjireferencjareferencji. Tak połączone węzły tworzą strukturę dynamiczną nazywaną listą jednokierunkową (dokładniej omówimy ją nieco niżej). Wskaźnik ostatniego węzła takiej listy zawiera wartość pustąwartość pustawartość pustą, często oznaczaną jako NULL lub NIL.

R1Ea0MDsJSn7H

Ilustracja przedstawia działanie stosu.
Na środku znajdują się cztery bloki z wartościami liczbowymi: 2, 4, 7, 6.
Blok na samej górze z wartością 2 oznaczony jest jako top().
Długość czterech bloków z wartościami oznaczona jest jako size().
Od bloku z wartością 2 wychodzi strzałka do przekreślonego bloku.
Strzałka ta podpisana jest jako pop().
Powyżej znajduje się blok z wartością 0.
Wychodzi od niego strzałka z podpisem push().
Wskazuje ona na miejsce nad blokiem oznaczonym jako top() z liczbą 2.

Przy implementacji stosu należy zdefiniować kilka operacji (w nawiasach zapisano ich formalne, angielskie nazwy):

• odłóż(element) – (push) – dodaje element na wierzch stosu,

• zdejmij() – (pop) – usuwa element z wierzchu stosu,

• wierzchołek() – (peek) – zwraca element znajdujący się na szczycie stosu,

• rozmiar() – (size) – zwraca aktualną liczbę elementów stosu.

Zalety listy jako struktury implementującej stos:

• operacje odkładania i zdejmowania elementu mają stałą złożoność czasową $O(1)$,

• lista ułatwia rozwiązywanie problemów bazujących na rekurencji.

Wady listy jako struktury implementującej stos:

• utrudniony, a przez to spowolniony (liniowy) dostęp do elementów innych niż wierzchołek,

• wykorzystanie dodatkowej pamięci na dowiązania.

Zalety tablic w implementacji stosu:

• prosta implementacja i użycie,

• szybki (stały) dostęp do elementów.

Wady tablic (statycznych i dynamicznych) w implementacji stosu:

• operacje odkładania i zdejmowania mają liniową złożoność czasową $O(n)$,

• słaba skalowalność.

Kolejka

Kolejka jest dynamiczną strukturą danych, w której dane są uporządkowane liniowo. Jest to struktura typu FIFO (ang. First‑In, First‑Out - pierwszy na wejściu, pierwszy na wyjściu), czyli taka, w której nowy element można dodać jedynie na końcu kolejki, natomiast usuwanie elementów odbywa się tylko na jej początku.

Budowę i zasadę działania kolejki możemy łatwo skojarzyć z kolejką w sklepie. Klient, który był pierwszy w kolejce, opuszcza ją również jako pierwszy. Każdy wchodzący do sklepu klient ustawia się na końcu kolejki i jest obsługiwany zgodnie z kolejnością, w jakiej do niej dołączył. Dopiero po obsłużeniu pierwszej osoby sprzedawca może obsłużyć drugą, a potem następną osobę stojącą w kolejce.

Kolejkę realizować można przy użyciu tablicy, ale tak samo jak w przypadku stosu nie jest to rozwiązanie elastyczne, dlatego również w tej sytuacji kolejka często implementowana jest przy użyciu listy jednokierunkowej.

RIYQjqcPQPzTi

Ilustracja przedstawia przykładowe działanie kolejki.
Znajdują się w niej cztery bloki z wartościami liczbowymi: 2, 0 ,1, 1.
Blok z wartością 2 oznaczony jest jako tail().
Pierwszy blok z wartością 1 oznaczony jest jako head().
Długość wszystkich bloków oznaczona jest jako size().
Od bloku head() z wartością 1 wychodzi strzałka podpisana jako dequeue() wskazująca na przekreślony blok poniżej.
Powyżej kolejki znajduje się blok z wartością 4, od którego wychodzi strzałka z podpisem enqueue(), wskazująca na ostatnie miejsce w kolejce przed blokiem tail() o wartości 2.

Wyróżniamy kilka metod charakterystycznych dla kolejki (w nawiasach zapisano formalne, angielskie nazwy operacji):

• dodaj(element) – (enqueue) – dodaje nowy element na koniec kolejki,

• usuń() – (dequeue) – usuwa jeden element z przodu kolejki,

• głowa() – (head) – zwraca pierwszy element kolejki,

• ogon() – (tail) – zwraca ostatni element kolejki,

• rozmiar() – (size) – zwraca aktualną liczbę elementów kolejki.

Kolejka jako struktura danych implementowana przy pomocy listy jednokierunkowej ma następujące zalety:

• operacje dodawania i usuwania elementów mają stałą złożoność czasową $O(1)$,

• umożliwia efektywne zarządzanie dużą ilością danych,

• jest użyteczna przy implementacji usług dla wielu użytkowników,

• zapewnia szybką wymianę danych między procesami.

Wadą kolejki jako struktury danych jest natomiast brak swobodnego dostępu do danych (mamy dostęp jedynie do pierwszego elementu).

Kolejka priorytetowa

Kolejka priorytetowa to dynamiczna, liniowa struktura danych, która od zwykłej kolejki różni się tym, że każdy z jej elementów ma przydzielony priorytet – im jest on wyższy, tym bliżej głowy kolejki zostanie umieszczony dany element.

Budowę i zasadę działania tej wersji kolejki możemy porównać z kolejką, w której pewne osoby mają pierwszeństwo (np. kobiety w ciąży, osoby niepełnosprawne, rodziny z dziećmi). Każdy klient obsługiwany jest zgodnie z kolejnością, jednak jeśli do kolejki dołączy osoba należąca do grupy uprzywilejowanej, może ona ominąć klientów stojących w kolejce i przejść na jej początek.

Wyróżniamy kilka metod charakterystycznych dla kolejki priorytetowej (w nawiasach zapisano formalne, angielskie nazwy operacji):

• dodaj(element) – (enqueue) – dodaje nowy element na odpowiedniej pozycji w kolejce, zgodnie z priorytetem,

• usuń() – (dequeue) – usuwa jeden element z przodu kolejki,

• głowa() – (head) – zwraca pierwszy element kolejki,

• ogon() – (tail) – zwraca ostatni element kolejki,

• rozmiar() – (size) – zwraca aktualną liczbę elementów kolejki.

Lista

Lista to liniowa, dynamiczna struktura danych. Podobnie jak w przypadku stosu czy kolejki, dodanie nowego elementu rozszerza listę, zatem nie jesteśmy zmuszeni do wskazania rozmiaru podczas jej tworzenia. Lista jest zbudowana z węzłów, z których każdy składa się z pojedynczej przechowywanej danej oraz wskaźnikówwskaźnikwskaźników lub referencjireferencjareferencji odnoszących się do kolejnego i poprzedniego elementu listy (w zależności od implementacji i wersji). Programy mogą dowolnie dołączać i usuwać węzły listy wedle zadanych instrukcji.

Lista posiada kilka charakterystycznych dla siebie metod (w nawiasach zapisano formalne, angielskie nazwy operacji):

• głowa() – (head) – zwraca pierwszy element listy,

• ogon() – (tail) – zwraca ostatni element listy,

• dodaj(element) – (add) – dodaje nowy element na koniec listy,

• usuń(element) – (remove) – usuwa wskazany element,

• następny() – (next) – zwraca następny element w liście,

• poprzedni() – (prev) – zwraca poprzedni element w liście,

• rozmiar() – (size) – zwraca aktualną liczbę elementów listy.

Lista jednokierunkowa

Lista jednokierunkowa to lista, której węzły zawierają pewne dane oraz wskaźnik na następny węzeł. Przechodzenie takiej listy możliwe jest tylko w jednym kierunku, począwszy od pierwszego węzła wskazywanego przez zmienną głowa (ang. head). Jak już wcześniej wspomnieliśmy, wskaźnik ostatniego węzła listy jednokierunkowej zawiera wartość pustą, czyli NULL (lub NIL).

RdvtP5P31dqww

Ilustracja przedstawia pięć opisanych bloków w kształcie kwadratu.
Kwadrat pierwszy: head, wychodzi od niego strzałka skierowana w prawą stronę.
Kwadrat drugi podzielony na dwie części: środkowa z wartością: 90, prawa dolna: next Od next wychodzi strzałka skierowana na następny blok po prawej stronie.
Kwadrat trzeci podzielony na dwie części: środkowa z wartością: 12, prawa dolna: next. Od next wychodzi strzałka skierowana na następny blok po prawej stronie.
Kwadrat czwarty podzielony na dwie części: środkowa z wartością: 1, prawa dolna: next. Od next wychodzi strzałka skierowana na następny blok po prawej stronie.
Kwadrat piąty podzielony na dwie części: środkowa z wartością: 22, prawa dolna: next.

Zalety listy jednokierunkowej:

• struktura dynamiczna (alokacja pamięci w miarę potrzeby),

• prostota implementacji operacji wstawiania i usuwania elementów, jak i samej struktury,

• łatwy dostęp do węzłów znajdujących się w dalszej części struktury.

Wady listy jednokierunkowej:

• brak bezpośredniego dostępu do elementów,

• dłuższy niż w przypadku tablic czas dostępu do elementu wewnątrz listy,

• wymaganie większej ilości pamięci (niż w przypadku tablicy) ze względu na konieczność zapisywania wskaźnika do następnego elementu,

• brak możliwości przejścia do poprzedniego węzła.

Lista dwukierunkowa

Lista dwukierunkowa w każdym elemencie listy przechowuje odniesienie zarówno do następnika, jak i poprzednika elementu w liście. Takie rozwiązanie umożliwia swobodne przemieszczanie się po liście w obie strony.

Rv4E1vBrs8xBz

Ilustracja przedstawia sześć opisanych bloków w kształcie kwadratu.
Kwadrat pierwszy: head, wychodzi od niego strzałka skierowana w prawą stronę.
Kwadrat drugi podzielony na trzy części lewa górna: prev, środkowa z wartością: 90, prawa dolna: next.
Z prev wychodzi strzałka skierowana w lewą stronę na napis: NIL, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
Kwadrat trzeci podzielony na trzy części lewa górna: prev, środkowa z wartością: 12, prawa dolna: next.
Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
Kwadrat czwarty podzielony na trzy części lewa górna: prev, środkowa z wartością: 1, prawa dolna: next.
Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na następny blok po prawej stronie.
Kwadrat piąty podzielony na trzy części lewa górna: prev, środkowa z wartością: 22, prawa dolna: next.
Z prev wychodzi strzałka skierowana w lewą stronę na poprzedni blok, od next wychodzi strzałka skierowana na napis NIL po prawej stronie.
Na końcu znajduje się ostatni kwadrat podpisany jako: tail zawierający napis: next.
Wychodzi od niego strzałka wskazująca na poprzedni blok.

Zalety listy dwukierunkowej:

• alokacja pamięci w miarę potrzeby,

• możliwość łatwego odwrócenia kolejności elementów w strukturze,

• możliwość przechodzenia listy w obu kierunkach.

Wady listy dwukierunkowej:

• wymaganie większej ilości miejsca w pamięci w porównaniu ze zwykłą tablicą,

• dłuższy niż w przypadku tablic czas dostępu do elementu,

• brak bezpośredniego dostępu do elementów.

Między listą jednokierunkową i dwukierunkową występują istotne różnice, które należy brać pod uwagę, wybierając jedną z nich jako strukturę do przechowywania danych.

Lista jednokierunkowa:

• wymaga przechowywania jedynie jednego wskaźnika na początek listy,

• zajmuje mniej miejsca w pamięci niż lista dwukierunkowa,

• zalecana do implementowania stosu lub kolejki.

Lista dwukierunkowa:

• wymaga przechowywania wskaźników na początek i koniec listy,

• zajmuje więcej miejsca w pamięci niż lista jednokierunkowa,

• zalecana do implementowania stosu, sterty lub drzewa binarnego.

Porównanie złożoności czasowej operacji na listach:

Słownik