List_all_2

#include<iostream>
#include<string>

using namespace std;

class Exception
{
private:
    string content;
public:
    Exception(string message) : content(message) {}

    string Message()
    {
        return content;
    }
};

template<class Item> class List
{
private:
    struct Element
    {
        Item inf;
        Element* next;

        Element(Item inf, Element* next) : inf(inf), next(next) {}
    };

    Element* head;
    int length;

    Element* find_index(int index)
    {
        if (index < 0 || index >= length) throw Exception("List - Index error");

        Element* t = head;
        while (index > 0)
        {
            t = t->next;
            index--;
        }

        return t;
    }
public:
    List()
    {
        head = 0;
        length = 0;
    }

    void Add(Item data)
    {
        if (length == 0)
        {
            head = new Element(data, 0);
            length++;
            return;
        }

        find_index(length - 1)->next = new Element(data, 0);
        length++;
    }

    void Insert(Item data, int index)
    {
        if (index == 0)
        {
            head = new Element(data, head);
            length++;
            return;
        }

        if (index == length)
        {
            Add(data);
            return;
        }

        Element* t = find_index(index - 1);
        t->next = new Element(data, t->next);
        length++;
    }

    Item Get(int index)
    {
        return find_index(index)->inf;
    }

    int Length()
    {
        return length;
    }
};

void with_list(int* a, int n)
{
    cout << "--- List ---\n";

    List<int>* l = new List<int>();

    for (int i = 0; i < n; i++)
    {
        l->Add(a[i]);
    }

    int sum = 0;
    List<int>* l2 = new List<int>();
    int t;

    for (int i = 0; i < l->Length(); i++)
    {
        t = l->Get(i);
        cout << t << " ";
        if (t > 0)
        {
            sum += t;
            l2->Add(t);
        }
    }

    cout << "\n" << sum << "\n";
    for (int i = 0; i < l2->Length(); i++)
    {
        cout << l2->Get(i) << " ";
    }
    cout << "\n--- --- ---\n";
}

template<class Item> class DLList
{
private:
    struct Element
    {
        Item inf;
        Element* next;
        Element* prev;

        Element(Item data, Element* next, Element* prev) : inf(data), next(next), prev(prev) {}
    };

    Element* head;
    Element* tail;
    int length;
public:
    DLList()
    {
        head = tail = 0;
        length = 0;
    }

    int Length()
    {
        return length;
    }

    void Add(Item data)
    {
        if (length == 0)
        {
            head = tail = new Element(data, 0, 0);
            length++;
            return;
        }

        tail->next = new Element(data, tail, 0);
        tail = tail->next;
        length++;
    }

    Item Get(int index)
    {
        if (index < 0 || index >= length) throw Exception("DLList - Index error");

        Element* t = head;
        while (index > 0)
        {
            t = t->next;
            index--;
        }

        return t->inf;
    }
};

void with_dllist(int* a, int n)
{
    cout << "--- Double Linked List ---\n";

    DLList<int>* l = new DLList<int>();

    for (int i = 0; i < n; i++)
    {
        l->Add(a[i]);
    }

    int sum = 0;
    DLList<int>* l2 = new DLList<int>();
    int t;

    for (int i = 0; i < l->Length(); i++)
    {
        t = l->Get(i);
        cout << t << " ";
        if (t > 0)
        {
            sum += t;
            l2->Add(t);
        }
    }

    cout << "\n" << sum << "\n";
    for (int i = 0; i < l2->Length(); i++)
    {
        cout << l2->Get(i) << " ";
    }
    cout << "\n--- --- ---\n";
}

template<class Item> class Stack
{
private:
    struct Element
    {
        Item inf;
        Element* next;

        Element(Item data, Element* next) : inf(data), next(next){}
    };

    Element* head;
    int length;
public:
    Stack()
    {
        head = 0;
        length = 0;
    }

    int Length()
    {
        return length;
    }

    void Add(Item data)
    {
        if (length == 0)
        {
            head = new Element(data, 0);
            length++;
            return;
        }

        head = new Element(data, head);
        length++;
    }

    Item Get()
    {
        Element * t = head;
        head = head->next;
        length--;

        int res = t->inf;
        delete t;

        return res;
    }
};

void with_stack(int* a, int n)
{
    cout << "--- Stack ---\n";

    Stack<int>* l = new Stack<int>();

    for (int i = 0; i < n; i++)
    {
        l->Add(a[i]);
    }

    int sum = 0;
    Stack<int>* l2 = new Stack<int>();
    int t;

    for (int i = 0; l->Length() > 0; i++)
    {
        t = l->Get();
        cout << t << " ";
        if (t > 0)
        {
            sum += t;
            l2->Add(t);
        }
    }

    cout << "\n" << sum << "\n";
    for (int i = 0; l2->Length() > 0; i++)
    {
        cout << l2->Get() << " ";
    }
    cout << "\n--- --- ---\n";
}

template<class Item> class Queue
{
private:
    struct Element
    {
        Item inf;
        Element* next;

        Element(Item data, Element* next) : inf(data), next(next) {}
    };

    Element* head;
    Element* tail;
    int length;
public:
    Queue()
    {
        head = tail = 0;
        length = 0;
    }

    int Length()
    {
        return length;
    }

    void Add(Item data)
    {
        if (length == 0)
        {
            head = tail = new Element(data, 0);
            length++;
            return;
        }

        tail->next = new Element(data, 0);
        tail = tail->next;
        length++;
    }

    Item Get()
    {
        Element* t = head;
        head = head->next;
        length--;

        int res = t->inf;
        delete t;

        return res;
    }
};

void with_queue(int* a, int n)
{
    cout << "--- Queue ---\n";

    Queue<int>* l = new Queue<int>();

    for (int i = 0; i < n; i++)
    {
        l->Add(a[i]);
    }

    int sum = 0;
    Queue<int>* l2 = new Queue<int>();
    int t;

    for (int i = 0; l->Length() > 0; i++)
    {
        t = l->Get();
        cout << t << " ";
        if (t > 0)
        {
            sum += t;
            l2->Add(t);
        }
    }

    cout << "\n" << sum << "\n";
    for (int i = 0; l2->Length() > 0; i++)
    {
        cout << l2->Get() << " ";
    }
    cout << "\n--- --- ---\n";
}

int main()
{
    int n = 10;
    int* a = new int[n];

    for (int i = 0; i < n; i++)
    {
        if (i % 2) a[i] = i;
        else a[i] = -i;
    }

    with_list(a, n);
    with_dllist(a, n);
    with_stack(a, n);
    with_queue(a, n);

    //getc(stdin);
    return 0;
}