数据结构（六）队列

一、概念

队列是一种先入先出的结构（FIFO — first in first out）

二、逻辑结构：线性结构

三、存储结构

（一）顺序队列

顺序队列是基于 一个数组配合着两个下标(队列头front、队列尾rear)来实现的
顺序队列的本质就是对顺序表操作的一个约束：只能在一端插入 另一端删除

这种队列我们一般不直接使用，因为 入队列时rear++ 出队列时front++
相当于每块空间只使用了一次，即使数据出队列了，空间也不会被复用了，相当于一次性的队列

（二）循环队列

循环队列相当于顺序队列的一个小优化，目的是让空间复用起来

这种队列就能让空间复用起来了。
每次数据入队列后，不要直接执行 rear++ 而是改成 rear = (rear+1)%N
每次数据出队列后，不要直接执行 front++ 而是改成 front = (front+1)%N

判断队列为空 front == rear ，如下图，即认为队列空

判断队列为满 (rear+1)%N == front （浪费了一个存储空间 方便区分队列满 和 队列空），如下图，即认为队列已满

1. 结构体定义

typedef struct _Queue{int s[N];int front;int rear;
}queue_t;

2. 创建队列

（1）函数定义

int create_queue(queue_t **my_queue);

（2）注意点

（3）代码实现

int create_queue(queue_t **my_queue){if(NULL==my_queue) return -1;*my_queue=(queue_t *)malloc(sizeof(queue_t));if(NULL==*my_queue) return -1;//初始化(*my_queue)->front=0;(*my_queue)->rear=0;return 0;
}

3. 入队列

（1）函数定义

int is_full(queue_t *my_queue);
int push_queue(queue_t *my_queue,int num);

（2）注意点

（3）代码实现

//满为1，空为0
int is_full(queue_t *my_queue){if(NULL==my_queue) return -1;return (my_queue->rear+1)%N==my_queue->front?1:0;
}//入队列
int push_queue(queue_t *my_queue,int num){if(NULL==my_queue) return -1;if(is_full(my_queue)){printf("队列满\n");return -1;}my_queue->s[my_queue->rear]=num;my_queue->rear=(my_queue->rear+1)%N;return 0;
}

4. 出队列

（1）函数定义

int is_empty(queue_t *my_queue);
int pop_queue(queue_t *my_queue,int num);

（2）注意点

（3）代码实现

//空为1，不空为0
int is_empty(queue_t *my_queue){if(NULL==my_queue) return -1;return my_queue->rear==my_queue->front?1:0;
}int pop_queue(queue_t *my_queue,int *num){if(NULL==my_queue || NULL==num) return -1;if(is_empty(my_queue)){printf("队列空\n");return -1;}*num=my_queue->s[my_queue->front];my_queue->front=(my_queue->front+1)%N;
}

5. 清空和销毁

（1）函数定义

int clean_queue(queue_t *my_queue)
int destroy_queue(queue_t **my_queue)；

（2）注意点

（3）代码实现

int clean_queue(queue_t *my_queue){if(NULL==my_queue) return -1;my_queue->rear=my_queue->front;return 0;
}int destroy_queue(queue_t **my_queue){if(NULL==my_queue || NULL==*my_queue) return -1;free(*my_queue);*my_queue=NULL;return 0;
}

6. 打印

（1）函数定义

int print_queue(queue_t *my_queue);

（2）注意点

（3）代码实现

int print_queue(queue_t *my_queue){if(NULL==my_queue) return -1;/**也可以写成这种形式*for(int i=my_queue->front;i!=my_queue->rear;i=(i+1)%N){*	printf("%d ",my_queue->s[i]);*}**/int temp=my_queue->front;while(temp!=my_queue->rear){printf("%d ",my_queue->s[temp]);temp=(temp+1)%N;}putchar(10);return 0;
}

（三）链式队列

逻辑结构：线性结构
存储结构：链式存储，在内存中不连续

1. 结构体定义

//数据元素的结构体
typedef struct _Node{int data;struct _Node *next;
}node_t;//队列的结构体
typedef struct _Queue{node_t *front;node_t *rear;
}queue_t;

2. 创建队列

（1）函数定义

int create_queue(queue_t **my_queue);

申请一块数据对象的内存空间
初始化

（2）注意点

1. 初始化时，front和rear指针均为NULL

（3）代码实现

int create_queue(queue_t **my_queue){if(NULL==my_queue) return -1;*my_queue=(queue_t *)malloc(sizeof(queue_t));if(NULL==*my_queue) return -1;//初始化(*my_queue)->front=NULL;(*my_queue)->rear=NULL;return 0;
}

3. 入队列

（1）函数定义

int push_queue(queue_t *my_queue,int num);

申请一块数据元素的内存空间
采用尾插

（2）注意点

1. 插入第一个节点时，需要将front和rear都指向第一个节点
2. 其他节点采用尾插的方法，front无需改变

（3）代码实现

//尾插，无需判断是否满
int push_queue(queue_t *my_queue,int num){if(NULL==my_queue) return -1;node_t *p=(node_t *)malloc(sizeof(node_t));if(NULL==p) return -1;p->next=NULL;p->data=num;//插入第一个节点if(NULL==my_queue->front){my_queue->front=p;my_queue->rear=p;return 0;}//插入其他节点,头节点不变my_queue->rear->next=p;my_queue->rear=p;return 0;
}

4. 出队列

（1）函数定义

int is_empty(queue_t *my_queue);
int pop_queue(queue_t *my_queue,int num);

（2）注意点

1. 头删，需要判断队列是否为空，当my_queue->front为NULL时说明队列空
2. 只有一个元素时，删除它时front和rear指针均需要置NULL

（3）代码实现

int is_empty(queue_t *my_queue){if(NULL==my_queue) return -1;return my_queue->front==NULL?1:0;
}
int pop_queue(queue_t *my_queue,int *num){if(NULL==my_queue||NULL==num) return -1;if(is_empty(my_queue)){printf("栈空\n");return -1;}//只有一个元素if(my_queue->front==my_queue->rear){*num=my_queue->front->data;free(my_queue->front);my_queue->front=NULL;my_queue->rear=NULL;return 0;}//有多个元素node_t *ptemp=my_queue->front;*num=my_queue->front->data;my_queue->front=my_queue->front->next;free(ptemp);ptemp=NULL;return 0;
}

5. 清空和销毁

（1）函数定义

int clean_queue(queue_t *my_queue)
int destroy_queue(queue_t **my_queue)；

（2）注意点

1. 清空是释放所有元素的节点空间
2. 销毁是先清空，然后释放数据对象的空间

（3）代码实现

int clean_queue(queue_t *my_queue){if(NULL==my_queue) return -1;node_t *ptemp=NULL;while(my_queue->front!=NULL){ptemp=my_queue->front;my_queue->front=my_queue->front->next;free(ptemp);}ptemp=NULL;my_queue->rear=NULL;return 0;
}int destroy_queue(queue_t **my_queue){if(NULL==my_queue||NULL==*my_queue) return -1;clean_queue(*my_queue);free(*my_queue);*my_queue=NULL;return 0;
}

6. 打印

（1）函数定义

int print_queue(queue_t *my_queue);

（2）注意点

1. 链式队列与顺序队列不同的一点是，链式队列的rear指向的是最后一个已存入数据的节点，顺序队列rear指向的是最后一个已存入数据的空间的下一个空间。
2. 先打印除了最后一个节点以外所有节点，此时还有最后一个节点没打印

（3）代码实现

int print_queue(queue_t *my_queue){if(NULL==my_queue||NULL==my_queue->front) return -1;node_t *ptemp=my_queue->front;//打印除了最后一个节点之外所有节点while(ptemp!=NULL){printf("%d ",ptemp->data);ptemp=ptemp->next;}putchar(10);return 0;
}

四、所有源代码已上传至我的资源

下载链接：
C语言实现循环队列
C语言实现链式队列