Zásobník, fronta, seznam
Všechny tyto ADT implementují IsEmpty (prázdná struktura) a Size (pošet prvků ve struktuře)
Zásobník: ADT Interface: operace Push, Pop, Peek Push vkládá data do zásobníku za sebe Pop vybírá nejpozději vložená data Peek vrátí nejpozději vložená data bez výběru prvku ze struktury = LIFO pamět Všechny operace jsou O(1)
Head: vrchol zásobníku
Implementace objektově: Prvky (objekty) obsahují data a ukazují na nižžší prvky v zásobníku (na prvky pod sebou) Konstruktor: Vytvoříme ukazatel Head, který nastavíme na null Modifikátor: Push vyrvoří pro data nový prvek, který ukazuje na prvek Head (Head bude předchozí), a změní ukazatel Head na vytvořený prvek Selektor: Peek vrátí data prvku Head, pokud Head != null. Pop vrátí stejná data jako Peek, ale před návratem změní ukazatel Head na předchozí prvek (Head = Head.Previous)
Implementace na poli: Máme pode typu stejného jako data Konstruktor: Alokace pole a indexu Head, nastavení Head na -1 Modifikátor: Push zvýší index Head o 1 a zapíše data do pole na tento index. Pokud je index mimo pole, zvětšení pole (např. 2x), a po té zápis Selektor: Peek vrátí prvek pole pod indexem Head, pokud Head >= 0. Pop jako peek, ale před návratem provede Head--, pokud Head >= 0.
Fronta: ADT Interface: operace Push, Pop, Front Push vkládá data do fronty za sebe Pop vybírá nejdříve vložená data Peek vrátí nejdříve vložená data bez výběru prvku ze struktury = FIFO pamět
First: začítek fronty Last: konec fronty
Implementace objektově: Prvky obsahují data a ukazují na následující prvky fronty Konstruktor: Vytvoříme pouze ukazatele First a Last, ukazující na null. Modifikátor: Push vytvoří pro data nový prvek, upraví prvek Last (pokud != null) tak, aby ukazoval na tento prvek, a změní ukazatel Last na tento prvek. Je-li ukazatel First nastaven na null, nastaví tento také na vytvořený prvek. Selektor: Front vrátí data prvku First, pokud First != null. Pop vrátí stejná data jako Peek, ale před návratem změní ukazatel First na následující prvek, pokud First != null (First = First.Next)
Implementace na poli (cyklicky): Máme podle typu stejného jako data a indexy First a Last. Indexy nukazují přímo do pole, nýbrž je proveden přepočet (Index mod Delka pole) abychom využili celé pole. Tato fronta má omezenou délku. Konstruktor: Alokace pole a indexů, nastavení Last na -1 a First na -1 Modifikátor: Pokud ((Last + 1) mod Delka) != (First mod Delka), Push provede Last++ a zapíše data do pole na tento index, jinak chyba (plná fronta). Pokud First = -1, pak First = 0 (první prvek). Selektor: Peek vrátí prvek pole pod indexem First, pokud First <= Last. Pop jako peek, ale před návratem provede First++.
Speciálním případem je například prioritní fronta, která řadí prvky ve frontě podle priority
Seznam: ADT Interface - Iterator nad seznamem: Add, Remove, Get; First, Next, IsLast, případně další (Previous, Last, IndexOf, ...) Add vkládá data na pozici iterátoru. Složitost dle implementace. Remove maže data na pozici iterátoru Get vrátí data na pozici iteratoru First vrátí iterátor na začátek seznamu Next posune iterátor dále IsLast indikuje koncová prvek (Previous v obousměrných seznamech posune iterator na předchozí prvek) (Last posune iterator na poslední prvek) (IndexOf vyhledá prvek ve struktuře) = struktura, do které je možné libovolně zapisovat a číst (na libovolné pozici)
Iterator: ukazatel do struktury
Implementace objektově - nástřel: Prvky ukazují na následující prvky seznamu. Iterátor je dobré implementovat tak, že ve skutečnosti ukazuje na předchozí prvek (Pokud tedy seznam není obousměrný, pak máme metodu Previous a je to jedno). Metoda add vloží prvek za prvek, na který ukazuje iterátor tak, že pouze upraví ukazatele prvků:
Remove je opačný proces, Get vrátí data (Tedy Iterator.Next.Data), První prvek seznamu si uložíme, abychom se mohli rychle vracet, stejně jako poslední prvek. Next provede Iterator.Next = Iterator.Next.Next. Kontrolujeme, zda nejsme mimo seznam.
Obousměrný seznam: Prvky mají i ukazatele na předchozí prvky, a je tedy možné se po nich pohybovat na obě strany.
Kruhový seznam: Poslední prvek neukazuje na null, ale na první prvek. Tyto seznamy jsou použitelné ve speciálních případech (například nastavení segmentů sedmisegmentovky pro digitální hodiny)
Implementace na poli (nástřel): Pole má nevýhodu, že je nutné přesunout prvky doprava od iterétoru, pokud vkládáme prvky. Při mazání lze prvky posunout doleva, nebo do pole uložit hodnotu, která se zcela jistě nebude v poli nebude vyskytovat, nebo vytvořit stínové pole, ve kterém si smazané prvky označíme, a při posunu iterátoru je poté vynecháme. Tento přístup je dobrý pokud pole často upravujeme.
