Lineární datové struktury - seznam, zásobník, fronta

Datové struktury

• = Způsob uložení entit, které se vyskytují v programu, do paměti
  • entita = jakákoliv přesně definovaná množina dat

Lineární datové struktury

• Prvky jsou seřazeny do posloupnosti (má smysl uvažovat o pořadí prvků)
• U každého prvku známe předka a následníka (pokud existují)

Zásobník (Stack)

• Pracuje na principu LIFO (Last In First Out)
• Operace
  • Push(S, x) $\to$ nahrazuje insert
  • Pop(S) $\to$ odstraní naposled přidaný prvek a vrátí jej
• 
• Zásobník se přirozeně používá při implementaci rekurze. Když je funkce volána, její kontext (lokální proměnné, návratová adresa, atd.) se uloží na zásobník. Když se funkce dokončí, její kontext se ze zásobníku odstraní.
• Dále se používá například při průchodu grafem do hloubky (DFS).

Fronta (Queue)

• Pracuje na principu FIFO (First In First Out)
• Operace
  • Enqueue(Q, x) $\to$ nahrazuje insert
  • Dequeue(Q) $\to$ odstraní nejdříve přidaný prvek a vrátí jej
• 
• Fronty jsou využívány v aplikacích zpracovávajících data v reálném čase, jako jsou streamy videa nebo zvuku, kde data přicházejí postupně a musí být zpracována ve správném pořadí.
• Dále se používá například při průchodu grafem do šířky (BFS).

Spojový seznam (cyklický, se zarážkou)

• Prvky jsou lineárně za sebou, nelze přistupovat pomocí indexu, zapojení je zajištěno pomocí pointerů
• Nemusí být v paměti za sebou
• Jednosměrný = u prvků známe následovníka
• Obousměrný = u prvků známe následovníka i předchůdce
• 
• Spojové seznamy jsou ideální pro situace, kdy není předem znám počet prvků, které budou uloženy. Díky dynamické alokaci paměti může seznam růst nebo se zmenšovat dle potřeby, aniž by bylo nutné alokovat velký blok paměti najednou.

Navigace

Předchozí: O-notace a růst funkcí, definice, vlastnosti, příklady použití Následující: Problém třídění, rozdělení třídících algoritmů, dolní mez složitosti třídění porovnáváním Celý okruh: 1. Teoretické základy informačních technologií