一种 “ 超强 ” 队列的C语言实现(附代码)

1、初识size_t

    这里可能大部分都不太知道有size_t这样的一个数据类型，可以说该类型是英文size type的一个缩写，它是一种记录数据大小的数据类型(可以认为是一种整形数据)。其实我们经常使用的sizeof()的返回值数据类型就是size_t，只是我们常常用一个整形比如int来保存返回值。

值得我们注意得是:sizeof类型是一个与操作系统相关得数据类型，它主要是为了提高C语言的可移植性和可读性而加入的，可以说它并不是一种基本的数据类型，而且在头文件中用typedef来重命名的数据类型。其实在我们平时很多地方都用到了size_t，比如：

void *memcpy(void *s1, void const *s2,size_t n);size_t strlen(char const *s);

我们使用的时候几乎都用整形比如int变量来使用，并没有使用到size_t类型，所以说尽管我们的int依赖于C编译器，有些情况size_t并不是固定的，如果我们用基本类型替换可能带来数据类型过小或者过大的问题，过小可能会导致数据溢出问题，过大可能导致运行速度降低！

size_t的使用:只要是用到sizeof等返回值，或者传入值的变量都定义为size_t类型！

2、什么是队列？

​​​​ 队列—一种特殊的操作受限制得线性表，用户仅允许在线性表的头部获取数据，在尾部插入数据，所以大家也叫FIFO(先进先出)线性表。

形象一点的表达：类似于一队人排队钻进一根只能进入一个人的管子，先进去的人先出来，后面的人只能在从同一个口子进入！

队列的类型：顺序队列和循环队列。顺序队列，出队列指针必须>或者=入队列指针，否则容易出现假溢出现象；而循环队列只要入队列指针与出队列指针不再次重合就不回溢出！

3、不受类型限制的队列实现

首先我们先贴上刚刚写好的Queue.h和Queue.c文件

//FileName : Queue.h

#include<stdio.h>

#ifndef __QUEUE_H__
#define __QUEUE_H__

/***************************************
*fuction :数据类型定义
*author  :(公众号:最后一个bug)
**************************************/
//节点数据类型定义
typedef struct _tag_stNode
{
   void *data;              //数据指针
   struct _tag_stNode *next;//指向下一个节点
}STNode;

//队列结构体定义
typedef struct _tag_stQueue
{
   int    QueueSize; //队列大小
   size_t memSize;  //数据大小
   STNode *head;    //头指针
   STNode *tail;    //尾指针
}STQueue;

/***************************************
*fuction  :函数接口声明
*author   :(公众号:最后一个bug)
**************************************/
//队列接口函数定义
void QueueInit(STQueue *q, size_t memSize);
int  QueueIn(STQueue *, const void *);
void QueueOut(STQueue *, void *);
void GetQueueUnit(STQueue *, void *);
void ClearQueue(STQueue *);
int  GetQueueSize(STQueue *);

#endif

//FileName : Queue.c#include <stdlib.h>#include <string.h>

#include "Queue.h"

/***************************************
*fuction  :队列初始化
*author   :(公众号:最后一个bug)
**************************************/
void QueueInit(STQueue *q, size_t memSize)
{
   q->QueueSize = 0;
   q->memSize = memSize;
   q->head = q->tail = NULL;
}

/***************************************
*fuction  :入队列
*author   :(公众号:最后一个bug)
**************************************/
int QueueIn(STQueue *q, const void *data)
{
    STNode *newNode = (STNode *)malloc(sizeof(STNode));

    if(newNode == NULL)
    {
        return -1;
    }

    newNode->data = malloc(q->memSize);

    if(newNode->data == NULL)
    {
        free(newNode);
        return -1;
    }

    newNode->next = NULL;

    memcpy(newNode->data, data, q->memSize);

    if(q->QueueSize == 0)
    {
        q->head = q->tail = newNode;
    }
    else
    {
        q->tail->next = newNode;
        q->tail = newNode;
    }

    q->QueueSize++;
    return 0;
}

/***************************************
*fuction  :出队列
*author   :(公众号:最后一个bug)
**************************************/
void QueueOut(STQueue *q, void *data)
{
    if(q->QueueSize > 0)
    {
        STNode *temp = q->head;
        memcpy(data, temp->data, q->memSize);

        if(q->QueueSize > 1)
        {
            q->head = q->head->next;
        }
        else
        {
            q->head = NULL;
            q->tail = NULL;
        }

        q->QueueSize--;
        free(temp->data);
        free(temp);
    }
}

/***************************************
*fuction  :获得队列头部数据
*author   :(公众号:最后一个bug)
**************************************/
void GetQueueUnit(STQueue *q, void *data)
{
    if(q->QueueSize > 0)
    {
       STNode *temp = q->head;
       memcpy(data, temp->data, q->memSize);
    }
}

/***************************************
*fuction  :清除队列
*author   :(公众号:最后一个bug)
**************************************/
void ClearQueue(STQueue *q)
{
  STNode *temp;

  while(q->QueueSize > 0)
  {
      temp = q->head;
      q->head = temp->next;
      q->QueueSize--;
      free(temp->data);
      free(temp);
  }

  q->head = NULL;
  q->tail = NULL;
}

/***************************************
*fuction  :获得队列数据个数
*author   :(公众号:最后一个bug)
**************************************/
int GetQueueSize(STQueue *q)
{
    return q->QueueSize;
}

//FileName :main.c#include "Queue.h"

/***************************************
*fuction  :测试函数
*author   :(公众号:最后一个bug)
**************************************/
int main(void)
{
    int val;
    STQueue q;

    QueueInit(&q, sizeof(int));

    for(val = 0; val < 10; val++)
    {
        QueueIn(&q, &val);
        printf("Data: %d enter Quene.\n", val + 1);
    }

    printf("\n");

    GetQueueUnit(&q, &val);

    printf("The value that is at the front of the queue is %d\n\n", val + 1);

    while(GetQueueSize(&q) > 0)
    {
        QueueOut(&q, &val);
        printf("Data: %d exit Quene.\n", val + 1);
    }

    printf("欢迎大家关注公众号：最后一个bug");
    return 0;
}

编译中... 编译成功!Data: 1 enter Quene.

Data: 1 enter Quene.

Data: 2 enter Quene.

Data: 3 enter Quene.

Data: 4 enter Quene.

Data: 5 enter Quene.

Data: 6 enter Quene.

Data: 7 enter Quene.

Data: 8 enter Quene.

Data: 9 enter Quene.

Data: 10 enter Quene.The value that is at the front of the queue is 1

Data: 1 exit Quene.

Data: 2 exit Quene.

Data: 3 exit Quene.

Data: 4 exit Quene.

Data: 5 exit Quene.

Data: 6 exit Quene.

Data: 7 exit Quene.

Data: 8 exit Quene.

Data: 9 exit Quene.

Data: 10 exit Quene.

欢迎大家关注公众号：最后一个bug

   解析代码：

     1)节点数据结构中采用void类型的指针，能够指向任意数据类型来扩展我们的队列。

2)队列数组顺序队列，我们可以通过修改扩展变成循环队列，便于我们使用。

3)具体的使用可以参考上面的例子进行开发。

4、队列的应用

     1)队列可以作为一种数据缓冲，当我们的数据无法实时进行发送的时候，可以进行适当的队列缓冲，集中到一定的数据，然后进行打包发送。

2)队列可以实现任务之间的一个信息交互，可以解决一些多线程问题，实现一种任务之间的异步处理。

3)由于是队列的一个先进先出特点，我们也可以利用队列来严格的控制数据的顺序。

好了，这里是公众号“最后一个bug”，欢迎各位关注本公众号，我将继续为大家带来更加精彩的原创文章！