【C语言/数据结构】队列：从概念到队列的实现

一、队列的基础知识

1.队列的定义

        队列是一种特殊的线性表，只允许在一端插入数据，在另一端删除数据；插入数据的一端叫做队尾，插入数据的一端叫做队头；其有着先进先出的准则，FIFO(First In First Out)。

2.队列的功能接口

 初始化

 销毁

 插入数据

 删除数据

 获取队头元素

 获取队尾元素

 返回队列的元素个数

 判断队列是否为空

二、队列的设计思路

1.顺序结构实现队列

2.链式结构实现队列

3.两种结构之间的比较

• 链式结构实现队列：队头与队尾的设计，使得只存在第一个结点数据的删除，巧妙的避开了删除一个结点，需要找到一个结点的问题；插入和删除元素的时间复杂度为O(1)；
• 顺序结构实现队列：数组删除队头的元素时，后面的所有元素，需要向前挪动，其时间复杂度为O(N)；
• 总结：实现队列的最优结构是链式结构，下面将对链式结构实现队列进行深入讲解

  三、队列的代码实现

  1.初始化

  // 初始化void QueueInit(Queue* qu){assert(qu);qu->phead = qu->ptail = NULL;qu->size = 0;}

  2.毁销

  // 销毁void QueueDestory(Queue* qu){while (!QueueEmpty(qu)){QueuePop(qu);}}

  3.插入数据

  // 队尾插入void QueuePush(Queue* qu, QDateType x){assert(qu);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (!newnode){perror("malloc mistake");return;}newnode->Date = x;newnode->next = NULL;if (qu->ptail == NULL){qu->phead = qu->ptail = newnode;}else{qu->ptail->next = newnode;qu->ptail = newnode;}qu->size++;}

  4.删除数据

  // 队头删除void QueuePop(Queue* qu){assert(qu);    //没有元素的处理if (qu->size == 0)return;    //只有一个元素的处理if (qu->ptail == qu->phead){free(qu->phead);qu->phead = qu->ptail = NULL;}    //多个元素的处理方法else{QNode* next = qu->phead->next;free(qu->phead);qu->phead = next;}    //不要忘了size -1qu->size--;}

   5.获取队头元素

  // 获取队头数据QDateType QueueFront(Queue* qu){assert(qu);return qu->phead->Date;}

   6.获取队尾元素

  // 获取队尾数据QDateType QueueBack(Queue* qu){assert(qu);return qu->ptail->Date;}

  7.返回队列的元素个数

  // 获取队列长度size_t QueueSize(Queue* qu){assert(qu);return qu->size;}

   8.判断队列是否为空

  // 判空bool QueueEmpty(Queue* qu){assert(qu);return qu->size == 0 ? true : false;}