Wikipedysta:Yusek/Matematyka dyskretna/Struktura danych
Lista
[edytuj]Aby uporządkować dane często używa się różnych list takich jak stos i kolejka.
Stos
[edytuj]Stos jest to struktura w której dane są kładzione na szczycie i ztamtąd zdejmowane. Dobrym przykładem stosu jest stos książek. Wyobraż sobię, że mamy książki na stole, żeby zdjąć jakąś książkę musimy zdejmować je po kolei od góry, podobnie jeśli chcemy dołożyć kilka książek. Ten sposób dodawania nazywamy LIFO (Last in First out).
Kolejka
[edytuj]Kolejka jest inną strukturą danych jest kolejka. W kolejce dane są dodawane z jednej strony a zabierane z drugiej. Przykładem kolejki jest kolejka do kasy, ludzie przychodzą na koniec kolejki do kasy a przy kasie wychodzą (z biletami czy zakupamy). Ten system nazywa się FIFO (First in First out).
Stos vs. kolejka
[edytuj]Wiele problemów można rozwiązać zarówno za pomocą algorytmu mającego stos jak i wykorzystującego kolejkę. Załużmy że chcemy poszukać kogoś kto ma jakąś książkę. Mamy kilka numerów telefonów do kolegów i pytamy czy mają tą książkę a jeśli nie mają czy wiedzą kto by miał. Następny przykładem jest przeszukiwanie drzew wprawdzie o drzewach będzie szerzej w następnym rodziale.
Szukanie książki
[edytuj]Wersja ze stosem
[edytuj]- Wkładamy na stos numery które mamy
- Dzwonimy do osoby której numer jest na szczycie
- Pytamy czy osoba ma książkę lub ewentualnie numer telefonu do osoby która mogła by mieć i kładziemy ją na szczycie.
- A następnie powtarzamy ostanie dwa kroki aż znajdziemy książkę lub skończą się nam numery.
Wersja z kolejką
[edytuj]- Wkładamy do kolejki numery telefonów
- dzwonimy do osoby która jest napoczątku naszej kolejki
- Pytamy czy ma książkę lub ewentualnie numer telefonu do kogoś kto by miał książkę. I dopisujemy te numery na końcu kolejki oraz skreślamy ten numer.
- Potem powtarzamy to tak długo aż będziemy mieć książkę albo wykreślimy wszystkie numery.
Przeszukiwanie drzewa
[edytuj]Wersja ze stosem
[edytuj]Mamy dany stos, który na początku jest pusty oraz wierzchołek drzewa. Podczas przeszukiwania kładziemy na stos wszystkie nie zaznaczone wierzchołki a następnie wybieramy ostani z nich i dopisujemy wierzchołki z którymi ten ma kontakt w przypadku braku takich wierzchołków zdejmujemy go ze stosu.
Wersja z kolejką
[edytuj]Mamy kolejkę która jest pusta oraz wierzchołek. Podczas przeszukiwania dodajemy elementy na koniec kolejki jednakże bierzemy wierzchołki znajdujące się na początku kolejki.