leecode-面59（队列的最大值）

维护双端单调队列：

未完成代码：

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

typedef struct MaxQueue_{
    int val;
    struct MaxQueue_ *next;
    struct MaxQueue_ *pre;//双向队列
}MaxQueue;

typedef struct QueneMark_{
    MaxQueue *head;
    MaxQueue *tail;
}QueneMark;

QueneMark *mark_normal;
QueneMark *max_quene; //用来记录normal队列中最大元素和位置在normal队列后
//小于最大元素的值.

QueneMark* maxQueueCreate() {
    QueneMark* mark=(QueneMark*)calloc(1,sizeof(QueneMark));
    mark->tail=mark->head;
    return mark;
}

int maxQueueMax_value() {
    if(max_quene->head==NULL) return -1;
    else  return max_quene->head->val;
}

void maxQueueFree(QueneMark* obj) {
    while(obj->head!=NULL)
    {
        QueneMark* p=obj->head;
        obj->head=obj->head->next;
        free(p);
    }
    obj->tail=obj->head=NULL;
}

int maxQueuePop_front(MaxQueue* obj) {
    int value=0;
    if(obj==NULL) return -1;
    else
    {
        value=obj->val;
        QueneMark* p=obj;
        obj=obj->next;
        free(p);
        return value;
    }   
}


void maxQueuePush_back(int value) {
    MaxQueue* node=(MaxQueue*)calloc(1,sizeof(MaxQueue));
    node->val=value;
    node->next=NULL;
    //加入normal_quene
    mark_normal->tail->next=node;
    mark_normal->tail=node;
    //判断是否加入max_quene
    while(max_quene->tail!=NULL)
    {
        if(max_quene->tail->val<value)//小于就pop出来
        {
            MaxQueue* q=max_quene->tail;
            max_quene->tail=max_quene->tail->pre;
            maxQueuePop_front(q);
        }
        else//大于或者等于就正常加入队列
        {
            MaxQueue* node_add=(MaxQueue*)calloc(1,sizeof(MaxQueue));
            node_add->val=value;
            node_add->pre=max_quene->tail;
            node_add->next=NULL;
            max_quene->tail->next=node_add;
            max_quene->tail=node_add;
        }
        
    }

    if(max_quene->head=NULL)
    {
        MaxQueue* node_add=(MaxQueue*)calloc(1,sizeof(MaxQueue));
        node_add->next=NULL;
        node_add->pre=NULL;
        node_add->val=value;
        max_quene->tail=node_add;
        max_quene->head=max_quene->tail;
    }
}