Abstract, zásobník, fronta, spojáky, stromy

BI-SPOL.21-23
  • Abstraktní datový typy
    • specifikace
    • implementace
  • Zásobník
  • Fronta
  • Pole
  • Seznam
  • Tabulky
  • Set (množina)
  • Implemetace pomocí
    • Spojového seznamu
    • Stromu
    • Pole

Klasický datový tip

  • Specifikují množinu hodnot
  • Specifikují množinu hodnot
  • Mají jasně danou implementaci (přesně daný postup operací a ukládání dat)
  • Známe:
    • Jednoduché primitivní — nedělitelné/atomické hodnoty
    • Strukturované — skládají se ze složek
    • Ukazatele — adresy do paměti, závislé na typu na který ukazují
    • Jiné — např. funkce

Abstraktní datový typ

  • Tento datový typ nemá danou implementace, jen funkčnost
    • Definují množinu hodnot
    • Definují množinu operací
    • Je popsán signaturou operací a axiomy (funkčnosti/počáteční podmínky a chování)
      • Operandy
      • datové typy in/out

Zásobní

  • kontejner, kde nejnovější prvky jsou odebrány první (LIFO)
    • push(s, x) – vložení prvku na vrchol zásobníku p
    • pop(s) – odebrání prvku na vrcholu zásobníku
    • front(s) – nahlédnutí na vrchol zásobníku bez odebrání prvku
    • isEmpty(s) – ověření, zda je zásobník prázdný
  • Implementace:
    • pomocí pole má omezení, buď musí být konstantní velikost, nebo v případě nafukovacího může být problém při realokaci
    • pomocí spojového seznamu (ukazatele na předchozí prvek)

Fronta

  • Nejstarší prvky jsou odebrány první (FIFO)
  • Rozhraní (obdobně jako u zásobníku):
    • push(q, x)
    • pop(q)
    • front(q)
    • isEmpty(q)
  • Implementace:
    • pomocí pole — cyklický buffer, pevná velikost fronty, dva indexy ukazují na první volné místo a první ve frontě, pokud se rovnají, je fronta plná
    • pomocí spojového seznamu – větší režie
  • Variantou je prioritní fronta – prvky odebírány dle priority

Pole

  • Lze ke všem prvkům přistupovat přímo v čase O(1)
  • Může být vícerozměrné (pak ale problémy s nafukováním)
  • Implementace:
    • pomocí jednorozměrného pole (lze i více dimenzí, např. ukládat řádky za sebe)
    • pomocí vícerozměrného pole

List

  • Lze přistupovat ke všem prvkům
  • Prvky se mohou opakovat a pořadí prvků je důležité
  • Implementace:
    • pomocí pole – nutné zvětšování pole (pomocí realloc)
    • (obousměrný) spojový seznam (přístup a vkládání jinam než na konec/konce seznamu je lineární)

Mapa

  • Kontejner, který obsahuje data identifikovaná klíčem
  • Chová se jako množina, která má pod klíči navíc data
  • Implementace:
    • pole (klíče == indexy v poli)
    • pole (seřazené dle klíčů, obsahuje páry key-value)
    • spojový seznam (seřazený dle klíčů, obsahuje páry key-value)
    • hash table
    • binární vyhledávací strom

Set

  • kontejner, který obsahuje prvky bez duplikátů
  • typické operace:
    • vypsání všech prvků
    • vložení / odebrání prvku
    • kontrola přítomnosti prvku
    • množinové operace – průnik, sjednocení, rozdíl . . .
  • implementace:
    • seřazené/neseřazené pole — pomalé i na seřazeném (nutnost udržení uspořádání)
    • pomocí spojového seznamu (seřazeného) — jednoduchá změna velikosti, ale vysoká režie
    • binární vyhledávací strom
    • hash table

Vytvořeno: 27. 5. 2026, 12:00
Poslední aktualizace: 9. 6. 2026, 12:18