先来解释一下数据结构队列的概念：
队列：只允许在一端进行数据插入操作，在另一端进行删除操作的特殊线性表.
队列具有先进先出的性质，和栈的先进后出相反.
其中，进行插入操作的一端称为队尾，进行删除操作的一端称为队头.
这是队列的基本操作.
?实现队列数据插入和删除的办法有两种，一种是用数组，另一种是使用链表.
这两种中，用链表的结构实现会更加好，因为如果用数组在进行头删时，每次都需要移动大量数据来覆盖前一个，导致效率会非常低，所以选择链表.
知道了大概队列的大致内容，我们来说它的模拟实现.
首先说队列的结构体：
既然用链表来实现，那么每个数据一定是用结点保存的，所以先定义一个结构体来表示结点.
因为队列是对队头和队尾进行操作，所以再需要一个结构体来保存头结点和尾结点，类型为结点类型.
结构如下：
typedef int QDataType;
//定义结点类型结构体
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
//队列，包含头结点和尾结点，因为队列操作都是对这两个结点进行操作
struct Queue
{
QNode* head;
QNode* tail;
};下面是队列的一些模拟操作.
目录
队列的初始化
将head和tail结点全部置为空即可.比较简单
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}队列的销毁
思路是：先创建一个临时变量来遍历整个队列，每次将这个结点释放掉，与此同时注意保存这个结点的下一个结点next，这样每次释放掉当前结点后依然可以找到下一个结点.最后将head和tail全部置为空即可.
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}队列的插入
首先用给定的数据先创建一个结点，创建完成之后有两种情况：
队列为空，此时head和tail全部指向NULL，这个时候插入之后只有一个元素，我们让head和tail全部指向它
队列不为空，让tail的next指向这个新结点，并将tail更新为新结点。
代码如下：
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("Malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == 0)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}队列的删除
注意：删除只是指删除队头元素，插入是指从只尾部插入，这是队列的特性所决定的！
删除的时候也会分为两种情况：
如果队列中有两个及以上元素，则保存头结点的下一个结点next，释放掉头结点，并将头节点更新为next
如果队列中只有一个元素时，直接释放掉头结点，并将head和tail全部指向空.
代码如下：
void QueuePop(Queue* 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;
}
}取队头元素
这个非常简单，先判断队列是否为空，不为空就直接返回head指向的数据即可.
QDataType QueueFront(Queue* pq)
{
assert(pq);
//判断队列是否为空
assert(!QueueEmpty(pq));
return pq->head->data;
}取队尾元素
和队头一样的道理.
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}队列的判空
当队列为空时，head和tail也一定为空，所以返回其中任意一个即可.
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}队列元素的个数
思路：定义一个size来计数，遍历队列，每次size++，最后返回size即可.
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
int size = 0;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}下面是总代码：
Queue.h文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
struct Queue
{
QNode* head;
QNode* tail;
};
//队列初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestory(Queue* pq);
//队列的插入(尾部插入)
void QueuePush(Queue* pq, QDataType x);
//队列的删除(头部删除)
void QueuePop(Queue* pq);
//取得队头元素
QDataType QueueFront(Queue* pq);
//取得队尾元素
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//队列的大小
int QueueSize(Queue* pq);Queue.cpp文件
#include"Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("Malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == 0)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* 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;
}
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
int size = 0;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}Test.cpp文件
#include"Queue.h"
int main()
{
Queue q1;
QueueInit(&q1);
QueuePush(&q1,1);
QueuePush(&q1,2);
QueuePush(&q1,3);
QueuePush(&q1,4);
QueuePush(&q1,5);
QueuePop(&q1);
while (!QueueEmpty(&q1))
{
printf("%d ",QueueFront(&q1));
QueuePop(&q1);
}
QueueDestory(&q1);
return 0;
}以上就是数据结构 队列的一些基本内容和操作啦.
如有遗漏或错误之处，欢迎补充或指正哦~