#include <iostream>
#include <stdexcept>

template<class T>
struct List {
    T a;
    List<T>* prev, * next;

    List() {
        prev = next = NULL;
    }

    List(T value) {
        a = value;
        prev = next = NULL;
    }

    void push_front(T value) {
        List<T>* nv = new List<T>(value);
        nv->next = this;
        nv->prev = NULL;
        if (prev == NULL)
            prev = nv;
        else {
            prev->next = nv;
            nv->prev = prev;
            prev = nv;
        }
    }

    void push_back(T value) {
        List<T>* nv = new List<T>(value);
        nv->prev = this;
        nv->next = NULL;
        if (next == NULL)
            next = nv;
        else {
            next->prev = nv;
            nv->next = next;
            next = nv;
        }
    }

    void pop_back() {
        if (next != NULL) {
            List<T>* temp = next;
            if (next->next != NULL) {
                next->next->prev = this;
                next = next->next;
            }
            else
                next = NULL;
            delete temp;
        }
    }

    void pop_front() {
        if (prev != NULL) {
            List<T>* temp = prev;
            if (prev->prev != NULL) {
                prev->prev->next = this;
                prev = prev->prev;
            }
            else
                prev = NULL;
            delete temp;
        }
    }
};

template<class T>
struct Stack {
private:
    int _size;
    List<T> *back;
public:
    Stack() {
        _size = 0;
        back = new List<T>();
    }

    void push(T value) {
        _size++;
        back->push_back(value);
        back = back->next;
    }

    T pop() {
        if (back->prev == NULL)
            throw std::out_of_range();
        T res = back->a;
        back = back->prev;
        back->pop_back();
        _size--;
        return res;
    }

    int size() {
        return _size;
    }
};

template<class T>
struct Queue {
private:
    int _size;
    List<T>* back, *front;
public:
    Queue() {
        _size = 0;
        front = back = new List<T>();
    }

    void push(T value) {
        if (front == back) {
            front = new List<T>(value);
            front->next = back;
            back->prev = front;
        }
        else {
            back->push_front(value);
        }
        _size++;
    }

    T pop() {
        if (front->next == NULL) {
            throw std::out_of_range();
        }
        T res = front->a;
        front = front->next;
        front->pop_front();
        _size--;
        return res;
    }

    int size() {
        return _size;
    }
};





void queue_work() {
    Queue<int> sample;
    std::cout << "Queue working: write here how many commands you'll write: ";
    int n;
    std::cin >> n;
    std::cout << "Ok, commands're easy: + <value> to add, - to pop and write in console, s - get size\n";
    for (int i = 0; i < n; ++i) {
        char c;
        int v;
        std::cin >> c;
        if (c == '+') {
            std::cin >> v;
            sample.push(v);
        }
        else if (c == '-') {
            std::cout << sample.pop() << '\n';
        }
        else if (c == 's') {
            std::cout << sample.size() << '\n';
        }
    }
}

void stack_work() {
    Stack<int> sample;
    std::cout << "Stack working: write here how many commands you'll write: ";
    int n;
    std::cin >> n;
    std::cout << "Ok, commands're easy: + <value> to add, - to pop and write in console, s - get size \n";
    for (int i = 0; i < n; ++i) {
        char c;
        int v;
        std::cin >> c;
        if (c == '+') {
            std::cin >> v;
            sample.push(v);
        }
        else if (c == '-') {
            std::cout << sample.pop() << '\n';
        }
        else if (c == 's') {
            std::cout << sample.size() << '\n';
        }
    }
}

int main() {
    char c;
    std::cout << "Help for you: 1 - Queue, 2 - Stack, 3 - Help, 4 - Clear, 5 - Exit\n";
    while (std::cin >> c) {
        switch (c)
        {
        case '1':
            queue_work();
            break;
        case '2':
            stack_work();
            break;
        case '3':
            std::cout << "Help for you: 1 - Queue, 2 - Stack, 3 - Help, 4 - Clear, 5 - Exit\n";
            break;
        case '4':
            system("cls");
            break;
        case '5':
            exit(0);
            break;
        default:
            break;
        }
    }
    return 0;
}