#include <stdio.h>
#include <stdlib.h>
#define TYPE int
#define STACKSIZE 1000


typedef struct
{
    int top;
    TYPE items[STACKSIZE];
} Stack;


void initialize(Stack *s)
{
    s->top=0;
}

int isfull (Stack *s)
{
    return s->top>=STACKSIZE?1:0;
}

int isempty(Stack *s)
{
    return s->top==0?1:0;
}

void push(Stack *s,TYPE value)
{
    s->items[s->top++]=value;
}

TYPE pop(Stack *s)
{
    return s->items[--s->top];
}

TYPE peek(Stack *s)
{
    return s->items[s->top-1];
}

int Stack_count(Stack *s)
{
    Stack x;
    int countt=0;
    initialize(&x);
    TYPE temp;
    while(!isempty(s))
    {

        temp=pop(s);
        push(&x,temp) ;
        countt++;
    }
    while(!isempty(&x))
    {
        push(s,pop(&x));
    }

    return countt;
}

Stack reverse_stack(Stack *s)
{
    Stack rev;
    initialize(&rev);
    while(!isempty(s))
    {
        push(&rev,pop(s));

    }
    return rev;
}

void evenoddsort(Stack *s)
{
    Stack odd,even;
    initialize(&odd);
    initialize(&even);
    TYPE x;

    while(!isempty(s))
    {
        x=pop(s);
        if(x%2) push(&even,x);
        else push (&odd,x);

    }

    while(!isempty(&odd))
    {
        push(s,pop(&odd));
    }

    while(!isempty(&even))
    {
        push(s,pop(&even));
    }

}




Stack stack_sort(Stack *s)
{
    Stack x;
    Stack y;
    initialize(&x);
    initialize(&y);
    TYPE temp,xvalue;


    while(!isempty(s))
    {
        TYPE svalue =pop(s);

        if(isempty(&x)) //init,
        {
            push(&x,svalue);
            continue;   //push it and check next item in stack
        }

        xvalue=peek(&x);

        while (svalue>xvalue && !isempty(&x))
        {
            pop(&x);
            push(&y,xvalue);
            xvalue=peek(&x);

        }
        push(&x,svalue);
        while(!isempty(&y))
        {
            push(&x,pop(&y));
        }

    }
return x;
}



Stack stack_sort_insert(Stack *s,TYPE value)
{
    push(s,value);
   return stack_sort(s);
}


Stack two_ordered(Stack *s, Stack *s2)
{
    while(!isempty(s))
    {
        push(s2,pop(s));
    }
     return stack_sort(s2);



}



void stack_delete(Stack *s,int k)
{
    int i;
    Stack x; initialize(&x);

    for(i=1;i<=k-1;i++)
    {

        push(&x,pop(s));

    }
    pop(s);

    while(!isempty(&x))
    {

                push(s,pop(&x));
    }


}

int check_sum(Stack s)//check sum of first half equals sum of secound half
{
    Stack x; initialize(&x);



int    n=Stack_count(&s)/2;
    int i;
    int sum1=0;
    int sum2=0;
    for (i=0;i<=n;i++)
    {
        sum1+=pop(&s);
    }

    while(!isempty(&s))
    {
         sum2+=pop(&s);
    }

    return sum1==sum2?1:0;
}