#include <stack>
#include <queue>
#include <array>
#include <list>
#include <forward_list>
#include <vector>

#include <set>

#include <map>

#include <unordered_map>
#include <unordered_set>

#include <iostream>

using namespace std;


//forward_list односвязный список
struct Node {
    int value;
    Node* next;
    //конструктор по умолчанию. После : - значит,
    //что инициализация проиходит в момент создания переменной
    Node() : value(0), next(nullptr) {
    };

    Node(int value, Node* n) : value(0), next(n) {
    };
};

//двусвязный список //list<>
//Он содержит указатель на предыдущий (и на следующий тоже) элементы
struct Node {
    int value;
    Node* next;
    Node* prev;
    //конструктор по умолчанию. После : - значит,
    //что инициализация проиходит в момент создания переменной
    Node() : value(0), next(nullptr), prev(nullptr) {
    };

    Node(int value, Node* n, Node* p) : value(0), next(n), prev(p) {
    };
};



//stl - standart template library
int main() {
    stack<int> s; //FILO
    s.push(1);
    cout << s.top() << '\n';
    s.pop();
    s.empty(); //возвращает true, усли пустой

    queue<int> q; //FIFO
    q.push(1);
    cout << q.front() << ' ' << q.back() << '\n';
    q.pop();
    cout << q.empty() << '\n';

    forward_list<int> fl;
    fl.push_front(1);
    cout << fl.front() << '\n';
    //вставка элемента за константу
    fl.insert_after(fl.begin(), 10); //так как это односвязный список вставляем после определенного элемента

    //вставка элемента за константу
    list<int> l;
    l.insert(l.begin(), 10); // тут свободно перемещаемся вперед и назад, вставлять значение легче.

    /*
    Node nw;
    Node n1;
    auto o = n1->next;//&n2
    n1->next = nw;
    nw->next = o;

    n1->n2
    o = n2
    n1->nw
    nw->n2
    n1->nw->n2
    */

    int c[100];

    array<int, 26> a;
    a.fill(0);

    set<int> se;//красночерное дерево - оно же бинарное дерево поиска, все операции за логорифм, кроме
    //минимум и максимум за константу. Самобалансируется! (родительский элемент меняется - не обязательно самый верхний)

    se.insert(1); //log(n)
    se.find(10); //log(n)
    cout << se.contains(7) << '\n';
    //элементы хранятся отсортированными

    map<int, string> mp; //такое же красночерное дерево, с такими асимптотиками, только каждый элемент хранит еще и значение

    unordered_set<int> st;
    //добавление за o(1) обычно, в худшем случае за o(n)
    //таблица со списками. (каждый элемент - список)

    //разные элементы возвращают одинаковые hash - коллизия
    //метод открытой адресации.
}