手撕数据结构 —— 队列（C语言讲解）

目录

1.什么是队列

2.如何实现队列 

3.队列的实现

Queue.h中接口总览

具体实现

结构的定义

初始化

销毁

入队列

出队列

取队头元素

取队尾元素

判断是否为空

获取队列的大小 

4.完整代码附录

Queue.h

Queue.c

---

1.什么是队列

队列是一种特殊的线性表，只允许在一端进行数据的插入操作，在另一端进行数据的删除操作。队列中的数据元素必须满足先进先出的性质。

• 插入数据的操作叫做入队列，插入数据的一端叫做队尾。
• 删除数据的操作叫做出队列，删除数据的一端叫做队头。

队列逻辑结构如下图所示：

2.如何实现队列 

要想实现队列，必须满足队列的要求，也就是以下两点：

• a、在一端插入数据，在另一端删除数据。
• b、满足先进先出的性质。

所以，我们使用数组（顺序表）或者 链表实现，那么使用哪种结构来实现更好呢？

我们可以对比一下：

	数组（顺序表）	链表（单链表）
头插效率	O(N)	O(1)
头删效率	O(N)	O(1)
尾插效率	O(1)	O(N)
尾删效率	O(1)	O(N)

貌似使用数组和链表实现都是一样的，在一端进行插入or删除的效率是O(1)，在另一端进行删除or插入的效率就是O(N) 。

但是我们可以优化一下链表，链表在尾部进行插入or删除的效率之所以是O(N)，是因为需要遍历链表找尾结点，但是，如果我们能够直接找到尾结点，那么链表在尾部进行插入和删除的效率不就都是O(1)了吗？

所以，我们可以使用两个指针head和tail分别指向链表的头结点和尾结点。这样一来，进行尾插时，直接就能找到尾结点，所以尾插的效率也是O(1)。

所以我们实现的队列的最终形态如下：

3.队列的实现

队列的实现，我们主要实现Queue.h和Queue.c文件即可，Queue.h文件中存放声明，Queue.c文件中存放定义。

Queue.h中接口总览

具体实现

结构的定义

实现队列结构的时候，由于我们采用的是链表来实现队列，所以我们需要定义一个个的结点；前面我们分析可知，head指向头结点，tail指向尾结点，可以使得入队列和出队列的时间复杂度都为O(1)，所以我们需要管理好head指针和tail指针，这里我们也采用结构体来管理。

初始化

初始化队列只需要初始化 struct Queue 结构体对象中的成员即可。

• head和tail指针都初始化为空。
• size初始化为0。

 

销毁

销毁队列的时候，首先需要将节点全部释放，然后将head和tail指针置空，并将size置为0。

入队列

入队列的时候要区分两种情况：

• 入队列的结点是第一个结点，此时让head和tail同时指向该结点即可。
• 入队列的结点不是第一个结点，此时让新结点连接到尾结点的后面即可。
• 最后记得将size++。

出队列

出队列的时候要区分三种情况：

• 队列不能为空。
• 只有一个结点的情况。此时，释放结点之后，将head和tail指针置空。
• 不止一个结点的情况。此时，记录head指向的结点，将head后移，然后释放记录的节点。

注意：最后记得将size--。

  

取队头元素

直接返回head指向的结点的数据即可。

取队尾元素

直接返回tail指向的结点的数据即可。

判断是否为空

当队列为空时，head和tail都指向空，所以直接判断head或者tail是否为空都可以。

获取队列的大小 

直接返回struct Queue结构体类型对象中的size即可。

4.完整代码附录

Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode    // 定义结点 
{struct QueueNode* next; // 存储下一个结点的地址 QDataType data;         // 存储数据 
}QNode;typedef struct Queue        // 定义队列 
{QNode* head;            // 指向头结点 QNode* tail;            // 指向尾结点 int size;               // 记录队列的大小 
}Que;// 初始化 
void QueueInit(Que* pq);
// 销毁 
void QueueDestroy(Que* pq);
// 入队列 
void QueuePush(Que* pq, QDataType x);
// 出队列 
void QueuePop(Que* pq);
// 取队头元素 
QDataType QueueFront(Que* pq);
// 取队尾元素 
QDataType QueueBack(Que* pq);
// 判断是否为空 
bool QueueEmpty(Que* pq);
// 获取队列的大小 
int QueueSize(Que* pq);

Queue.c

// 初始化队列 
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}// 销毁队列 
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur)             // 遍历释放结点 {QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}// 入队列 
void QueuePush(Que* pq, QDataType x)
{assert(pq); // pq指针不能为空 QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新结点 if (newnode == NULL){perror("malloc fail");exit(-1);}// 初始化新结点中的成员 newnode->data = x;newnode->next = NULL;if (pq->tail == NULL)  // 入队列的结点是第一个结点 {pq->head = pq->tail = newnode;}else                   // 入队列的结点不是第一个结点 {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}// 出队列
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));      // 出队列的时候，队列不能为空 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;}pq->size--;
}// 取队头元素 
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}// 取队尾元素 
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}// 判空 
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}// 获取队列的大小 
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}