/*
    Absztrakt adattípusok

    "absztrakt" - nem érdekel feltétlenül az,
    hogy hogy van tárolva, csak az, hogy
    milyen műveleteket lehet vele végezni


    1. Várakozási sor / sor / Queue / Coadă

        - lehet betenni elemet (PUSH)
        - meg lehet kérdezni, hogy üres-e
        - lehet kivenni elemet (POP)
        - meg lehet nézni, hogy ki az "első"
          (kit vennénk ki)

        Egy kivevés azt az elemet veszi ki,
        amelyik a legrégebben volt beletéve.
        (FIFO sorrend - First In, First Out)

        Pl.
            sor <- {}
            push(3)
            push(2)
            kiír pop()
            push(1)
            kiír pop()

            kimenet: 3 2

    2. Verem / Stack / Stivă

        - lehet betenni elemet (PUSH)
        - meg lehet kérdezni, hogy üres-e
        - lehet kivenni elemet (POP)
        - meg lehet nézni, hogy ki az "felső"
          (kit vennénk ki)

        Egy kivevés azt az elemet veszi ki,
        amelyik a legutóbb volt beletéve.
        (LIFO sorrend - Last In, First Out)

        Pl.
            verem <- {}
            push(3)
            push(2)
            kiír pop()
            push(1)
            kiír pop()

            kimenet: 2 1

    Feladatok érettségiből:
        2009 var 14, II.2.

            10 5 4
                pop
            10 5
                push(7)
            10 5 7
                pop
            10 5
                pop
            10
                push(9)
            10 9

        2009 var 41, II.2.
            push 3; push 7; pop; push 5; push 1

            {}
            3
            3  7
            3
            3 5
            3 5 1   -> megoldás: 1

        Ugyanez sorral: (Melyik elem van a sor elején?)
            3
            3 7
            7
            7 5
            7 5 1   -> megoldás: 7


    Verem implementálása statikusan (tömbbel)

           n:  0
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  _  _  _  _  _  _  _  _  _  _


        push(10)

           n:  1
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  10 _  _  _  _  _  _  _  _  _

        push(4)


           n:  2
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  10 4  _  _  _  _  _  _  _  _


        pop -> t[n-1]
               és n--


        push(7)

           n:  2
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  10 7  _  _  _  _  _  _  _  _


        HF. implementálni


    Sor implementálása statikusan (tömbbel)

        bal:   0
        jobb:  -1
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  _  _  _  _  _  _  _  _  _  _


        push(5)

        bal:   0
        jobb:  0
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  5  _  _  _  _  _  _  _  _  _


        push(6)

        bal:   0
        jobb:  1
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  5  6  _  _  _  _  _  _  _  _


        push(7)

        bal:   0
        jobb:  2
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  5  6  7  _  _  _  _  _  _  _


        pop -->  t[bal]
                és bal++

         bal:  1
        jobb:  2
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  5  6  7  _  _  _  _  _  _  _


        push(8)

         bal:  1
        jobb:  3
           i:  0  1  2  3  4  5  6  7  8  9
        t[i]:  5  6  7  8  _  _  _  _  _  _


        pop -->  t[bal]
                és bal++

        HF. implementálni
*/


// Sor implementálása statikusan (megoldva):
/*
#include <iostream>
using namespace std;

struct Sor
{
    int t[100];
    int bal = 0;
    int jobb = -1;
};

void betesz(Sor &s, int elem)
{
    ++s.jobb;
    s.t[s.jobb] = elem;
}

int kivesz(Sor &s)
{
    int elem = s.t[s.bal];
    s.bal++;
    return elem;
}

int megnez(Sor &s)
{
    return s.t[s.bal];
}

int meret(Sor &s)
{
    return s.jobb - s.bal + 1;
}

int main()
{
    Sor s;
    betesz(s, 120);
    betesz(s, 121);
    betesz(s, 122);
    cout << kivesz(s) << endl;
    cout << kivesz(s) << endl;
    betesz(s, 5);
    betesz(s, 6);
    cout << kivesz(s) << endl;
    cout << kivesz(s) << endl;

    return 0;
}
*/


// Verem implementálása statikusan (megoldva):
/*
#include <iostream>
using namespace std;

struct Verem
{
    int t[100];
    int n = 0;
};

void betesz(Verem &v, int elem)
{
    v.t[v.n] = elem;
    v.n++;
}

int kivesz(Verem &v)
{
    v.n--;
    return v.t[v.n];
}

int megnez(Verem &v)
{
    return v.t[v.n-1];
}

int meret(Verem &v)
{
    return v.n;
}


int main()
{
    Verem v;

    betesz(v, 120);
    betesz(v, 121);
    betesz(v, 122);
    cout << kivesz(v) << endl; // 122
    cout << kivesz(v) << endl; // 121
    betesz(v, 5);
    betesz(v, 6);
    cout << kivesz(v) << endl; // 6
    cout << kivesz(v) << endl; // 5

    return 0;
}
*/


/*
    Verem implementálása dinamikusan
    (láncolással / egyszeresen láncolt listával)

    - az elejére teszünk be és onnan veszünk ki
*/
/*
#include <iostream>
using namespace std;

struct Elem
{
    int adat;
    Elem *next;
};

struct Verem
{
    Elem *fej = nullptr;
};


void betesz(Verem &v, int e)
{
    Elem *uj = new Elem;
    uj->adat = e;
    uj->next = v.fej;

    v.fej = uj;
}

int kivesz(Verem &v)
{
    int eredmeny = v.fej->adat;
    Elem *torolni = v.fej;

    v.fej = v.fej->next;

    delete torolni;
    return eredmeny;
}

int megnez(Verem &v)
{
    return v.fej->adat;
}

bool ures_e(Verem &v)
{
    return v.fej == nullptr;
}

int main()
{
    Verem v;

    betesz(v, 1);
    betesz(v, 2);
    betesz(v, 3);
    kivesz(v);
    kivesz(v);
    kivesz(v);

    betesz(v, 120);
    betesz(v, 121);
    betesz(v, 122);
    cout << kivesz(v) << endl; // 122
    cout << kivesz(v) << endl; // 121
    betesz(v, 5);
    betesz(v, 6);
    cout << kivesz(v) << endl; // 6
    cout << kivesz(v) << endl; // 5

    return 0;
}
*/


/*
    Sor implementálása dinamikusan
    (láncolással / egyszeresen láncolt listával)


    - a végére teszünk be és az elejéről veszünk ki
*/
#include <iostream>
using namespace std;

struct Elem
{
    int adat;
    Elem *next;
};

struct Sor
{
    Elem* fej = nullptr;
    Elem* veg = nullptr;
};

void betesz(Sor &s, int e)
{
    if (s.fej == nullptr) {
        Elem *uj = new Elem;
        uj->adat = e;
        uj->next = nullptr;

        s.fej = s.veg = uj;
    }
    else {
        Elem *uj = new Elem;
        uj->adat = e;
        uj->next = nullptr;

        s.veg->next = uj;
        s.veg = uj;
    }
}

int kivesz(Sor &s)
{
    int eredmeny = s.fej->adat;
    Elem *torolni = s.fej;

    s.fej = s.fej->next;
    if (s.fej == nullptr)
        s.veg = nullptr;

    delete torolni;
    return eredmeny;
}

int megnez(Sor &s)
{
    return s.fej->adat;
}

bool ures_e(Sor &s)
{
    return s.fej == nullptr;
}

int main()
{
    Sor s;
    // kivesz(s); - run-time hiba

    betesz(s, 120);
    betesz(s, 121);
    betesz(s, 122);
    cout << kivesz(s) << endl; // 120
    cout << kivesz(s) << endl; // 121
    betesz(s, 5);
    betesz(s, 6);
    cout << kivesz(s) << endl; // 122
    cout << kivesz(s) << endl; // 5

    return 0;
}