Temat 3

Question 1

Czym jest kolejka? Jakie mamy rodzaje kolejek?

Answer 1

Kolejka do abstrakcyjna struktura danych, w której dodawanie i usuwanie jest ze sobą powiązane.

Rodzaje:
- FIFO (First-In First-Out)
- LIFO (Last-In First-Out)
- Dwukierunkowa (Deque) - dodawanie i usuwanie na obu końcach
- Cykliczna
- Priorytetowa

Question 2

Na jakich strukturach możemy zaimplementować kolejkę?

Answer 2

Listy wiązane, tablica dynamiczna, grafy/drzewa

Question 3

Czym różni się stos od typowej kolejki?

Answer 3

Stos jest to implementacja kolejki LIFO, gdzie elementy dodawane są na szczyt i ze szczytu są usuwane.

Question 4

Dlaczego implementacja kolejki priorytetowej na liście wiązanej jest naiwna?

Answer 4

Implementacja kolejki priorytetowej musi mieć wydajną metodę extract_max/min, a żeby to osiągnąć, musi wydajnie przeszukiwać kolejkę w poszukiwaniu elementu.
Przeszukiwanie listy w poszukiwaniu wartości jest naiwne na czas złożoności obliczeniowej, która w najgorszym przypadku wynosi O(n), czyli musimy przejść przez całą listę, aby znaleźć nasz element.

Question 5

Złożoność operacji dla kolejki w zależności od implementacji: lista wiązana, tablica dynamiczna

Answer 5

ENQUEUE: Lista wiązana=O(1) | Tablica dynamiczna=O(1) A
DEQUEUE: Lista wiązana=O(1) | Tablica dynamiczna=O(1) A
ISEMPTY: Lista wiązana=O(1) | Tablica dynamiczna=O(1)
PEEK: Lista wiązana=O(1) | Tablica dynamiczna=O(1)