#include<iostream>
#include <conio.h>
#include<string>
#include<iomanip>
using namespace std;


struct dane {
    string nazwisko;
    string imie;
    int wynik;
};
typedef struct rob {
    dane element;
    struct rob * nastepny;
} elem;
typedef struct {
    elem * glowa;
    elem * ogon;
} wskaznik;
wskaznik wsk;


void podaj_dane(dane  & element)

{
    cout <<"podaj nazwisko ";
    cin >> element.nazwisko;
    cout << "\n";
    cout << "podaj imie ";
    cin >> element.imie;
    cout << "\n";
    cout << "podaj wynik ";
    cin >> element.wynik;
    cout << "\n";
}
void wypisz_dane(dane element)

{
    cout <<left<< setw( 12)<<element.nazwisko;
    cout << "\t";
    cout << left<< setw( 10)<<element.imie;
    cout << "\t";
    cout << element.wynik;
    cout << "\n";
}
void doloz_do_listy( dane element) {
    dane el;
    podaj_dane( el);
    elem  * q=new(elem);
    q->element=el;
    q->nastepny=NULL;
    if (wsk.glowa==NULL) wsk.glowa=wsk.ogon=q;
    else {
        wsk.ogon->nastepny=q;
        wsk.ogon=q;
    }
}
void wstaw_do_kolejki( dane element) {
    dane el;
    podaj_dane( el);
    elem  * q=new(elem);
    q->element=el;
    q->nastepny=NULL;
    if (wsk.glowa==NULL) wsk.glowa=wsk.ogon=q;
    else {
        wsk.ogon->nastepny=q;
        wsk.ogon=q;
    }
}

void poloz_na_stos( dane & element) {
    dane el;
    elem  *p;
    p=wsk.glowa;
    podaj_dane( el);
    elem  * q=new(elem);
    if(wsk.glowa==NULL)wsk.glowa=wsk.ogon=q;
    q->element=el;
    q->nastepny=p;
    wsk.glowa=q;
}

void zdejmij_ze_stosu( dane & element) {
    elem  * q;
    dane el;
    el=wsk.glowa->element;
    q=wsk.glowa;
    wsk.glowa=q->nastepny;
    delete(q);
    cout<<"zdjeto ze stosu "<<"\n";
    wypisz_dane(el);
}
void usun_z_kolejki( dane & element) {
    elem  * q, * p;
    dane el;
    el=wsk.glowa->element;
    p=wsk.glowa->nastepny;
    q=wsk.glowa;
    wsk.glowa=p;
    delete(q);
    cout<<"usunieto z kolejki "<<"\n";
    wypisz_dane(el);
}
void wypisz_liste() {
    dane el;
    elem  * q=wsk.glowa;
    cout << "oto aktualny stan"<<"\n";
    if (wsk.glowa==NULL) cout << "lista pusta"<<"\n";
    else
        while(q!=NULL) {
            el=q->element;
            wypisz_dane(el);
            q=q->nastepny;
        }
}
int oblicz_rozmiar() {
    int roz=0;
    elem * q=wsk.glowa;
    if (wsk.glowa==NULL) roz=0;
    else
        while (q!=NULL) {
            roz=roz+1;
            q=q->nastepny;
        }
    return roz;
}
void wstaw_do_listy_za() {
    int k;
    do {
        cout<<"podaj nr elementu za który wstawic element"<<"\n";
        cin >>k;
    } while(oblicz_rozmiar()<k);
    dane el;
    podaj_dane(el);
    int j=0;
    elem * q=new(elem);
    elem * p=wsk.glowa;
    q->element=el;
    if (oblicz_rozmiar()==0) {
        wsk.glowa=q;
        wsk.ogon=q;
        q->nastepny=NULL;
    } else {
        if (k==1) {
            q->nastepny=p->nastepny;
            p->nastepny=q;
        } else if ((oblicz_rozmiar()==k) && (k!=0)) {
            p=wsk.ogon;
            p->nastepny=q;
            q->nastepny=NULL;
            wsk.ogon=q;
        } else {
            p=wsk.glowa;
            j=2;
            p=p->nastepny;
            while (j<k) {
                j=j+1;
                p=p->nastepny;
            }
            q->nastepny=p->nastepny;
            p->nastepny=q;
        }
    }
}


void wstaw_do_listy_kolejny() {
    dane el;
    podaj_dane(el);
    elem *q=new(elem);
    q->element=el;
    if (wsk.glowa==NULL) {
        wsk.glowa=wsk.ogon=q;
        q->nastepny=NULL;
    } else {
        elem *przed=NULL,*po=wsk.glowa;
        enum {SZUKAJ,ZAKONCZ} stan=SZUKAJ;
        while ((stan==SZUKAJ) && (po!=NULL))
            if (po->element.wynik>=el.wynik)
                stan=ZAKONCZ;
            else {
                przed=po;
                po=po->nastepny;
            }
        if (przed==NULL) {
            wsk.glowa=q;
            q->nastepny=po;
        } else if (po==NULL) {
            wsk.ogon->nastepny=q;
            q->nastepny=NULL;
            wsk.ogon=q;
        } else {
            przed->nastepny=q;
            q->nastepny=po;
        }
    }
}

void wstaw_do_listy_na_koniec() { // dolaczamy rekord na koniec listy
    dane el;

    elem *q=new(elem);
    podaj_dane(el);
    q->element=el;
    q->nastepny=NULL;

    if (wsk.glowa==NULL)       // lista pusta
        wsk.glowa=wsk.ogon=q;
    else {               // coœ jest w liscie
        (wsk.ogon)->nastepny=q;
        wsk.ogon=q;
    }
}

void usun_z_listy_pierwszy( dane & element) {
    elem  * q, * p;
    dane el;
    el=wsk.glowa->element;
    p=wsk.glowa->nastepny;
    q=wsk.glowa;
    wsk.glowa=p;
    delete(q);
    cout<<"usunieto z listy "<<"\n";
    wypisz_dane(el);
}




void wypisz_opcje_menu_stosu() {
    cout<<"Opcje stosu \n";
    cout<<"1.Poloz na stos element \n";
    cout<<"2.Zdejmij ze stosu element \n";
    cout<<"3.Wypisz stos \n";
    cout<<"4.Oblicz rozmiar stosu \n";
    cout<<"5.Wyjscie \n";
}
void wypisz_opcje_menu_kolejki() {
    cout<<"Opcje stosu \n";
    cout<<"1.Dolacz dokolejki element \n";
    cout<<"2.Usun z kolejki element \n";
    cout<<"3.Wypisz kolejke \n";
    cout<<"4.Oblicz rozmiar kolejki \n";
    cout<<"5.Wyjscie \n";
}


void wypisz_opcje_menu_lista() {
    cout<<"Opcje listy \n";
    cout<<"1.Dolacz do listy element na koniec \n";
    cout<<"2.Usun z listy element pierwszy \n";
    cout<<"3.Wypisz liste \n";
    cout<<"4.Oblicz rozmiar listy \n";
    cout<<"5. Wstaw do listy za\n";
    cout<<"6. Wstaw do listy w kolejnoœci wyniku \n";
    cout<<"7.Wyjscie \n";
}
void wypisz_opcje_menu() {
    cout<<"Struktury listowe \n";
    cout<<"1.Stosy \n";
    cout<<"2.Kolejki \n";
    cout<<"3.Listy \n";
    cout<<"4.koniec \n";
}
int main() {
    int k,n,opc;
    wskaznik wsk;
    dane element;
    char opcja;
    bool koniec=true;
    while(1) {
        koniec=true;
        wypisz_opcje_menu();

        cin>>opc;

        switch(opc) {

        case 1:
            while(koniec)

            {
                wypisz_opcje_menu_stosu();
                cin>>opcja;
                switch(opcja) {
                case '1':
                    cout<<"Podaj liczbe elemantow \n";
                    cin>>n;
                    for (int i=1; i<=n; i++) poloz_na_stos(element);
                    break;
                case '2':
                    zdejmij_ze_stosu(element);
                    break;

                case '3':
                    wypisz_liste();
                    break;
                case '4':
                    cout<<"rozmiar stosu "<<oblicz_rozmiar()<<" \n";
                    break;

                case '5':
                    koniec=false;
                    break;
                }

            }

            break;

        case 2:
            while(koniec) {
                wypisz_opcje_menu_kolejki();
                cin>>opcja;
                switch(opcja) {
                case '1':
                    cout<<"Podaj liczbe elemantow \n";
                    cin>>n;
                    for (int i=1; i<=n; i++) wstaw_do_kolejki(element);
                    break;
                case '2':
                    usun_z_kolejki(element);
                    break;

                case '3':
                    wypisz_liste();
                    break;
                case '4':
                    cout<<"rozmiar kolejki "<<oblicz_rozmiar()<<" \n";
                    break;

                case '5':
                    koniec=false;
                    break;
                }
            }
            break;
        case 3:
            while(koniec) {
                wypisz_opcje_menu_lista();
                cin>>opcja;
                switch(opcja) {
                case '1':
                    cout<<"Podaj liczbe elemantow \n";
                    cin>>n;
                    for (int i=1; i<=n; i++) wstaw_do_listy_na_koniec();
                    break;
                case '2':
                    usun_z_listy_pierwszy(element);
                    break;

                case '3':
                    wypisz_liste();
                    break;
                case '4':
                    cout<<"rozmiar kolejki "<<oblicz_rozmiar()<<" \n";
                    break;
                case '5':
                    wstaw_do_listy_za();
                    break;
                case '6':
                    wstaw_do_listy_kolejny();
                    break;

                case '7':
                    koniec=false;
                    break;
                }
            }
            break;
        case 4:
            return 0;


        }


    }
}