Skip to content

Instantly share code, notes, and snippets.

@sunxu

sunxu/main.c

Created November 29, 2012 13:06
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sunxu/4168918 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sunxu/4168918 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sunxu created this gist Nov 29, 2012.
    177 changes: 177 additions & 0 deletions main.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,177 @@
    #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;
    }