【数据结构】队列

前言：
本节博客是对基础数据结构队列的一种实现思路的分享，有需要借鉴即可。

1.队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先
进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一
端称为队头
与此恰好相反的数据结构是栈的概念：详情见博客LINK

2.队列的结构

在写代码之前，我们首先要搞清楚几个问题：
1.队列依托的底层数据结构是什么？为什么？
如果用数组来做队列的话，有个问题，就是需要不停的一个一个的挪动数据。

我们接下来看一下用链表做队列的情况:

所以选择单链表。因为单链表可行且效率较高。

总结一下:用数组实现队列，无论怎么进行布局，都避免不了挪动数据的问题；用链表实现，尾插可以作为队尾（插入数据）头删可以用来出数据。

2.队列的一个整体接口是如何的？

3.为什么在队列的效率考虑我采用了一个结构体来存储指针？（这里指针意思是记录phead的内容与ptail的内容的指针）

原因：如果不用结构体来存储指针的话，那我们每个接口传入都需要传入这两个指针比较麻烦。

3.各种接口的实现

1.初始化与销毁

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;//记录free(pcur);//销毁pcur = next;//更新}pq->phead = pq->ptail = NULL;pq->size = 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.进队列与出队列

这个模块属于队列的重点，因而特地强调一下。

在进队列的情况下，有两种情况，一是没有结点的时候，需要移动phead与ptail两个指针。二是有一个或者多个结点的时候，只需要移动ptail进行尾插即可。

在出队列的情况下，有三种情况，一是没有结点的时候，不能出队列；二是有一个队列的时候，需要对ptai和phead两个指针做改动；三是有多个结点的时候，只需要修改phead进行头删即可。

void QueuePush(Queue* pq, QDataType x)//=尾插
{assert(pq);//申请一块堆空间QNode* newnode = (QNode*)malloc(sizeof(QNode));if(newnode == NULL){perror("malloc fail");exit(1);}//新节点的初始化newnode->val = x;newnode->next = NULL;//如果是没有结点时候需要插入if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}//至少有一个节点时需要插入（尾插）else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);//这里其实有三种不同的情况：//1.没有结点，这种是不可以删除的//2.一个结点，那么就需要phead与ptail都需要调整(容易被坑)//3.多个结点，只需要调整phead即可assert(pq->phead != NULL);if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

3.取头结点与取尾结点

QDataType QueueFront(Queue* pq)
{assert(pq);//没有数据，不能取出assert(pq->phead != NULL);//有数据return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);//没有数据，不能取出assert(pq->phead != NULL);//有数据return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

4.全部代码一览

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;//记录free(pcur);//销毁pcur = next;//更新}pq->phead = pq->ptail = NULL;pq->size = 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}void QueuePush(Queue* pq, QDataType x)//=尾插
{assert(pq);//申请一块堆空间QNode* newnode = (QNode*)malloc(sizeof(QNode));if(newnode == NULL){perror("malloc fail");exit(1);}//新节点的初始化newnode->val = x;newnode->next = NULL;//如果是没有结点时候需要插入if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}//至少有一个节点时需要插入（尾插）else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);//这里其实有三种不同的情况：//1.没有结点，这种是不可以删除的//2.一个结点，那么就需要phead与ptail都需要调整(容易被坑)//3.多个结点，只需要调整phead即可assert(pq->phead != NULL);if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);//没有数据，不能取出assert(pq->phead != NULL);//有数据return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);//没有数据，不能取出assert(pq->phead != NULL);//有数据return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>//队列结构-底层：单链表实现
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//两个指针的结构体
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//实现的各种接口：
//初始化与销毁
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
int QueueSize(Queue* pq);
//插入与删除
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
//取头结点与取尾结点
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);

#include"Queue.h"test1()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QDataType x = QueueFront(&q);printf("%d ", x);QueuePop(&q);x = QueueFront(&q);printf("%d ", x);QueuePop(&q);QueuePush(&q, 4);QueuePush(&q, 5);QueuePush(&q, 6);//取出while (QueueSize(&q) != 0){x = QueueFront(&q);printf("%d ", x);QueuePop(&q);}}int main()
{test1();return 0;
}

---

完。