#答问题，赢牛书# 设计一个队列，在满足“先进先出”的特点，同时还能在O(1)时间得到队列的最大值。 http://e.weibo.com/1665356464/z7fnGxAbF

main.c

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

typedef struct _node{
	int             data;
	struct _node*   next;
    struct _node*   max;
} Node, *pNode;

typedef struct
{
	pNode   head;
	pNode   tail;
} Queue;

void init_queue(Queue *Q);
void clear_queue(Queue *Q);
bool queue_empty(Queue *Q);
int  queue_length(Queue *Q);
bool get_head(Queue *Q, int *data);
bool en_queue(Queue *Q, int data);
bool de_queue(Queue *Q, int *data);
bool get_max(Queue *Q, int* data);

void init_queue(Queue *Q){
    Q->head = NULL;
    Q->tail = NULL;
}

void clear_queue(Queue *Q){
    pNode node = Q->head;
    pNode temp ;
    while (NULL != node) {
        temp = node->next;
        free(node);
        node = temp;
    }
    Q->head = NULL;
    Q->tail = NULL;
}

bool queue_empty(Queue *Q){
    if (NULL == Q->head) {
        return true;
    }else{
        return false;
    }
}

int  queue_length(Queue *Q){
    pNode node = Q->head;
    int lengh = 0;
    while (NULL != node) {
        lengh++;
        node = node->next;
    }
    return lengh;
}

bool get_head(Queue *Q, int *data){
    if (queue_empty(Q)) {
        return false;
    }
    
    *data = Q->head->data;
    return  true;
}

bool en_queue(Queue *Q, int data){
    pNode node = malloc(sizeof(Node));
    if (NULL == node) {
        return false;
    }
    node->data  = data;
    node->next  = NULL;
    node->max   = node;
    
    if (queue_empty(Q)) {//queue is empty
        Q->head = node;
        Q->tail = node;
        return true;
    }
    
    pNode cursor  = Q->head->max;
    pNode pre_cur = NULL;
    while (NULL != cursor) {
        while (NULL != cursor && cursor != pre_cur && cursor->data >= data) {
            pre_cur = cursor;
            cursor  = cursor->max;
        }
        if (cursor == pre_cur) {
            cursor = cursor->next;
        }else{
            break;
        }
    }
    
    if(NULL == cursor){//cursor is tail
        Q->tail->next = node;
        Q->tail       = node;
        return true;
    }
    
    if (NULL == pre_cur) {
        cursor = Q->head;
    }else{
        cursor = pre_cur->next;
    }
    
    //from cursor node, max data is node
    while (NULL != cursor) {
        cursor->max = node;
        cursor = cursor->next;
    }
    Q->tail->next = node;
    Q->tail       = node;
    
    return true;
}

bool de_queue(Queue *Q, int *data){
    if(queue_empty(Q)){
        return false;
    }
    
    pNode tmp   = Q->head;
    *data       = tmp->data;
    Q->head     = tmp->next;
    free(tmp);
    return true;
}

bool get_max(Queue *Q, int* data){
    if (queue_empty(Q)) {
        return false;
    }
    
    *data = Q->head->max->data;
    return true;
}

int main(int argc, const char * argv[])
{
    Queue* q = malloc(sizeof(Queue));
    if (NULL == q) {
        return 1;
    }
    
    init_queue(q);
    en_queue(q, 10);
    en_queue(q, 3);
    en_queue(q, 2);
    en_queue(q, 100);
    en_queue(q, 300);
    en_queue(q, 40);
    en_queue(q, 20);
    en_queue(q, 50);
    en_queue(q, 60);
    en_queue(q, 10);
    en_queue(q, 20);
    en_queue(q, 2);
    en_queue(q, 1);
    en_queue(q, 0);
    
    int data = 0;
    while (!queue_empty(q)) {
        get_max(q, &data);
        printf("max is %d \n",data);
        de_queue(q, &data);
        printf("de queue %d \n\n",data);
    }
    
    clear_queue(q);
    free(q);
    return 0;
}