数据结构——队列
一、队列是什么
队列，它只允许在一端进行插入操作，一端进行删除操作，队列具有先进先出FIFO(First In First Out)的特性。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
举个栗子：进队列的顺序是1,2,3,4,5。那么出队列的顺序也必然是1,2,3,4,5
二、队列的实现
队列如果要入数据，只能从队列的尾部入，如果要出数据只能从队头出，那么必然涉及到大量的尾插和头删。
用顺序表
顺序表尾插还可以，但是顺序表的尾删要挪动数据，效率不是很高，那么还有没有更优的实现方案呢？
用链表
头删，链表是很擅长的，但是尾插呢？尾插需要遍历链表，找到最后一个节点，然后插入，效率不是也不高吗？此时我们可以定义一个尾节点来解决这个问题，直接插入到尾节点的后面，更新尾节点到下一个位置即可。
1、队列的基本结构
既然要用链表，那肯定要有一个个的节点，我们可以用结构体来定义，接下来我们需要一个头节点和一个尾节点，还有当前队列的数据个数，多个数据，我们最好再用结构体封装起来。
typedef int QTDataType;
typedef struct QNode
{
struct QNode* next;
QTDataType val;
}QNode;
typedef struct Queue
{
QNode* head; // 队列头节点
QNode* tail; // 队列尾节点
int size; // 队列数据个数
}Queue2、队列的初始化
将头节点和尾节点初始化为NULL，size初始化为0。
void QInit(Queue* q)
{
q->head = q->tail = NULL;
q->size = 0;
}3、队列的插入
队列只能从一端进行插入，也就是从尾部进行插入。那么我们需要先malloc申请一个新节点newnode。之后判定是否是第一次入队列，第一次入队列head和tail都是NULL，需要将head和tail都置为newnode，如果不是第一次，直接在tail后面尾插，然后更新tail和size
void QPush(Queue* q, QTDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
//第一次入队列，队列为NULL，特殊处理
if (q->head == NULL)
{
q->head = q->tail = newnode;
}
else
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}4、队列的删除
队列的删除就是头删，头删先记录一下队列头部的下一个节点，然后free掉头结点，更新头节点即可，但是，如果队列只有一个节点，tail指向head已经释放的节点，就野指针了，因此需要特殊处理只有一个节点的情况：free掉head节点，并将head和tail都置NULL。要判断队列是否为空，为空是删除不了的，直接暴力一点报错。
void QPop(Queue* q)
{
assert(q);
assert(q->head != NULL);
// 只有一个节点
if (q->head->next == NULL)
{
free(q->head);
q->head = q->tail = NULL;
}
//两个及以上节点
else
{
QNode* next = q->head->next; // 记录头的下一个节点
free(q->head); //释放掉头节点
q->head = next; //让头节点指向下一个
}
q->size--;
}5、返回队列的队头数据
将head的val返回即可，但是要判定一下队列不为空。
QTDataType QFront(Queue* q)
{
assert(q);
assert(q->head != NULL);
return q->head->val;
}6、返回队列的队尾数据
将tail的val返回即可，同样判定一下队列不为空，队列是先进先出的，1,2,3,4，5进了只能以1,2,3,4,5的顺序出。那返回队尾元素有啥意义呢？队尾元素在某些情况下是非常有意义的，比如说用队列实现栈这道题。 用队列实现栈
QTDataType QBack(Queue* q)
{
assert(q);
return q->tail->val;
}
7、判定队列是否为空
判定head是否为空即可
bool QEmpty(Queue* q)
{
return q->head == NULL;
}
8、返回队列元素个数
返回size即可。
int QSize(Queue* q)
{
return q->size;
}9、队列的遍历
队列的遍历和栈是非常相似的，打印对头数据，然后出队。
#include "queue.h"
int main()
{
Queue q;
QInit(&q);
QPush(&q, 1);
QPush(&q, 2);
QPush(&q, 3);
QPush(&q, 4);
QPush(&q, 5);
while (!QEmpty(&q))
{
printf("%d\n", QFront(&q));
QPop(&q);
}
QDestory(&q);
return 0;
}
10、队列的释放
void QDestory(Queue* q)
{
assert(q);
QNode* cur = q->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->head = q->tail = NULL;
q->size = 0;
}原文地址：https://blog.csdn.net/2301_76227083/article/details/142983614
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！