#include <iostream>
#include "windows.h"
#include <fstream>
using namespace std;

struct list
{
    int info;
    list* next, *prev;
};


void Create(list*& head, list*& end);
void Add(list*& head, list*& end);
void Add_end(list*& end, int inf);
void Add_head(list*& head, int inf);
void Del_el(list*& head);
void Delete(list*& head);
void View(list*& head, list*& end);
void View_head(list*& head);
void View_end(list*& end);
void Solution(list** head, list** end);


int main()
{
    setlocale(LC_ALL, "rus");
    list* head = new list;
    head = NULL;
    list* end = new list;
    end = NULL;

    int choice,info=0;
    while (true)
    {
        cout << " 1. Создание\n 2. Добавление\n 3. Удаление\n 4. Просмотр \n 5. Сортировка\n 6. Выход" << endl;
        cin >> choice;
        switch (choice)
        {
        case 1:
            Create(head, end);
            Sleep(1000);
            system("cls");
            break;
        case 2:
            Add(head, end);
            Sleep(1000);
            system("cls");
            break;
        case 3:
            Del_el(head);
            Sleep(1000);
            system("cls");
            break;
        case 4:
            View(head,end);
            Sleep(1000);
            system("cls");
            break;
        case 5:

            Solution(&head,&end);
            Sleep(3000);
            system("cls");
            break;
        case 6:
            Delete(head);
            Delete(end);
            exit(0);
            break;
        default:
            cout << "Повторите еще раз" << endl;
            break;
        }
    }
}

void Create(list*& head, list*& end)
{
    if (head == NULL)
    {
        int kolvo, i, info;
        cout << "Введите количество элементов" << endl;
        cin >> kolvo;
        if (cin.fail() || kolvo < 0)
        {
            cout << "Условия ввода не соблюдены" << endl;
            return;
        }
        cout << "1-ый " ;
        cin >> info;
        list* t = new list;
        t->info = info;
        t->next = head;
        t->prev = end;
        head = end = t;
        for (i = 1; i < kolvo; i++)
        {
            cout << i + 1 << "-ый ";
            cin >> info;
            Add_end(end, info);
        }
    }
    else
        cout << "Список уже создан" << endl;
}

void Add(list*& head, list*& end)
{
    cout << " 1.Добавить элемент в начало списка\n 2.Добавить элемент в конец списка" << endl;
    int u,element;
    cin >> u;
    switch (u)
    {
    case 1:
        cout << "Введите добавляемый элемент" << endl;
        cin >> element;
        Add_head(head, element);
        break;
    case 2:
        cout << "Введите добавляемый элемент" << endl;
        cin >> element;
        Add_end(end, element);
        break;
    default:
        cout << "Данный символ ввести невозможно" << endl;
        break;
    }
}

void Add_end(list*& end, int inf)
{
    list* t = new list;
    t->info = inf;
    t->next = NULL;
    t->prev = end;
    end->next = t;
    end = t;
}

void Add_head(list*&head,int inf)
{
    list* t = new list;
    t->prev = NULL;
    t->info = inf;
    t->next = head;
    head->prev = t;
    head = t;
}

void Del_el(list*& head)
{
    if (head != NULL)
    {
        list* t = nullptr;
        t = head;
        head = head->next;
        delete t;

    }
}

void Delete(list*& head)
{
    list* t = nullptr;
    while (head!= NULL)
    {
        t =head;
        head = head->next;
        delete t;

    }
}

void View(list*& head, list*& end)
{

    if (head == NULL)
    {
        cout << "Список пуст!" << endl;
        return;
    }
    cout << "\n 1. Просмотр списка сначала\n 2. Просмотр списка с конца" << endl;
    int r;
    cin >> r;
    switch (r)
    {
     case 1:
         View_head(head);
        break;
     case 2:
         View_end(end);
        break;
     default:
        cout << "Значение введено неправильно" << endl;
        return;
    }
}

void View_head(list*& head)
{
    list* t =head;
    while (t != NULL)
    {
        cout << "Элемент равен " << t->info << endl;
        t = t->next;
    }
}

void View_end(list*& end)
{
    list* t =end;
    while (t != NULL)
    {
        cout << "Элемент равен " << t->info << endl;
        t = t->prev;
    }
}

//void Solution(list*& head, list*& end, list*& Even_head, list*& Even_end, list*& Odd_head, list*& Odd_end)
//{
//  list* current = head;
//  list* t1 = new list;
//  list* t2 = new list;
//  list* t3 = new list;
//  t1->prev = NULL;
//  t1->next = NULL;
//  t2->prev = NULL;
//  t2->next = NULL;
//  t3->prev = NULL;
//  t3->next = NULL;
//  Even_head = Even_end = t1;
//  Odd_head = Odd_end = t2;
//  head = end = t3;
//
//  while (current != nullptr)
//  {
//      if (current->info % 2 == 0)
//      {
//          list* tmp = current;
//          tmp->info = current->info;
//          current = current->next;
//          tmp->next = NULL;
//          tmp->prev = Even_end;
//          Even_end->next = tmp;
//          Even_end = tmp;
//
//      }
//      else
//      {
//          list* tmp = current;
//          tmp->info = current->info;
//          current = current->next;
//          tmp->next = NULL;
//          tmp->prev = Odd_end;
//          Odd_end->next = tmp;
//          Odd_end = tmp;
//
//      }
//
//  }
//  list* t = Even_head;
//  Even_head = Even_head->next;
//  delete t;
//  list* ttt = Odd_head;
//  Odd_head = Odd_head->next;
//  delete ttt;
//  list* tt = Odd_end;
//  Odd_end = Odd_end->prev;
//  delete tt;
//
//
//}
//
void Solution(list** head, list** end)
{
    list* pbeg2 = new list, * pend2 = new list; //*pbeg2 и *pend2 - начало и конец второй очереди
    list* tempbeg = new list, * tempend = new list;// пустышки для первого стека (чтобы не делать исключительных ситуаций с началом очреди и его конца)

    (*head)->prev = tempbeg;//вставляем пустышку в начало первого стека
    tempbeg->next = *head;//думаю тут понятно как это делется (если нет то бери листик с ручкой и рисуй кружочки со связями)
    *head = tempbeg;
    (*end)->next = tempend;// и в конец
    tempend->prev = *end;
    *end = tempend;

    list* pv1 = (*head)->next;// наш счётчик (ну как int i в цикле for для массивов)
    // тут у нас будет два while'a: первый для того, чтобы найти ПЕРВЫЙ нечётный элемент, второй для остальных
    // зачем нам 2 while'a? Дело в том, что, когда мы запихиваем первый элемент во вторую очередь, мы работаем с вершиной-началом этой очереди,
    // а с остальными мы работаем с концом(мы ведь при добавлении нового элемента меняем его конец)
    while (abs(pv1->info % 2) != 1 && pv1->next != NULL)// идём нашим счётчиком от начала(68 строка) до тех пор пока не встретим нечётное число
    {// либо если их вообще нет, то до конца(до NULL)
        pv1 = pv1->next;
    }// после этого цикла мы либо дошли до конца либо дошли до первого нечётного
    if (pv1->next != NULL)// но нам нужна ситуация когда мы дойдём до первого нечётного, поэтому такой и if
    {// а вот тут лучше взять листик с ручкой и всё нарисовать (в голове вряд ли что-то сделаешь)
        pv1->next->prev = pv1->prev;//тут(78 и 79 строка) мы меняем связи предыдущего и следующего элементов...
        pv1->prev->next = pv1->next;// ...так чтобы они были связаны друг с другом
        pbeg2 = pv1;//присваиваем начало второй очереди наш текущий элемент
        pbeg2->next = NULL;// расставляем NULL начала второго стека (до и после ничего ведь не идёт, мы ведь вставляем первый элемент)
        pbeg2->prev = NULL;
        pend2 = pbeg2;// если элемент один значит, что он и начало и конец
        pv1 = pv1->next;//у нас связь для продолжения счётчика никуда не пропала поэтому идём дальше (по сравниению с массивом это i++)
    }
    while (pv1->next != NULL)//ну, с началом разобрались, теперь и с остальными надо(то есть сейчас пойдет работа с вершиной-концом)
    {
        if (abs(pv1->info % 2) == 1)// если нашли
        {
            pv1->prev->next = pv1->next;//как и с началом меняем свзяи предыдущих так чтобы они бли связаны друг с другом
            pv1->next->prev = pv1->prev;
            pend2->next = pv1;// по сути pv1 будет новым концом, поэтому следующий элемент старого конца присваиваем pv1
            pv1 = pv1->next;//тут идём дальше по счётчику (i++)
            pend2->next->prev = pend2;// pend2->next - новой конец, а ->prev указатель на прдыдущий, поэтому присваиваем его старому концу
            pend2 = pend2->next;// наконец, переопределяем ссылку на конец (у нас до этого pend2 был старым концом)
            pend2->next = NULL;// ну и после нового конца идёт NULL
        }
        else  pv1 = pv1->next;// если элемент чётный то просто идём дальше
    }

    // тут обычный вывод
    cout << "Новая очередь: " << endl;
    pv1 = pbeg2;
    while (pv1 != NULL)
    {
        cout << pv1->info << endl;
        pv1 = pv1->next;
    }
    cout << "Остаток первой очереди: " << endl;
    pv1 = (*head)->next;
    while (pv1->next != NULL)
    {
        cout << pv1->info << endl;
        pv1 = pv1->next;
    }

    //пустышки которые мы создали в начале функции надо удалить и поставить указатели на вершины на свои места
    *head = (*head)->next;
    delete (*head)->prev;
    *end = (*end)->prev;
    delete (*end)->next;
}// всё