Az adatszerkezeteket kétféleképp is megkülönböztethetjük.

Felépítés szerint (pl. tömb, fa, hash tábla), vagy pedig a rajtuk elvégezhető műveletek szerint. Erre a két kategóriára nincs általánosan elfogadott szakszó, ezért úgy fogom hívni őket, hogy:

  • Fizikai adatszerkezetek (a felépítés szerinti)
  • Logikai adatszerkezetek (műveletek szerint)

Itt most az utóbbiból mutatok be néhányat.

Verem

  • Angolul stack
  • LIFO (Last-in First-out)

A verem két műveletet definiál:

  • push -> beleteszegy elemet
  • pop -> kiveszi azt az elemet, amelyet legutóljára tettünk bele.

Az alábbi módon tudjuk elképzelni:

v = új üres Verem()    // []
v.push(5)              // [5]
v.push(10)             // [5, 10]
v.push(-1)             // [5, 10, -1]
Kiír(v.pop())          // [5, 10]       Ki: -1
Kiír(v.pop())          // [5]           Ki: 10

Sor

  • Angolul queue
  • FIFO (First-in First-out)

A sor szintén két műveletet definiál:

  • enqueue -> beleteszegy elemet
  • dequeue -> kiveszi azt az elemet, amelyet legelőször tettünk bele.
s = új üres Sor()         // []
s.enqueue(5)              // [5]
s.enqueue(10)             // [5, 10]
s.enqueue(-1)             // [5, 10, -1]
Kiír(s.dequeue())         // [10, -1]       Ki:  5
Kiír(s.dequeue())         // [-1]           Ki: 10

Prioritási sor

  • Angolul priority queue
  • A kivétel sorrendje nem féltétlen a berakás sorrendjében történik
    • Az elemeket sorrendbe kell tudni rendezni
    • A legkisebb értéket veszi ki
ps = új üres PriritásiSor()    // []
ps.hozzáad(5)                  // [5]
ps.hozzáad(10)                 // [5, 10]
ps.hozzáad(-1)                 // [5, 10, -1]
Kiír(ps.kivesz())              // [5, 10]       Ki: -1
Kiír(ps.kivesz())              // [10]          Ki:  5

Halmaz

  • Angolul set
  • Az elemeknek nincs előre definiált sorrendje
  • Minden elem csak egyszer szerepelhet
  • A leggyakrabban használt művelet a “bennevan(): logikai”, általában erre van optimizálva
h = új üres Halmaz()     // []
h.hozzáad(5)             // [5]
h.hozzáad(1)             // [5, 1]
h.hozzáad(11)            // [5, 1, 11]
h.hozzáad(5)             // [5, 1, 11]
h.bennevan(2)            // Hamis
h.bennevan(5)            // Igaz

Szótár

  • Angolul map
    • Map: párosítás
    • Dictionary: szótár
    • Asszociatív tömb: assicative array
  • Minden értékhez tartozik egy egyedi kulcs, amely alapján lehet az értékeket kikeresni
sz = új üres Szótár()
sz.hozzáad(5, "Gyurika")
sz.hozzáad(9, "Petike")
sz[5]                       // "Gyurika"
sz[10]                      // HIBA: nincs 10-es kulcs

A kulcs nem csak szám lehet, persze:

sz = új üres Szótár()
sz.hozzáad("Gyurika", 5.6)
sz.hozzáad("Petike", -8.7)
sz["Petike"]                // -8.7
sz["Csőrike"]               // HIBA: nincs "Csőrike" kulcs

Programkódban

Programkódban természetesen nem csak a fenti pár művelet van definiálva, pl. szinte minden osztályon létezik a Count tulajdonság, a Contains() függvény stb. Érdemes használatkor átnézni őket.

C#

var stack = new Stack<int>();
stack.Push(5);
stack.Push(10);
stack.Push(-1);
Console.WriteLine(stack.Pop()); // -1
Console.WriteLine(stack.Pop()); // 10

var queue = new Queue<int>();
queue.Enqueue(5);
queue.Enqueue(10);
queue.Enqueue(-1);
Console.WriteLine(queue.Dequeue()); // 5
Console.WriteLine(queue.Dequeue()); // 10

// .NET-ben nincs beépített prioritási sor osztály,
// de az alábbi NuGet csomag segít:
// https://www.nuget.org/packages/OptimizedPriorityQueue/
// Az értéknek nem kell megegyeznie a prioritással!
var pq = new SimplePriorityQueue<int, int>();
pq.Enqueue(5, 5);
pq.Enqueue(10, 10);
pq.Enqueue(-1, -1);
Console.WriteLine(pq.Dequeue()); // 5
Console.WriteLine(pq.Dequeue()); // 10

var s = new HashSet<int>();
s.Add(5);
s.Add(1);
s.Add(11);
s.Add(5);   // false visszatérési értékkel jelez, hogy már benne van
Console.WriteLine(s.Count);         // 3
Console.WriteLine(s.Contains(2));   // false
Console.WriteLine(s.Contains(5));   // true

var d = new Dictionary<string, double>();
d.Add("Gyurika", 5.6);
d.Add("Petike", -8.7);
Console.WriteLine(d.ContainsKey("Csőrike"));  // hamis
Console.WriteLine(d["Petike"]);               // -8.7
Console.WriteLine(d["Csőrike"]);              // KeyNotFoundException

Java

Java-ban a verem és sor adatszerkezeteket az ArrayDeque osztályon keresztül használhatjuk.

Deque<Integer> stack = new ArrayDeque<>();
// A végére rekjuk az elemet
stack.addLast(5);
stack.addLast(10);
stack.addLast(-1);
// ...és onnan is vesszük ki
System.out.println(stack.removeLast()); // -1
System.out.println(stack.removeLast()); // 10

// Ugyanaz az osztály, de a Queue interface-en keresztül használjuk
Queue<Integer> queue = new ArrayDeque<>();
queue.add(5);
queue.add(10);
queue.add(-1);
System.out.println(queue.remove()); // 5
System.out.println(queue.remove()); // 10

Queue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(10);
pq.add(-1);
System.out.println(pq.remove()); // 5
System.out.println(pq.remove()); // 10

Set<Integer> s = new HashSet<>();
s.add(5);
s.add(1);
s.add(11);
s.add(5);   // false visszatérési értékkel jelez, hogy már benne van
System.out.println(s.size());        // 3
System.out.println(s.contains(2));   // false
System.out.println(s.contains(5));   // true

Map<String, Double> d = new HashMap<>();
d.put("Gyurika", 5.6);
d.put("Petike", -8.7);
System.out.println(d.containsKey("Csőrike"));  // hamis
System.out.println(d.get("Petike"));           // -8.7
System.out.println(d.get("Csőrike"));          // null

PHP

A PHP csak korlátozottan taralmaz dedikált adatszerkezeteket, amelyekkel a műveletek megvalósíthatók.

A tömbhöz azonban rengeteg segédfüggvény jár, amivel a verem/sor megoldható:

$stack = [];
$stack[] = 5;  // push művelet
$stack[] = 10;
$stack[] = -1;
print( array_pop($stack) ); // -1
print( array_pop($stack) ); // 10

$queue = [];
$queue[] = 5;  // enqueue művelet, ua. mint fent
$queue[] = 10;
$queue[] = -1;
print( array_shift($queue) ); // 5  - az elejéről veszi le, azaz dequeue
print( array_shift($queue) ); // 10

A PHP-s prioritási sor “fordítva” működik, először a legnagyobb értéket veszi ki. Itt is meg lehet adni különböző prioritást az elemhez képest:

$pq = new SplPriorityQueue();
$pq->insert(5, 5);
$pq->insert(10, 10);
$pq->insert(-1, -1);
print( $pq->extract() ); // 10 (legnagyobb)
print( $pq->extract() ); // 5

Ha az elemeink, kulcsaink egész vagy string típusúak, akkor a tömbből akár halmaz és szótár is lehet.

$set = [];
$set[5] = true;            // Hozzáadás a halmazhoz
$set[1] = true;
$set[11] = true;
$set[5];                   // Duplán hozzáadás sem gond
print( count($set) );      // 3
print( isset($set[2]) );   // false
print( isset($set[5]) );   // true
unset($set[11]);           // Törlés

$dict = [];
$dict["Gyurika"] = 5.6;            // Hozzáadás a szótárhoz
$dict["Petike"] = -8.7;
print( isset($dict["Csőrike"]) );  // hamis
print( $dict["Petike"] );          // -8.7
print( $dict["Csőrike"] );         // Notice: Undefined index: Csőrike
unset($dict["Petike"]);            // Törlés

Mivel egy tömb kulcsa csak egész szám vagy szöveg lehet, ez a módszer más típusokra nem működik. Ha halmaz elem, vagy a szótár kulcsa objektum, használhatjuk még az SplObjectStorage osztályt.