链式存储结构 - 队列

//linkedqueue.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
// 类型
typedef struct list_node{
 
    int data;
    struct list_node * next;
 
}list_t;
 
typedef struct queue_node{
    list_t* head;
    list_t* tail;
}queue_t;
 
 
// 创建
queue_t* create_queue()
{queue_t* queue=malloc(sizeof(queue_t));
 
    queue->head=malloc(sizeof(list_t));
 
    queue->head->next=NULL;
 
    queue->tail=queue->head;
 
    return queue;
}
// 判空
int isnull_queue(queue_t* queue)
{if(queue==NULL)
        return 0;
    return queue->head==queue->tail;
//    return queue->head->next==NULL;   // 可以屏蔽掉一些隐患
}
// 入队
int push_queue(queue_t* queue,int data)
{
    //1
    if(queue==NULL)
        return -1;
 
    //2
    list_t* newnode=malloc(sizeof(list_t));
    newnode->next=NULL;
 
    newnode->data=data;
 
    //3
    queue->tail->next=newnode;
 
    //4
    queue->tail=newnode;
 
    return 0;
}
// 出队
int pop_queue(queue_t* queue,int *data)
{if(queue==NULL||isnull_queue(queue))
        return -1;
 
    list_t* temp=queue->head->next;
 
    if(queue->head->next==queue->tail)
        queue->tail=queue->head;
 
    *data=temp->data;
 
    queue->head->next=temp->next;
 
    free(temp);
 
    return 0;
}
// 打印 (伪)
int print_queue_notreal(queue_t* queue)
{if(queue==NULL||isnull_queue(queue))
        return -1;
 
    list_t* temp=queue->head;
    while(temp->next!=NULL)
    {printf("%3d",temp->next->data);
        temp=temp->next;
    }
    printf("\n");
 
//        sleep(1);
 
    return 0;
}
// 长度
int length_queue(queue_t* queue)
{if(queue==NULL||isnull_queue(queue))
        return 0;
 
    int sum=0;
    list_t* temp=queue->head;
    while(temp->next!=NULL)
    {
        sum++;
    //    printf("%3d",temp->next->data);
        temp=temp->next;
    
    }
    return sum;
}
// 清空
int clear_queue(queue_t* queue)
{if(queue==NULL)
        return -1;
 
    int data;
    while(!isnull_queue(queue))
    {pop_queue(queue,&data);
 
    }
    return 0;
}
// 销毁
int destroy_queue(queue_t* queue)
{if(queue==NULL)
        return -1;
 
    if(!isnull_queue(queue))
        clear_queue(queue);
 
 
    free(queue->head);
 
    free(queue);
 
    return 0;
}
 
// 正打印（真）int print_queue_real(queue_t* queue)
{if(queue==NULL||isnull_queue(queue))
        return -1;
 
    queue_t* temp=create_queue();
 
    int data;
    while(!isnull_queue(queue))
    {pop_queue(queue,&data);
 
        printf("%3d",data);
 
        push_queue(temp,data);
    
    }
    printf("\n");
 
    while(!isnull_queue(temp))
    {pop_queue(temp,&data);
 
        push_queue(queue,data);
 
    }
    destroy_queue(temp);
 
    return 0;
}
// 逆打印（真）//     用栈实现队列
int reprint_queue(queue_t* queue)
{if(queue==NULL||isnull_queue(queue))
        return -1;
 
 
    int *stack1=malloc(sizeof(int)*length_queue(queue));
    int top1=-1;
 
    int *stack2=malloc(sizeof(int)*length_queue(queue));
    int top2=-1;
 
 
    int data;
    while(!isnull_queue(queue))
    {pop_queue(queue,&data);
        stack1[++top1]=data;
    }
 
    while(top1!=-1)
    {data=stack1[top1--];//  取数据 后  top --
        printf("%3d",data);
        stack2[++top2]=data;
    }
    printf("\n");
 
 
    while(top2!=-1)
    {data=stack2[top2--];
        push_queue(queue,data);
    
    }
 
    free(stack1);
    free(stack2);
 
    return 0;
}
 
 
int main(int argc, const char *argv[])
{queue_t* queue=create_queue();
 
    int i;
    for(i=1;i<=20;i++)
    {push_queue(queue,i*6);
        print_queue_notreal(queue);
    }
 
    print_queue_real(queue);
    print_queue_notreal(queue);
 
    reprint_queue(queue);
    print_queue_notreal(queue);
#if 0
    int data;
 
    for(i=1;i<=20;i++)
    {pop_queue(queue,&data);
        printf("pop data:%d\n", data);
 
        print_queue_notreal(queue);
    
    }
 
    push_queue(queue,888);
    push_queue(queue,999);
    print_queue_notreal(queue);
#endif    
    return 0;
}