Egyéb adatszerkezetek

Dictionary-k

A Dictionary vagy más néven Hash-Map olyan adatszerkezet, amely kulcs-érték párokat tárol. A kulcsok egyediek és indexálásra használhatók a hozzájuk tartozó értékek lekérdezésére.

A tömbök indexelésével szemben a Dictionary index típusa bármi lehet.

A Dictionary elnevezés találó, hiszen ahogy egy szótár is egy könnyen kereshető kulcshoz (szó neve) tárol el egy extra adatot (szó definíciója) ugyanúgy ezt teszi a Dictionary is.

using System.Collections.Generic;

//...

// Létrehozás
Dictionary<string, Vector3> positions = new Dictionary<string, Vector3>();
// Kulcs: string
// Érték: Vector3

// Kulcs-érték párok hozzáadása
positions.Add("John", new(1,2,4));
positions.Add("Emily", new(1,3,0));
positions.Add("Michael", new(7,2,2));

// Lekérdezés
Vector3 johnPsoition = positions ["John"];

// Felülrás
positions["Michael"] = new(7,3,3);

// Kulcs-érték párok törlése
studentGrades.Remove("John");

Egyéb hasznos Dictionary műveletek:

// Kulcs-érték párok száma:
int count = dictionary.Count;

// Ellenőrizzük, hogy a Dictionary tartalmazza-e a megadott kulcsot:
bool containsKey = dictionary.ContainsKey("key");

// Ellenőrizzük, hogy a Dictionary tartalmazza-e a megadott értéket.
bool containsValue = dictionary.ContainsValue(42);

// Megpróbálunk megtalálni egy értéket egy kulcs alapján
bool isFound = dictionary.TryGetValue("key", out Vector3 value);

// Az összes kulcs-érték pár eltávolítása a Dictionary-ből:
dictionary.Clear();

// Dictionary bejárása kulcs-érték párok szerint
foreach (KeyValuePair<string, int> pair in studentGrades)
{
	Debug.Log("Name: " + pair.Key + ", Grade: " + pair.Value);
}

A Dictionary egyik nagy előnye, hogy a keresés nagyon gyorsan történik bennük.

A C# Dictionary osztály implementációja hash táblát használ a kulcs-érték párok tárolására. Ennek köszönhetően a keresési műveletek nagyon gyorsak lehetnek. A hash táblák hatékonyak a kulcs alapú keresésekben az alábbi okok miatt:

1. Hash függvények: A Dictionary használata során

Hashset

A HashSet, egyedi elemek kollekcióját tárolja sorrend nélkül. Használata hasonló a Listához a következő különbségekkel:

1. A HashSet-ben egy elem csak egyszer szerepelhet. Ha új elemet tennénk bele, ami már szerepel benne, nem történik semmi.
2. A HashSet elemeinek nincs sorrendje.
3. Mivel az elemeknek nincs sorrendjük, nem indexelhetők, csak foreach ciklussal lehet végig iterálni rajta.
4. Az elemek hozzáadása, és kivétele, valamint annak vizsgálata, hogy a set tartalmaz-e egy elemet nagy mennyiségű adathalmazon is igen gyorsan történik. (Ideális esetben O(1) a keresés sebessége a kollekció méretére nézve: )

Használata:

using System.Collections.Generic;

// HashSet létrehozása és elemek hozzáadása
HashSet<string> set = new HashSet<string>();
set.Add("alma");
set.Add("körte");
set.Add("szilva");
set.Add("alma"); // Duplikált elem, nem kerül hozzáadásra - Nincs error sem

// Elemek megjelenítése
foreach (string elem in set)
{
    Debug.Log(elem);
}

// Elemek számának lekérdezése
Debug.Log("Elemek száma: " + set.Count);

// Elemek eltávolítása
set.Remove("körte");

// Elemek újra megjelenítése
Debug.Log("Elemek a körte eltávolítása után:");
foreach (string elem in set)
{
    Debug.Log(elem);
}

// Ellenőrzés, hogy egy elem a halmazban van-e
bool containsAlma = set.Contains("alma");
Debug.Log("Tartalmazza az 'alma' elemet? " + containsAlma);

// HashSet ürítése
set.Clear();

Tehát a HashSet akkor hasznos, ha egyedi elemeket kell tárolnunk, és gyorsan szeretnénk ellenőrizni, hogy egy adott elem már benne van-e a halmazban.

Stack

A Stack azaz verem egyik beépített adatszerkezet a C# nyelvben, és LIFO - Last-In, First-Out működést valósítja meg: A legutóbb hozzáadott elem mindig az első, amelyet eltávolíthatunk.

Fontos speciális műveletei:

1. Push: Az elem hozzáadása a veremhez. Az új elem mindig a legfelső pozícióra kerül.
2. Pop: Az elem eltávolítása a veremből. A legfelső elem kerül eltávolításra, és visszaadja azt.
3. Peek: A verem legfelső elemének lekérdezése anélkül, hogy az eltávolításra kerülne. Csak az elemet adja vissza.

using System.Collections.Generic;

//...

Stack<string> stack = new Stack<string>();

stack.Push("elem1");
stack.Push("elem2");
stack.Push("elem3");

Debug.Log("A legfelső elem: " + stack.Peek());  // Elem kivétele nélkül

string removedElement = stack.Pop();
Debug.Log("Az eltávolított elem: " + removedElement);

// Elemek számának lekérdezése
Debug.Log("Elemek száma a veremben: " + stack.Count);

// Kollekció törlése
stack.Clear(); 

A Stack működés szempontjából egy listához hasonló, csupán más interface-szel (függvényekkel) férünk hozzá az elemeihez.

A Stack-et használják a programozási nyelvek, például a C#, hogy nyomon kövessék egy program futását egymásba ágyazott függvényhívások mellett. Ezt a Stack-et gyakran "call stack"-nek vagy "execution stack"-nek nevezik.

A call stack egy verem, amelyben a program futása során minden függvényhívás nyomot hagy. Amikor egy függvényt meghívunk, a hívás helye, paraméterei és más releváns információk a verem tetejére kerülnek. Amikor a függvény végrehajtása befejeződik, a hívás a veremből eltávolításra kerül, és a program folytatja a következő függvény vagy utasítás végrehajtását.

Ennek a mechanizmusnak a segítségével a programok nyomon követhetik a függvényhívások sorrendjét és az aktuális visszatérési pontokat. Ez lehetővé teszi a programnak, hogy a helyes sorrendben és helyen térjen vissza a függvényekből, és tudja, a memóriában hova kell ugrani a folytatáshoz.

A call stack mérete általában véges lenni. Ez azt jelenti, hogy a call stack csak bizonyos számú függvényhívást tud tárolni, mielőtt megtelik.

Amikor egy függvény meghívódik, a szükséges hely a call stack-en a függvényhívás adatainak (visszatérési cím, paraméterek, lokális változók stb.) tárolására kerül. Ha egy program túl sok függvényt hív egymásba ágyazottan, vagy ha egy függvény túl mélyen rekurzív hívást végez, akkor a call stack megtelhet.

Amikor a call stack megtelik, akkor az újabb függvényhívások nem tudnak megtörténni, és a program futása a "StackOverflowException” hibával elszáll.

Erről kapta a nevét a népszerű programozói fórum, a stackoverflow.com

Queue

A Queue, azaz sor, egy másik beépített adatszerkezet a C# nyelvben, a Stack párja. Míg a Stack a LIFO (Last-In, First-Out) elvet követi, addig a Queue az FIFO (First-In, First-Out) elvet alkalmazza. Ez azt jelenti, hogy a Queue-ba az elemeket az egyik végén helyezzük el, és a másik végéntávolítjuk el.

Elképzelhetjük a Queue-t úgy, mint emberek sorbanállását egy pénztárnál. Aki korábban állt be, az korábban kerül kiszolgálásra

Fontos műveletei:

1. Enqueue: Az elem hozzáadása a sorhoz. Az új elem mindig a legutolsó pozícióra kerül.
2. Dequeue: Az elem eltávolítása a sorból. A legelső elem kerül eltávolításra, és visszaadja azt.
3. Peek: A legelső (következőre sorra kerülő) elem lekérdezése anélkül, hogy az eltávolításra kerülne.

Használata:

Queue<string> queue = new Queue<string>();

// Elemek hozzáadása a sorhoz
queue.Enqueue("Első elem");
queue.Enqueue("Második elem");
queue.Enqueue("Harmadik elem");

// Az első elem kiolvasása a sorból
string frontElement = queue.Dequeue();
Debug.Log("Az első elem a sorban: " + frontElement);

// A sor elején lévő elem lekérdezése, de nem törlése
string peekedElement = queue.Peek();
Debug.Log("A sor elején lévő elem: " + peekedElement);

// Elemek száma a sorban
Debug.Log("Elemek száma a sorban: " + queue.Count);

// Kollekció törlése
queue.Clear(); 

Miért használnék Stack-et vagy Queue-t egy feladatra, mikor a List tud mindent és még többet is?

Előnyük, hogy mivel a Queue és a Stack specifikus működést valósítanak meg, azaz egyfajta adott műveletekre fókuszálnak kifejezőbb, olvashatóbb lehet a kód.