---

前言

  队列实现源代码
  队列是我们遇到的第二个实用数据结构，栈和队列地位等同

---

一、队列的概念及结构

  队列是指只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出 FIFO(First In First Out) 这一点跟栈的先进后出是相反的

队列的核心操作有两个：

• 入队列：即尾插，进行插入操作的一端称为队尾
• 出队列：即头删，进行删除操作的一端称为对头

队列可以考虑顺序表和链表来实现，但是因为队列是一种一端插入一端删除的数据结构，所以最好的实现方式是头删尾插效率高的方式

1. 顺序表实现：尾插和尾删效率较高，但是头插和头删效率低，因此不太适合
2. 单链表实现：头删尾插效率较高，链表头删，链表尾插
3. 双向链表实现：头插头删尾插尾删效率都较高，可以实现队列

照这么看，似乎双向链表是最完美的答案

但是实际上，我们是采用第二种单链表来实现队列，你可能会差异，单链表要遍历一遍才能到达尾节点，而双向链表可以在常量操作内访问到尾节点，为什么我们还会采用单链表来实现队列呢？

答案是我们定义一个队列节点结构体的前提下，在定义一个队列的结构体，里面放着两个队列节点指针front、tail，这样双向链表这里就显得过于复杂，且多开辟了一个头节点，浪费了一点空间，也是不太适合的一种体现

二、队列的实现

  好，掌握了以上知识后，我们来立刻实现！

队列节点和队列

就像前文说的，我们定义两个结构体来实现队列
大致有点像下图：

typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;

	// 根据需要甚至还可以定义一个大小变量
	// int size;
}Queue;

初始化

首先我们肯定要先验空，确保我们确确实实实例化了一个队列结构体q，此时q内部的两个指针，我们需要先置空

void QueueInit(Queue* pq)
{
    assert(pq);

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

销毁

动态开辟的内存，需要手动释放，且由于是链表，所以需要一个一个循环释放
因此思路就是通过一个指针变量cur，一直销毁直到指向为空

void QueueDestroy(Queue* pq)
{
    assert(pq);

    QNode* cur = pq->head;
    while (cur != NULL){
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL; // 头尾节点指针所指向的内容已被回收，因此不置空将成为野指针
}

判断是否为空

我们看初始化函数就知道，当队列为空的时候，头节点指针为空指针（其实尾节点指针也是~），我们可以通过这个来判断

bool isQueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->head == NULL;
}

入队列

入队就是尾插

但是我们要分两种情况，一种是队列有数据，另外一种是队列没有数据的时候，这时候头尾节点指针都指向这个新开辟的节点；如果队列已经有数据了，这时候尾节点指针发生变化

void QueuePush(Queue* pq, QDataType val)
{
    assert(pq);

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL){
        printf("malloc fail\n");
        exit(-1);
    }

    newNode->data = val;
    newNode->next = NULL;

    if (pq->tail == NULL){ // 如果无数据，用pq->head来判断也行
        pq->head = pq->tail = newNode;
    }
    else {
        pq->tail->next = newNode;
        pq->tail = newNode; // 此时newNode就是新的尾节点
    }
}

出队列

出队就是头删

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    if (pq->head->next == NULL) // 只有一个节点的时候
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else { // 当有多个节点的时候
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

获取队头队尾数据

对于队列，我们是有权限来访问队头队尾两个元素，就像栈也有权限访问栈顶元素一样（但是栈底不行！）

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->tail->data;
}

获取队列元素个数

其实你的队列如果有size变量的话，那这里应该蛮简单，只是我这里提供的没有，那么就是经典的遍历套路

int QueueSize(Queue* pq)
{
	assert(pq);
	
	int size = 0;
	QNode* cur = pq->head;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	
	return size;
}

三、实际使用效果

// 各接口一览
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

void QueuePush(Queue* pq, QDataType val);
void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);

bool isQueueEmpty(Queue* pq);

---

总结

  栈和队列，将会贯穿我们后面的学习，所以，请对它们有深刻的认识