Absztrakt adatszerkezetek

Az „absztrakt” szó arra utal, hogy nem azt adjuk meg, hogy hogy lesz tárolva, hanem csak azt, hogy milyen viselkedést várunk el tőle.

verem (stack, stivă):

absztrakt adatszerkezet, elemeket tárol,
műveletek:
- elem betevése
- elem törlése
- melyik elem van a tetején?
viselkedés: LIFO sorrendben történnek (last in, first out) == amelyik elem legutóbb került be, azt fogjuk először kivenni

sor (queue, coadă)

absztrakt adatszerkezet, elemeket tárol,
műveletek:
- elem betevése
- elem törlése
- melyik lenne a következő kivett elem?
viselkedés: FIFO sorrendben történnek (first in, first out) == amelyik elem legrégebben került be, azt fogjuk először kivenni

Verem implementálása tömbbel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// a végére teszünk be és a végéről
// törlünk

// * * * * * _ _ _ _ _
//           ^ide jön be az új
#include <iostream>
using namespace std;

struct Verem
{
    int elemek[1000];
    int n;
};

// inicializál (létrehoz egy üres vermet)
void init(Verem &v)
{
    v.n = 0;
}

// betesz egy elemet a verem végére
void push(Verem &v, int ertek)
{
    v.elemek[v.n] = ertek;
    v.n++;
}

// kivesz egy elemet a verem végéről
int pop(Verem &v)
{
    if (v.n == 0) {
        cout << "hiba";
        return 0;
    }

    int ertek = v.elemek[v.n - 1];
    v.n--;
    return ertek;
}

// visszatéríti a tetején levő elemet (de nem veszi ki)
int top(Verem &v)
{
    if (v.n == 0) {
        cout << "hiba";
        return 0;
    }

    return v.elemek[v.n - 1];
}

int main ()
{
    Verem x;
    init(x);

    push(x, 10);
    push(x, 20);
    push(x, 30);

    cout << top(x) << endl; // 30
    cout << pop(x) << endl; // 30
    cout << pop(x) << endl; // 20
    cout << pop(x) << endl; // 10

    return 0;
}

Sor implementálása tömbbel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;

struct Sor
{
    int elemek[1000];
    int bal, jobb;
};

void init(Sor &s)
{
    s.bal = 0;
    s.jobb = -1;
}

void push(Sor &s, int ertek)
{
    s.jobb++;
    s.elemek[s.jobb] = ertek;
}

int pop(Sor &s)
{
    if (s.bal > s.jobb) {
        cout << "hiba";
        return 0;
    }

    s.bal++;
    return s.elemek[s.bal-1];
}


int main ()
{
    Sor s;
    init(s);

    push(s, 10);
    push(s, 20);
    push(s, 30);

    cout << pop(s) << endl; // 10
    cout << pop(s) << endl; // 20
    cout << pop(s) << endl; // 30

    // pop(s); // hiba

    return 0;
}

Feladatok (kézzel megoldható):

Adott egy kezdetben üres verem és az alábbi műveletek. Milyen elemek lesznek a végén a veremben?

    push 2  -> 2
    push 3  -> 2 3
    push 4  -> 2 3 4
    pop     -> 2 3
    pop     -> 2
    push 6  -> 2 6
    pop     -> 2
    push 7  -> 2 7
    push 8  -> 2 7 8
    pop     -> 2 7
    pop     -> 2
    pop     ->
    push 9  -> 9
    push 10 -> 9 10
    pop     -> 9
    push 11 -> 9 11

Az előző feladathoz hasonlóan, verem helyett sorral:

    push 2  -> 2
    push 3  -> 2 3
    push 4  -> 2 3 4
    pop     -> 3 4
    pop     -> 4
    push 6  -> 4 6
    pop     -> 6
    push 7  -> 6 7
    push 8  -> 6 7 8
    pop     -> 7 8
    pop     -> 8
    pop     ->
    push 9  -> 9
    push 10 -> 9 10
    pop     -> 10
    push 11 -> 10 11