简介
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 的特点。
入队列：进行插入操作的一端称为队尾 。
出队列：进行删除操作的一端称为队头。
入队出队形式：一种入队顺序，只有一种出队顺序。
队列的应用：比如生活中排队买东西，先排队的先购买，平时我们用微信聊天，用键盘进行各种数字的输入，到聊天框中输出，也是队列的应用。
顺序存储队列
循环的队列：
1.头元素指向的数据永远不能有有效数据
2.头元素和尾元素一样，则为空
3.（尾元素+1）%数组长度 == 头元素 则，队列已满
main.c
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
int main()
{
queue* qu;
qu = qu_create();
if(qu == NULL)
return -1;
datatype arr[] = {1,2,3,4,5};
for(int i=0;i<5;i++)
{
qu_enqueue(qu,&arr[i]);
}
datatype tmp;
qu_travel(qu);
qu_dequeue(qu,&tmp);
qu_dequeue(qu,&tmp);
qu_travel(qu);
qu_destroy(qu);
return 0;
}
quque.h
#ifndef QUEUE_H
#define QUEUE_H
#define MAXSIZE 5
typedef int datatype;
typedef struct node_st
{
datatype data[MAXSIZE];
int head,tail;
}queue;
queue* qu_create();
int qu_isempty(queue*qu);
int qu_enqueue(queue*qu,datatype*data);
int qu_dequeue(queue*qu,datatype*data);
void qu_travel(queue*qu);
void qu_clear(queue*qu);
void qu_destroy(queue*qu);
#endif
queue.c
#include <stdlib.h>
#include <stdio.h>
#include "queue.h"
queue* qu_create()
{
queue*qu;
qu = malloc(sizeof(*qu));
if(qu == NULL)
return NULL;
qu->head = 0;
qu->tail = 0;
return qu;
}
int qu_isempty(queue*qu)
{
if(qu->tail == qu->head)
return 0;
return 1;
}
int qu_enqueue(queue*sq,datatype*x)
{
if((sq->tail+1)%MAXSIZE == sq->head) // 队列满
return -1;
sq->tail = (sq->tail +1)%MAXSIZE; //取模构成一个循环
sq->data[sq->tail] = *x;
}
int qu_dequeue(queue*qu,datatype*data)
{
if(qu_isempty(qu) ==0)
return -1;
qu->head = (qu->head+1)%MAXSIZE;
qu->data[qu->head] = *data;
return 0;
}
void qu_travel(queue*qu)
{
if(qu->head == qu->tail) //队列为空
return;
int i;
i = (qu->head +1)%MAXSIZE;
while(i != qu->tail )
{
printf("%d ",qu->data[i]);
i = (i+1)%MAXSIZE;
}
printf("%d \n",qu->data[i]); //输出最后一个函数
}
void qu_clear(queue*qu)
{
qu->head = qu->tail;
}
void qu_destroy(queue*qu)
{
free(qu);
}
链式存储队列
顺序存储长度固定不利于使用，链式存储利于使用。（还是对链表lib2的封装，大家可以看看之前的文章：C数据结构：链表高级篇）
main.c
#include <stdlib.h>
#include <stdio.h>
#include "llist.h"
#include "queue.h"
struct score_st
{
int id;
char name[32];
int math;
int chinese;
};
void print_s(const void *record)
{
const struct score_st*r = record;
printf("%d %s %d %d \n",r->id,r->name,r->math ,r->chinese);
}
int main()
{
QUEUE*qu;
struct score_st temp;
qu = queue_create(sizeof(struct score_st ));
for(int i=0;i<5;i++)
{
temp.id = i;
snprintf(temp.name,32,"std_%d",i);
temp.math = rand()%100;
temp.chinese = rand()%100;
queue_en(qu,&temp);
}
while(1)
{
int ret;
ret = queue_de(qu,&temp);
if(ret == -1)
break;
print_s(&temp);
}
queue_destroy(qu);
return 0;
}
queue.c
#include "queue.h"
QUEUE* queue_create(int size)
{
return llist_create(size);
}
int queue_en(QUEUE*ptr,const void *data)
{
return llist_insert(ptr,data,LLIST_BACKWARD);
}
static int alway_match(const void*p1,const void*p2)
{
return 0;
}
int queue_de(QUEUE*ptr,void*data)
{
return llist_fetch(ptr,(void*)0,alway_match,data); //第二参数填什么都可以
}
void queue_destroy(QUEUE*ptr)
{
llist_destroy(ptr);
}
queue.h
#ifndef QUQUE_H
#define QUQUE_H
#include "llist.h"
typedef LLIST QUEUE;
QUEUE* queue_create(int size);
int queue_en(QUEUE*ptr,const void *data);
int queue_de(QUEUE*ptr,void*data);
void queue_destroy(QUEUE*ptr);
#endif
