#include <stdio.h>
#include <stdlib.h>

struct list
{
   char el;
   int prior;
   list *next, *pred;
};

struct  dline
{
   list *beg;
};

void create(dline **d);
int isEmpty(dline *d);
void push(dline **d, char x, int p);
int pop(dline **d, char *x);

int main()
{
   char x;
   dline *d;
   create(&d);

   push(&d, '4', 3);
   push(&d, '1', 1);
   push(&d, '5', 5);
   push(&d, '2', 2);
   push(&d, '3', 2);

   pop(&d, &x);

   return 0;
}

void create(dline **d)
{
   *d = new dline;
   (*d)->beg = NULL;
}

int isEmpty(dline *d)
{
   return !(d->beg);
}

void push(dline **d, char x, int p)
{
   list *h = (*d)->beg;
   list *r = h;
   if (isEmpty(*d))
   {
      h = new list;
      h->next = h;
      h->pred = h;
      h->el = x;
      h->prior = p;
      (*d)->beg = h;
   }
   else
   {
      bool e = false;
      if (r->next == r)
      {
         e = p >= r->prior ? 1 : 0;

         r->next = new list;
         r->pred = r->next;
         r->next->next = r;
         r->next->pred = r;
      }
      else
      {
         while (r->next->prior <= p && r->next != h)
            r = r->next;

         r->next->pred = new list;
         r->next->pred->next = r->next;
         r->next = r->next->pred;
         r->next->pred = r;

         e = true;
      }
      r->next->el = x;
      r->next->prior = p;

      (*d)->beg = e ? h : h->next;
   }

}

int pop(dline **d, char *x)
{
   list *r = (*d)->beg;
   if (!isEmpty(*d))
   {
      *x = r->el;
      if (r->next != r)
      {
         list *d1, *d2;
         d1 = r->next;
         d2 = r->pred;
         delete r;
         r = d1;
         r->pred = d2;
         r->pred->next = r;
      }
      else
      {
         delete r;
         r = NULL;
      }

      (*d)->beg = r;
      return 1;
   }
   else
      return 0;
}