PowerPoint Presentation

Kolejka (FIFO – First In
First Out)



Kolejka to struktura danych, w której
element, który został wstawiony do kolejki
jako pierwszy, jako pierwszy z niej jest
wyciągnięty.



Tę strukturę można porównać do kolejki w
sklepie. Osoba, która jako pierwsza
przyjdzie do sklepu, jako pierwsza zostanie
w nim obsłużona i pierwsza wyjdzie ze
sklepu (zakładamy, że nie żyjemy w PRL).



Podobnie jak w przypadku stosu, możliwe są

dwa sposoby realizacji kolejki. Pierwszy w

tablicy (co ogranicza rozmiar kolejki). Drugi,

bazując na strukturze zwanej listą.

Tworzymy wskaźnik do początku kolejki, a

każdy kolejny składnik kolejny przechowuje

wskaźnik do kolejnego elementu kolejki.

Dodatkowo tworzymy wskaźnik, który

przechowuje adres końca kolejki. Elementy

do kolejki wstawiamy od początku struktury,

a zdejmujemy od końca lub na odwrót.



Naszą tablicę można

przedstawić w formie

pierścienia.



Dodając element do kolejki

należy pamiętać, że

wyznaczając indeks

kolejnego wolnego miejsca

w tablicy należy

zabezpieczyć się przed

wyjściem poza obszar

pamięci przypisany do

tablicy. Robimy to dzieląc

indeks kolejnego wolnego

elementu modulo przez

rozmiar tablicy.

Implementacja kolejki z
wykorzystaniem listy
jednokierunkowej



Druga metoda polega na wykorzystaniu listy
jednokierunkowej, nieposortowanej.



Listę taką należy minimalnie zmodyfikować
dokładając dodatkowy wskaźnik wskazujący
zawsze na ostatni element na liście.

Kod kolejki w C++ (4/4).
Destruktor kolejki.

Działa jak uruchomiony wielokrotnie (w pętli
while) Pop, ale nie zwraca wartości.
Destruktor służy do zwolnienia całej
zaalokowanej dynamicznie pamięci (w C++
musi się tym zająć sam programista, np. w
Javie jest to zautomatyzowane).

Kolejka priorytetowa



Kolejka priorytetowa jest strukturą
danych, w której o zdjęciu elementu
z kolejki nie decyduje tylko
kolejność umieszczenia elementu
w kolejce, ale także priorytet.



Pierwszy zostanie obsłużony ten
element, który ma największy
priorytet.

Metody realizacji kolejki
priorytetowej



Możliwe są dwie metody realizacji
kolejki priorytetowej.



W pierwszym przypadku można
wykorzystać listę jednokierunkową
posortowaną – najlepiej malejąco.



Drugim sposobem implementacji
kolejki priorytetowej jest
wykorzystanie kopca.

Kolejka priorytetowa
wykorzystująca posortowaną
listę jednokierunkową.



Wstawianie elementu do takiej struktury

odbywa się na takich zasadach, jak zostały

opisane wcześniej (patrz dodawanie

elementu do listy posortowanej).



Jeśli nasza lista będzie posortowana

malejąco względem priorytetów to

obsługiwać będziemy zawsze jako pierwszy

element na początku listy.



Dla takiej struktury złożoność operacji

wstawiania będzie wynosić O(n), a złożoność

operacji zdejmowania O(1).

Kolejka priorytetowa z
wykorzystaniem kopca



Przy wstawianiu elementu do
takiej kolejki należy wykonać dwie
czynności:



1. Dodać nowy element na
pierwszej wolnej pozycji w kopcu.



2. Naprawić strukturę kopca.

Naprawa
kopca (przy
dokładaniu
jednego
elementu)

Porównujemy
nowowstawiony
(zielony) z ojcem i jeżeli
jest większy to
zamieniamy miejscami.
Wykonujemy tą
operację aż dojdziemy
do korzenia, lub ojciec
będzie większy od syna.

Kopiec



Kopiec to struktura drzewiasta posiadająca korzeń, od
którego rozchodzi się potomstwo, które przechowuje
zawsze mniejsze wartości niż ich ojciec.



Najwyżej w hierarchii kopca znajduje się korzeń, który
przechowuje element o największej wartości.



W kopcu znajdują się także elementy nie posiadające
już potomstwa. Określa się je mianem liści.

Sposoby implementacji
kopca

Kopiec możemy zaimplementować na dwa

sposoby.

1. Drzewo binarne (struktura dynamiczna) -

powstaje on z węzłów przechowujących
dane oraz dwa wskaźniki do potomstwa (do
lewego i prawego syna). Maksymalny
rozmiar kopca jest pseudo-nieograniczony.

2. Tablica (struktura statyczna). Maksymalny

rozmiar kopca jest ograniczony.