0225. Implement Stack using Queu

*LeetCode 225. Implement Stack using Queues
用队列来实现链表，对于C语言难点在于队列自己要实现，这里我们用链表
来实现队列。

typedef struct _listnode{
    int val;
    struct _listnode* next;
}ListNode;

typedef struct{
    int len;
    ListNode* head;
    ListNode* tail;
}Queue;

Queue* init(int size){
    Queue* que = (Queue*)calloc(1, sizeof(Queue));
    que->len = size;
    que->head = que->tail = (ListNode*)calloc(1, sizeof(ListNode));
    ListNode* tp = que->head;
    while(size-1){
        tp->next = calloc(1, sizeof(ListNode));
        tp = tp->next;
        size--;
    }
    tp->next = que->head;//Cycle Queue
    return que;
}

void offer(Queue* q, int val){
    q->tail->val = val;
    q->tail = q->tail->next;
}

int poll(Queue* q){
    int val = q->head->val;
    q->head = q->head->next;
    return val;
}

int peek(Queue* q){
    return q->head->val;
}

int empty(Queue* q){
    return q->head==q->tail?1:0;
}

//There are maxsize+1 nodes, tail always point the null node
// if head equals to tail, queue is empty, or we can calculate
//queue's size by count the node number between head and tail
int size(Queue* q){
    int count = 0;
    ListNode *hd, *tl;
    hd = q->head;
    tl = q->tail;
    while(hd!=tl){
        count++;
        hd = hd->next;
    }
    return count;
}

void clear(Queue* q){
    ListNode* tp = q->head;
    ListNode* nt = tp->next;
    free(tp);
    tp = nt;
    while(tp != q->head){
        nt = tp->next;
        free(tp);
        tp = nt;
    }
    free(q);
}

typedef struct {
    int len;
    Queue* q1;
    Queue* q2;
} MyStack;

MyStack* myStackCreate(int maxSize) {
    MyStack* stk = (MyStack*)malloc(sizeof(MyStack));
    stk->len = maxSize;
    stk->q1 = init(maxSize+1);//It can ensure it will not be overflow
    stk->q2 = init(maxSize+1);//When all element were put in one queue
    return stk;
}

void myStackPush(MyStack* obj, int x){//Push element x onto stack
    offer(obj->q1,x);
}

//Removes the element on top of the stack and returns that element
int myStackPop(MyStack* obj) {
    int ret;
    if(size(obj->q1)!=0){//All element were in q1
        while(size(obj->q1)!=1)//Leave only one element in q1
            offer(obj->q2, poll(obj->q1));//push element into q2
        ret = poll(obj->q1);
    }else if(size(obj->q2)!=0){//All element were in q2
        while(size(obj->q2)!=1)
            offer(obj->q1, poll(obj->q2));
        ret = poll(obj->q2);
    }
    return ret;
}

int myStackTop(MyStack* obj) {// Get the top element
    ListNode* tp;
    if(size(obj->q1)!=0){//If all element were in q1
        tp = obj->q1->head;
        while(tp->next != obj->q1->tail)
            tp = tp->next;//Move tp to proper position
    }else{/*If all element were in q1*/
        tp = obj->q2->head;
        while(tp->next != obj->q2->tail)
            tp = tp->next;
    }
    return tp->val;
}

bool myStackEmpty(MyStack* obj){// Returns whether the stack is empty
    return size(obj->q1)==0 && size(obj->q2)==0?1:0;
}

void myStackFree(MyStack* obj) {
    free(obj->q1);
    free(obj->q2);
    free(obj);
}