#include <iostream>
#include<string>

using namespace std;

template<typename Tip>
class Lista;
template <typename Tip>
class Iterator;




template<typename Tip>
class Stek
{
    Tip *Elementi;
    int kapacitet;
    int _vrh;
    int brEl; //uvela sam dodatnu varijablu, koja ce mi sluziti kao brojac elemenata

public:
    Stek():kapacitet(10), _vrh(-1), brEl(0)
    {
        Elementi=new Tip[kapacitet];
    }

    ~Stek()
    {
        delete[] Elementi;
        brEl=0;
    }

    Stek(const Stek&s)
    {
        kapacitet=s.kapacitet;
        _vrh=s._vrh;
        brEl=s.brEl;
        Elementi=new Tip[kapacitet];
        for (int i=0; i<_vrh; i++)
            Elementi[i]=s.Elementi[i];
    }

    void operator=(const Stek &s)
    {

        delete[] Elementi;
        kapacitet=s.kapacitet;
        _vrh=s._vrh;
        brEl=s.brEl;

        for (int i=0; i<_vrh; i++)
            Elementi[i]=s.Elementi[i];
    }



    void brisi()
    {
        _vrh=-1;
        brEl=0;
    }

    void stavi(const Tip& el)
    {
        if (_vrh==kapacitet-1) throw "Stek je pun.";
        Elementi[++_vrh]=el;
        brEl++;
    }

    Tip skini()
    {
        if (_vrh==-1) throw "Stek je prazan.";
        brEl--;
        return Elementi[_vrh--];

    }

    Tip &vrh()
    {
        if (_vrh==-1) throw "Stek je prazan.";
        return Elementi[_vrh];
    }

    int brojElemenata()
    {
        if (_vrh==-1)
        {
            int i=0;
            return i;
        }
        else if (_vrh==kapacitet-1) return _vrh;
        else return _vrh+1;
    }


    int brojEl()
    {
        return brEl;

    }

    void obrni()
    {
        Stek<Tip>s;
        Stek<Tip>s1;
        s1=*this;

        for(int i=s.brojEl(); i>=0; i--)
        {
            s.stavi(s1.skini());
        }

        *this=s;

    }

};

template<typename Tip>
class Red
{
    int kapacitet;
    int pocetak;
    int kraj;
    int brEl;//uvela sam dodatnu varijablu, koja ce mi sluziti kao brojac elemenata

    Tip *Elementi;

public:

    Red(): kapacitet(10), pocetak(-1), kraj(-1), brEl(0)
    {
        Elementi= new Tip[kapacitet];
    }

    ~Red()
    {
        delete[] Elementi;
        brEl=0;
    }

    Red (const Red &r)
    {   brEl=r.brEl;
        kapacitet=r.kapacitet;
        pocetak=r.pocetak;
        kraj=r.kraj;
        Elementi=new Tip[kapacitet];
        for (int i=pocetak; i<kraj; i++)
            Elementi[i]=r.Elementi[i];
    }

    void operator=(const Red &r)
    {
        delete[] Elementi;
        brEl=r.brEl;
        kapacitet=r.kapacitet;
        pocetak=r.pocetak;
        kraj=r.kraj;
        Elementi=new Tip[kapacitet];
        for (int i=pocetak; i<kraj; i++)
            Elementi[i]=r.Elementi[i];
    }

    void brisi()
    {
        pocetak=-1;
        kraj=-1;
        brEl=0;
    }

    void stavi(const Tip &el)
    {
        if (pocetak==(kraj+1)%kapacitet) throw "Red je pun.";

        kraj=(kraj+1)%kapacitet;
        Elementi[kraj]=el;
        if (pocetak==-1) pocetak=0;
        brEl++;
    }

    Tip skini()
    {

        if (pocetak==-1 && kraj==-1) throw "Red je prazan.";
        Tip x(Elementi[pocetak]);
        if(pocetak==kraj) pocetak=kraj=-1;
        else pocetak=(pocetak+1)%kapacitet;
        brEl--;
        return x;
    }

    Tip &celo()
    {
        if (pocetak==-1 && kraj==-1) throw "Red je prazan.";
        return Elementi[pocetak];
    }


    int brojElemenata()
    {

        if (pocetak==-1 && kraj==-1)
        {
            int i(0);
            return i;
        }
        else if (pocetak==(kraj+1)%kapacitet)
        {
            return kapacitet;
        }
        else
        {
            return ((kraj+1+kapacitet)-pocetak)%kapacitet;
        }
    }

    int brojEl()
    {
        return brEl;

    }

    void sortiraj()
    {

        for(int i=pocetak; i<=kraj; i++)
        {

            for(int j=i; j<=kraj; j++)
            {
                if(Elementi[i]<Elementi[j])
                {
                    Tip pom=Elementi[i];
                    Elementi[i]=Elementi[j];
                    Elementi[j]=pom;
                }
            }
        }
    }
};


//Zadatak 1

bool provjeri_zagrade(string tekst)
{

    Stek<char> s1;
    for (int i=0; i<int(tekst.size()); i++)
    {
        if (tekst[i]=='(' || tekst[i]=='[' || tekst[i]=='{') s1.stavi(tekst[i]);


        if (tekst[i]==')' )
        {
            if (s1.vrh()=='(' )
            {
                s1.skini();

            }
            else
            {
                return false;
            }
        }

        if (tekst[i]==']' )
        {
            if (s1.vrh()=='[' )
            {
                s1.skini();

            }
            else
            {
                return false;
            }
        }

        if (tekst[i]=='}')
        {
            if (s1.vrh()=='{' )
            {
                s1.skini();

            }
            else return false;

        }
    }
    if(s1.brojElemenata()!=0) return false;


    return true;
}


//Zadatak2
class StampacServer
{

    Red<string> s,r,_p;

public:

    enum Prioritet {Sef, Radnik, Pripravnik};

    void posaljiDokument(Prioritet p, string sadrzaj)
    {

        if(p<0 || p>2) throw "Ne postoji prioritet koji ste naveli.";
        if(p==0) s.stavi(sadrzaj);
        if(p==1) r.stavi(sadrzaj);
        if(p==2) _p.stavi(sadrzaj);

    }
    string dajDokument()
    {

        if(s.brojElemenata()!=0) return s.skini();
        else if(r.brojElemenata()!=0)  return r.skini();
        else if(_p.brojElemenata()!=0) return _p.skini();
        else return "";


    }
};


//Zadatak3
template<typename Tip>
int presjek(Stek<Tip> s1, Stek<Tip> s2)
{
    int brojac(0);
    while(s1.brojElemenata()!=0 && s2.brojElemenata()!=0)  {

            if(s1.vrh()==s2.vrh())
            {
                brojac++;
                s1.skini();
                s2.skini();
            }

            else if(s1.vrh()<s2.vrh())
            {

                while(s1.vrh()<s2.vrh())
                {
                    s1.skini();
                }
            }

            else
            {
                while(s2.vrh()<s1.vrh())
                {
                    s2.skini();
                }
            }
        }

    return brojac;
}


template <typename Tip>
class Iterator
{

    const Lista<Tip> *lista;

    typename Lista<Tip>::Cvor *trenutniLista;
     typename Lista<Tip>::Cvor *trenutniListaSKraja; //uvodim ovaj atribut zbog fje palindrom

public:


    Iterator(const Lista<Tip> &l) : lista(&l), trenutniLista(l.p), trenutniListaSKraja(l.poslj) {}

    Tip trenutni()
    {

        if (lista==0) throw "Lista je prazna.";

        else return trenutniLista->element;
    }


    Tip prethodni()
    {

        if (lista==0) throw "Lista je prazna.";
        typename Lista<Tip>::Cvor *novi(trenutniLista);
        while(novi->_sljedeci!=trenutniLista)
        {
            novi=novi->_sljedeci;
        }

        //trenutniLista=novi;

        return trenutniLista->element;


    }

    Tip sljedeci()
    {

        if (lista==0 ) throw "Lista je prazna.";

        else
        {
            trenutniLista=trenutniLista->_sljedeci;
            return trenutniLista->element;
        }
    }

    Tip pocetak()
    {

        if (lista==0) throw "Lista je prazna.";

            trenutniLista=trenutniLista.p;
            return trenutniLista->element;

    }

    Tip kraj()
    {

        if (lista==0) throw "Lista je prazna.";

        else
        {
            trenutniLista=trenutniLista.poslj;
            return trenutniLista->element;
        }
    }


    //uvodim ove metode zbog fje palindrom
    const Tip& trenutnisKraja()
    {
        if(lista->brojElemenata()==0) throw "Lista je prazna.";
        else return trenutniListaSKraja->element;

    }


    bool prethodniSKraja() {

    typename Lista<Tip>::Cvor *pr(lista->p);
    while(pr->_sljedeci!= trenutniListaSKraja) pr=pr->_sljedeci;
    trenutniListaSKraja=pr;
    return true;
    }

};

template<typename Tip>
class Lista
{

    struct Cvor //izmjena naziva struktura iz Clan u Cvor i Clan* veza u Cvor* _sljedeci, zbog prilagodjavanja imena i funkcije koju obavlja Cvor sljedeci, cisto radi lakse orjentacije
    {
        Tip element;
        Cvor *_sljedeci;
        Cvor(const Tip &element, Cvor *_sljedeci):element(element),_sljedeci(_sljedeci){}
    };
    Cvor* p; //pocetni
    Cvor* tr; //trenutni
    Cvor *poslj;// posljednji
    int br; // ukupan broj cvorova


public:
    Lista() :p(0), tr(0), poslj(0), br(0) {} //atributi su bili implementirani unutar zagrada, pa sam ih prebacila u konstruktorsku inicijalizacijsku listu

   virtual ~Lista()
    {tr=p;

        if (br==1)obrisi();//dodat uvjet
        else
        {
            while (br!=0)
            {
                obrisi();
            }
        }
        p=poslj=tr=0;

    }


    Lista(const Lista &a)
    {

        p= new Cvor;
        p->element=a.p->element;

        Cvor *temp=p;
        Cvor *temp1=a.p;
        int i(1);
        for(;;)
        {
            p->sljedeci=new Cvor;
            p=p->sljedeci;
            p->element=a[i];
            i++;
            if(a.tr==temp1) tr=p;
            if(temp1->sljedeci==0){
            p->sljedeci=0;
            poslj=p;
            break;

            }
        }
    }


    Lista &operator=(Lista &a)
    {
        Cvor *tem=p;
        while (tem->_sljedeci!=0)
        {
            tem=tem->_sljedeci;
            delete p;
            p=tem;
        }
        delete tem;
        p=tr=poslj=0;

        p= new Cvor;
        p->element=a.p->element;

        Cvor *temp=p;
        Cvor *temp1=a.p;
        int i(1);
        for(;;)
        {
            p->sljedeci=new Cvor;
            p=p->sljedeci;
            p->element=a[i];
            i++;
            if(a.tr==temp1) tr=p;
            if(temp1->sljedeci==0){
            p->sljedeci=0;
            poslj=p;
            break;

            }
        }

        return *this;
    }

    int brojElemenata()
    {
        return br;
    }

    Tip trenutni() const
    {
        if (br==0) throw "Lista  je prazna.";
        return tr->element;
    }

    bool prethodni()
    {
        if (br==0) return false;
        Cvor *novi=p;
        while (novi->_sljedeci!=tr)
        {
            novi=novi->_sljedeci;
        }
        tr=novi;
        return true;
    }


    bool sljedeci()
    {
        if (tr==poslj) return false;
        tr=tr->_sljedeci;
        return true;
    }

    void pocetak()
    {
        tr=p;
    }

    void kraj()
    {

        tr=poslj; //Obzirom da sam naknadno dodala varijablu posljednji, promjenila sam i ovu metodu u odnosu kakvu sam je poslala kao pripremu za tutorijal 2.
    }

    void obrisi()
    {
        if (br==0)throw "Nema elemenata za brisanje!";
    else
    {
        if (tr==p)
        {
            if (br==1)
            {
                //izmjenjeno jer nije radilo brisanje liste s jednim elementom
                delete tr;
                tr=0;
                p=0;
                poslj=0;
                br--;
            }
            else
            {
                p=p->_sljedeci;
                delete tr;
                tr=p;
                br--;
            }

        }
        else
        {
            if (tr==poslj)
            {
                if (br==1)
                {
                    delete tr;
                    tr=0;
                    p=0;
                    poslj=0;
                    br--;
                }
                else
                {
                    Cvor *k(tr);
                    prethodni();
                    poslj=tr;
                    delete k;
                    br--;
                }
            }
            else
            {
                Cvor *pom(tr->_sljedeci);
                Cvor *k(tr);
                prethodni();
                delete k;
                tr->_sljedeci=pom;
                sljedeci();
                br--;

            }
        }
    }
    }


    void dodajIza(const Tip &el)
    {
        Cvor* novi=new Cvor(0,0);
        novi->element=el;
        novi->_sljedeci=0;
        if (br==0)
        {
            poslj=tr=novi;
        }
        else
        {
            novi->_sljedeci=tr->_sljedeci;
            tr->_sljedeci=novi;
        }
        br++;
    }

    void dodajIspred(const Tip &el)
    {
        if (br==0)
        {
            p=new Cvor(0,0);
            p->element=el;
            p->_sljedeci=0;
            tr=p;
            br++;
            return;
        }

        if (tr==p)
        {
            Cvor* novi=new Cvor(0,0);
            novi->_sljedeci=p;
            novi->element=el;
            p=novi;
            br++;
            return;
        }
        prethodni();
        dodajIza(el);
        sljedeci();
        sljedeci();
    }

    Tip &operator [](int n)
    {
        if (n<0 || n>br) throw "Ne postoji taj clan niza.";
        Cvor* temp(p);
        for (int i=0; i<n; i++)
        {
            temp=temp->_sljedeci;
        }
        return temp->element;
    }

void Ispisi()const
{
    Cvor *pom(p);
    int i(0);
    cout<<"Sadrzaj liste:\n";
    while (pom!=0)
    {
        cout<<i<<":"<<p->element;
        if (pom==p)cout<<"<-pocetak";
        if (pom==tr)cout<<"<-teku,"<<i+1<<".";
        if (pom==poslj)cout<<"<-kraj";
        cout<<endl;
        i++;
        pom=pom->_sljedeci;
    }
}
};

//Zadatak4
/*bool palindrom(const Lista<char>& rijec){


int brojac(0);
Stek <char> pola_rijeci;
Iterator<char> cijela_rijec(rijec);
int pola =rijec.brojElemenata();
for(int i=brojac; i<pola/2; i++)
{
    pola_rijeci.stavi(cijela_rijec.trenutni());
    brojac++;
    cijela_rijec.sljedeci();
}

if(pola%2==0)
{
    for(int i=brojac; i<rijec.brojElemenata(); i++)
    {
        if(pola_rijeci.skini()!=cijela_rijec.trenutni()) return false;

        cijela_rijec.sljedeci();
    }

}

else {
        brojac++;
        cijela_rijec.sljedeci();
        for(int i=brojac; i<rijec.brojElemenata(); i++)
    {
        if(pola_rijeci.skini()!=cijela_rijec.trenutni()) return false;

        cijela_rijec.sljedeci();
    }

}*/


bool palindrom( Lista<char>& rijec){

    Iterator<char> i(rijec);
    i.pocetak();
    int pola =(rijec.brojElemenata())/2;

    while(pola!=0)
    {

        char c1=i.trenutni();
        char c2=i.trenutnisKraja();
        if(c1!=c2) return false;
        i.sljedeci();
        i.prethodniSKraja();
        pola--;

    }


return true;

}


int main()
{



    try
    {

        Stek<int>s;



       /* int b;
        b=provjeri_zagrade("{()}");
        cout<<b;*/


      /*  for (int i(1); i<=5; i++)
        s.stavi(i);

        s.obrni();

        for (int j(1); j<=5; j++)
        cout<<s.skini();
        /*int a;
        a=presjek(s1,s2);
        cout<<presjek(s1,s2)<<endl;*/


    }

    catch (const char greska[])
    {
        cout << greska;
    }
    catch (...)
    {
        cout << "\nGreska u programu";
    }

    return 0;
}