S, Q, L

//--------------Stiva--------------
struct Stiva
{
    int st[Nmax];
    int top;

    void Init()
    {
        top = -1;
    }

    int Empty()
    {
        if(top == -1) return 1;
        return 0;
    }

    int Full()
    {
        if(top == Nmax - 1) return 1;
        return 0;
    }

    void Push(int x)
    {
        if(Full()) cout << "Stack Overflow!";
        else st[++top] = x;
    }

    void Pop()
    {
        if(!Empty()) top--;
    }

    int Top()
    {
        return st[top];
    }
     int Size()
     {
         return top+1;
     }
};

//--------------Coada--------------
struct Coada
{
    int q[Nmax];
    int pr, ul;

    void Init()
    {
        pr = 0; ul = - 1;
    }

    int Empty()
    {
        if(pr <= ul) return 0;
        return 1;
    }

    void Push(int x)
    {
        q[++ul] = x;
    }

    void Pop()
    {
        if(!Empty()) pr++;
    }

    int Front()
    {
        return q[pr];
    }

    int Size()
    {
        return ul - pr + 1;
    }
};

//--------------Lista--------------
struct Lista
{
    int t[Nmax];
    int pr, ul;

    void Init()
    {
        pr = 0; ul = -1;
    }

    int Empty()
    {
        return pr > ul;
    }

    void InsertEnd(int x)
    {
        t[++ul] = x;
    }

    void Insert(int poz, int x)
    {
        for(int i = ul; i >= poz + pr - 1; i--)
            t[i+1] = t[i];
        t[poz + pr - 1] = x;
        ul++;
    }

    void Parcurgere()
    {
        if(Empty()) cout << "Lista este vida!";
        else
        {
            for(int i = pr; i <= ul; i++)
                cout << t[i] << " ";
            cout << "\n";
        }
    }

    void DeleteEnd()
    {
        if(!Empty()) ul--;
    }

    void DeleteBegin()
    {
        if(!Empty()) pr++;
    }

    void Delete(int poz)
    {
        if(Empty()) return;
        for(int i = poz + pr - 1; i < ul; i++)
            t[i] = t[i+1];
        ul--;
    }

    int GetElement(int k)
    {
        return t[pr + k - 1];
    }

    int Search(int x)
    {
        int i;
        for(i = pr; i <= ul; i++)
            if(t[i] == x) return i - pr + 1;
        return -1;
    }

    int Size()
    {
        return ul - pr + 1;
    }

};

//--------------Lista simplu inlantuita--------------
struct Nod
{
    int info;
    Nod *leg;
};

struct Lista                            /// Simplu inlantuita
{
    Nod *L;
    void Inserare1(int x)               /// Inserare la inceput
    {
        Nod *p;
        p = new Nod;
        p -> info = x;
        p -> leg = L;
        L = p;
    }

    void Inserare2(Nod *p, int x)       /// Inserare dupa nodul de adresa memorata in p
    {
        Nod *q;
        q = new Nod;
        q -> info = x;
        q -> leg = p -> leg;
        p -> leg = q;
    }

    ///     Insereaza dupa al k-lea nod
    /// un nou nod cu informatia x;
    /// Daca lista are mai putin de
    /// k noduri, inserarea se face
    /// la sfarsitul listei.
    void Inserare3(int k, int x)
    {
        Nod *p, *q;
        for(p = L; (k > 1) && (p != NULL); p = p -> leg)
        {
            k--;
            q = p;
        }
        if(p == NULL) /// Inserez dupa q
            Inserare2(q, x);
        else /// Inserez dupa p
            Inserare2(p, x);
    }

    void Parcurgere()                   /// Parcurgerea listei
    {
        for(Nod *p = L; p != NULL; p = p -> leg)
            cout << p -> info << " ";
        cout << "\n";
    }

    void Init()                         /// Initializarea listei vide
    {
        L = NULL;
    }

    void Sterge1()                      /// Stergerea primului nod
    {
        if(L = NULL) return;
        Nod *p;
        p = L;
        L = p -> leg;
        delete p;
    }

    void Sterge2(Nod *p)                /// Stergerea nodului dupa nodul de adresa memorata p
    {
        Nod *q;
        q = p -> leg;
        p -> leg = q -> leg;
        delete q;
    }

    Nod *Cautare(int x)                 /// Cautarea valorii x in lista si returnarea pointer-ului
    {
        Nod *p;
        for(p = L; p != NULL; p = p -> leg)
            if(p -> info == x)
                return p;
        return NULL;
    }

    void ParcDS(Nod *p) /// Parcurgerea de la dreapta la stanga a nodurilor listei
    {
        if(p != NULL)
        {
            ParcDS(p -> leg);
            cout << p -> info << " ";
        }
    }
};

//--------------Lista Dublu Inlantuita--------------
struct Nod
{
    int info;
    Nod *stg, *drp;
};

Nod *head, *tail;

void Init()                     /// Initializare
{
    head = tail = NULL;
}

void Creare(int x)              /// Creare l.d.i cu un nod
{
    head = new Nod;
    head -> info = x;
    head -> drp = NULL;
    head -> stg = NULL;
    tail = head;
}

void AdInceput(int x)           /// Adaugarea la inceput
{
    Nod *p;
    p = new Nod;
    p -> info = x;
    p -> drp = head;
    p -> stg = NULL;
    head -> stg = p;
    head = p;
}

void AdSfarsit(int x)           /// Adaugarea la sfarsit
{
    Nod *p;
    p = new Nod;
    p -> info = x;
    p -> stg = tail;
    p -> drp = NULL;
    tail -> drp = p;
    tail = p;
}

void AdDupaNod(Nod *p, int x)   /// Adaugarea dupa un nod
{
    Nod *q;
    q = new Nod;
    q -> info = x;
    q -> stg = p;
    q -> drp = p -> drp;
    p -> drp = q;
    p -> drp -> stg = q;
}

void ParcSD()                   /// Parcurgerea St->Dr
{
    for(Nod *p = head; p != NULL; p = p -> drp)
        cout << p -> info << " ";
    cout << "\n";
}

void ParcDS()                   /// Parcurgerea Dr->St
{
    for(Nod *p = tail; p != NULL; p = p -> stg)
        cout << p -> info << " ";
    cout << "\n";
}
}