Wybrane struktury danych i ich zastosowanie (lista, stos, kolejka)

1. Lista

Jest to liniowa struktura danych. Rozróżniane są dwa podstawowe rodzaje list: lista jednokierunkowa w której z każdego elementu możliwe jest przejście do jego następnika oraz lista dwukierunkowa w której z każdego elementu możliwe jest przejście do jego poprzednika i następnika. Dojście do elementu i-tego wymaga przejścia przez kolejne elementy od pierwszego do docelowego.

Pozwala na wstawianie elementów z przodu, z tyłu i w środku ciągu elementów. Możliwe jest także usuwanie elementów.

Za pomocą listy można symulować stos i kolejkę.

Lista jednokierunkowa:

Lista dwukierunkowa:

1. Kolejka

Jest to liniowa struktura danych, w której elementy pobieramy z początku, a nowe elementy wstawiamy na koniec. Specjalną modyfikacją kolejki jest kolejka priorytetowa – każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet, który modyfikuje kolejność późniejszego wykonania. Oznacza to, że pierwsze na wyjściu niekoniecznie pojawią się te dane, które w kolejce oczekują najdłużej, lecz te o największym priorytecie.

Kolejka wykorzystywana jest przede wszystkim w sytuacjach związanych z obsługą zdarzeń ale również w algorytmach np. w przeszukiwaniu grafu wszerz albo w algorytmie Dijkstry.

1. Stos

Jest to liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane. Jest przeciwieństwem kolejki.

Push – dokładanie elementu na stos, Pop – zdejmowanie elementu ze stosu.

Stos wykorzystywany jest np. przy obliczaniu wyrażeń zapisanych w odwrotnej notacji polskiej.

Bibliografia:

• http://edu.i-lo.tarnow.pl

• http://pl.wikipedia.org

Adam Sawicki kl.3c