#include <iostream>
#include <queue>
#include <stack>

using namespace std;

struct elem
{
    int data;
    unsigned int priority;

    elem *next, *prev;
};

struct priority_queue1
{
    int size = 0;
    elem *back, *front;

    priority_queue1(void) : back(NULL)
    {}
};


bool pop(priority_queue1 &q, int &out, unsigned &pr)
{
    if (!q.back) return false;
    q.size--;

    if (!q.back->next)
    {
        pr = q.back->priority;
        out = q.back->data;
        delete q.back;
        q.back = NULL;
        return true;
    }

    elem *prev, *end;
    prev = end = q.back;
    while (end->next)
    {
        prev = end;
        end = end->next;
    }
    pr = end->priority;
    out = end->data;
    delete end;
    prev->next = NULL;
    return true;
}

void clear(priority_queue1 &q)
{
    elem *del;
    while (q.back)
    {
        del = q.back;
        q.back = q.back->next;
        delete del;
    }
}

void print(priority_queue1 &q)
{
    elem *cursor = q.back;
    while (cursor)
    {
        std::cout << cursor->data << " ";
        cursor = cursor->next;
    }
    std::cout << std::endl;
}

bool compare(elem *prev, elem *next)
{
    return prev->priority > next->priority;
}


void push_by_prior(priority_queue1 &q, const int &value, const unsigned int &priority_value)
{
    q.size++;

    elem *temp = new elem;
    temp->data = value;
    temp->priority = priority_value;
    temp->next = NULL;

    if (!q.back)
    {
        q.back = temp;
        return;
    }

    elem *p = q.back, *prev = NULL;
    for (; p && compare(temp, p); prev = p, p = p->next);

    if (p == q.back)
    {
        temp->next = q.back;
        q.back = temp;
        return;
    }

    prev->next = temp;
    if (!p)return;

    temp->next = p;
}


void newn(priority_queue1 &q, priority_queue1 &a)
{
    unsigned prior;
    int x;

    int i = 1;
    while (q.size > 0)
    {
        if (i % 2 == 0)
        {
            pop(q, x, prior);
            prior = prior - 1;
            push_by_prior(a, x, prior);
        }
        else
        {
            pop(q, x, prior);
            push_by_prior(a, x, prior);
        }
        i++;
    }
}


int main()
{
    priority_queue1 q, a;
    unsigned prior;


    push_by_prior(q, 3, 2);
    push_by_prior(q, 5, 4);
    push_by_prior(q, 7, 3);
    push_by_prior(q, 12, 5);
    push_by_prior(q, 2, 2);

    int value = 0;

/*
    if (pop(q, value, prior))std::cout << value << " ";
    if (pop(q, value, prior))std::cout << value << " ";
    if (pop(q, value, prior))std::cout << value << " ";
    if (pop(q, value, prior))std::cout << value << " ";
*/


    print(q);
    newn(q, a);
    value = 0;

    if (pop(a, value, prior))std::cout << value << " ";
    if (pop(a, value, prior))std::cout << value << " ";
    if (pop(a, value, prior))std::cout << value << " ";
    if (pop(a, value, prior))std::cout << value << " ";


    print(a);


}