前言

在介绍栈之后，这里小编就给大家带来的另外一种特殊的线性结构——队列。

1.队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

2.队列的实现

和栈一样队列也可以用顺序表和链表来实现，但是对队列而言使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。2.1 队列结构的实现

那么为了实现队列我们应该定义什么样的结构呢？首先我们应该是声明出表示队列节点的的结构，这与链表并没有太大差异，其次是我们需要声明出一个队列结构了这里我们的想法是我们需要用一个队头指针和一个队尾指针，分别记录队头和队尾节点，然后就是用一个变量来记录队列的长度。

具体大家可以理解为是如下结构：

那么具体用代码实现是：

1.typedef int QDataType;
//队列节点的结构
typedef struct QListNode
{
  struct QListNode* _pNext;
  QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
 QNode * _front;
 QNode* _rear;
 int size;
}Queue;

2.2 初始化队列

void QueueInit(Queue* q)
{
  assert(q);
  q->_front = q->_rear = NULL;
  q->size = 0;
}

2.3 队尾入队列的实现

void QueuePush(Queue* q, QDataType data)
{
   //节点的创建
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->_pNext = NULL;
  newnode->_data = data;
    //情况一：
  if (q->_front == NULL)
  {
    assert(q->_rear == NULL);
    q->_rear=q->_front = newnode;
  }
    //情况二：
  else
  {
    q->_rear->_pNext = newnode;
    q->_rear = newnode;
  }
  q->size++;
}

在入队列前，我们首先需要的是创建一个节点，这里我们需要注意的是将新建节点的的_pNext指针赋值NULL，把需要插入的内容赋值给新建节点存储数据内容的类型。

对于入队列的情况这里有两种情况我们需要考虑一下

情况一：当队列的队头指针和队列的队尾指针都指向NULL时，此时这里插入的一个节点即是队头节点，也是队尾节点

情况二：这种也就是一般情况，这里我们插入一个节点，只需要我们把队尾元素的pNext指针指向新插入的节点，那么这个新插入的节点也就是新的尾节点，所以我们这个时候就需要把队尾指针指向新的队尾节点。示例图如下

在添加元素后记得给统计栈元素的个数的数量+1。

2.4 判断队列是否为空

1. bool QueueEmpty(Queue* q)
2. {
3.  assert(q);
4.  return q->size == 0;
5. }

这里的判断方式和栈是否为空的方式一致，这里我就不再讲解，不懂得话大家可以去小编与栈有关介绍的文章进行查看。

2.5  队头出队列

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  if (q->_front == q->_rear)
  {
  free(q->_front);
  q->_front = NULL;
  q->_rear == NULL;
  }
  else
  {
  QNode* next = q->_front->_pNext;
  free(q->_front);
  q->_front = next;
  }
  q->size--;
}

在进行删除前我们要对队列是否为空进行判断，如果为空我们就跳出程序。如果不为空，这里有两种情况需要我们进行讨论

情况一：当队列只有一个节点的时候，当队列只有一个节点时，我们可以直接对该节点进行删除操作，删除结束后由于队列没节点，我们需要把队头指针和队尾指针都指向NULL。

情况二：一般情况下，我们需要对队列队头元素进行删除时，我们需要提前记录队头节点的下一个节点位置，以免我们删除队头节点后访问不到后续节点，删除后我们需要重新把队头指针指向新的队头节点。