//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;
}