C数据结构：队列

简介

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
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