【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 -1
  	qu->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;
  }