[数据结构与算法]链式队列(LinkQueue)

??作为常用数据结构之一，队列（Queue）是一种线性表，具有先入先出（FIFO）的特性，在队尾入队、队首出队,按照存储结构划分，队列分为顺序队列和链式队列。
??顺序队列通常是使用数组存储队列元素，常用形式是循环队列，即将向量空间想象为一个首尾相接的圆环，使用索引对存储大小取余等手法完成循环，防止假溢出现象。
??链式队列则为单链表方式存储，输入队时从堆中动态申请及释放内存，可避免预置空间造成资源浪费及空间不够造成的队满溢出，但是需要多余的指针域空间。出入队即为单链表节点的插入删除操作，需注意数据取出的方式及时机。

链式队列的C程序

头文件：
节点：数据域及指针域
队列：队头及队尾指针

#ifndef _LINK_QUEUE_
#define _LINK_QUEUE_

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

//linux environment
#define uint8_t  __uint8_t  
#define uint16_t __uint16_t

typedef int data_type_t;

typedef struct
{
    data_type_t *data;
    struct node_t *next;
}node_t;

typedef struct
{
    node_t *front, *rear;
}link_queue_t;

link_queue_t* queue_create(void);
bool queue_is_empty(link_queue_t *queue);
bool enqueue(link_queue_t *queue,data_type_t *buf,uint16_t len);
bool dequeue(link_queue_t *queue,data_type_t *buf,uint16_t len);

源文件
队首创建、队空判断、入队、出队

#include "link_queue.h"

link_queue_t* queue_create(void)
{
    link_queue_t *queue = (link_queue_t *)malloc(sizeof(link_queue_t));
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->next = NULL;
    queue->front = queue->rear = node;
    return queue;
}

bool queue_is_empty(link_queue_t *queue)
{
    assert(queue != NULL);
    return (queue->front == queue->rear);
}

bool enqueue(link_queue_t *queue,data_type_t *buf,uint16_t len)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->data = (data_type_t *)malloc(sizeof(data_type_t) * len);
    memcpy(node->data,buf,len * sizeof(data_type_t));
    node->next = NULL;
    queue->rear->next = node;
    queue->rear = node;
    return true;
}

bool dequeue(link_queue_t *queue,data_type_t *buf,uint16_t len)
{
    if(queue_is_empty(queue)){
        return false;
    }
    node_t *node = queue->front->next;
    memcpy(buf,node->data,len * sizeof(data_type_t));

    queue->front->next = node->next;
    if(node->next == NULL){
        queue->rear = queue->front;
    }
    
    free(node->data);
    free(node);
}

出入队交叉测试
demo：main.c

#include "link_queue.h"

#define BUF_LEN 3

void print_buffer(data_type_t *buf,uint16_t len) 
{
    for(int i = 0; i<len; i++){
        printf("%d ",buf[i]);
    }   
     printf("\n");
}

int main(int argc,char *argv[])
{
    int buffer1[BUF_LEN] = {0,1,2}; 
    int buffer2[BUF_LEN] = {3,4,5}; 
    int buffer3[BUF_LEN] = {6,7,8}; 
    int buffer_out[BUF_LEN] = {0};

    link_queue_t* queue = queue_create();
    assert(queue != NULL);
    
    enqueue(queue,buffer1,BUF_LEN);
    dequeue(queue,buffer_out,BUF_LEN);
    print_buffer(buffer_out,BUF_LEN);
    
    enqueue(queue,buffer2,BUF_LEN);
    enqueue(queue,buffer3,BUF_LEN);

    while(1)
    {
        if(!queue_is_empty(queue)){
            dequeue(queue,buffer_out,BUF_LEN);
            print_buffer(buffer_out,BUF_LEN);
        }
    }
    return 0;
}