带你深入了解队列(c/cpp双版本模拟实现)
目录
一.队列的概念及结构
二.队列的实现
2.1队列的结构
2.2初始化队列
2.3队尾入队列
2.4队头出队列
2.5获取队列头部元素
2.6获取队列队尾元素
2.7获取队列中有效元素个数
2.8检测队列是否为空
2.9销毁队列
三.C++ 版本模拟实现队列
一.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
二.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.1队列的结构
首先，先建立一个单链表，用来存储数据和链接结构
然后建立队列，队列有俩个节点，一个指向队列的开始，一个指向结尾
size 用于存储队列长度
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;2.2初始化队列
队列的初始化，把队列的头尾都指向空，size设为0
void QueueInit(Queue* q)
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}2.3队尾入队列
1.首先，malloc一个节点cur
2.判断malloc是否开辟成功
3.给创建成功的节点进行赋值
4.判断如果队列为空，直接插入节点即可（使队列的头尾都指向这个节点）
5.如果不为空，使队列的尾的下一个位置指向新创建的节点，在然后队列的尾指向这个节点
6.最后，数据加一size++
void QueuePush(Queue* q, QDataType data)
{
QNode* cur = (QNode*)malloc(sizeof(QNode));
if (cur == NULL)
{
perror("malloc ");
exit(-1);
}
cur->data = data;
cur->next = NULL;
if (q->rear == NULL)
{
q->front = q->rear = cur;
}
else
{
q->rear->next = cur;
q->rear = cur;
}
q->size++;
}
2.4队头出队列
1.先判断队列是否只有为空，如果是，退出
2.如果队列只有一个数据，直接对队列进行销毁即可
3.如果队列有多个数据，新建一个节点cur等于队列“头”的下一个地址，然后释放掉队头，再把队头指向cur（以前对头的下一个地址），使得第二个数据成为队头
4.最后，数据减一size--
void QueuePop(Queue* q)
{
if(q->front==NULL)
{
exit(-1);
}
if (q->front->next == NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
else
{
QNode* cur = q->front->next;
free(q->front);
q->front = cur;
}
q->size--;
}
2.5获取队列头部元素
直接取头指向的数据即可
QDataType QueueFront(Queue* q)
{
return q->front->data;
}2.6获取队列队尾元素
直接取队列尾指向的元素即可
QDataType QueueBack(Queue* q)
{
return q->rear->data;
}2.7获取队列中有效元素个数
直接返回队列的size
int QueueSize(Queue* q)
{
return q->size;
}2.8检测队列是否为空
检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
return q->front == NULL && q->rear == NULL;
}2.9销毁队列
1.采用while循环依次把队列中的节点全部释放
2.使队列头尾指向空，并且size置为0
void QueueDestroy(Queue* q)
{
QNode* cur = q->front;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
三.C++ 版本模拟实现队列
考虑到学校有好多老师上课，虽然说得是用c语言实现，却用cpp进行操作，现在给大家更新cpp版本的队列的模拟实现，cpp版本的扩容使用的new，函数参数使用的&，可能有同学对指针使用不太熟悉，所以我们同意用&（引用）来实现，方便大家的理解，就不再详细的进行说明了，思路跟c语言实现的一样，只是c和cpp的语言差距有所不同。
#include<iostream>
#include<assert.h>
using namespace std;
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue& q)
{
q.front = NULL;
q.rear = NULL;
q.size = 0;
}
// 队尾入队列
void QueuePush(Queue& q, QDataType data)
{
QNode* cur = new QNode[sizeof(QNode)];
if (cur == NULL)
{
perror("malloc ");
exit(-1);
}
cur->data = data;
cur->next = NULL;
if (q.rear == NULL)
{
q.front = q.rear = cur;
}
else
{
q.rear->next = cur;
q.rear = cur;
}
q.size++;
}
// 队头出队列
void QueuePop(Queue& q)
{
if (q.front->next == NULL)
{
delete q.front;
q.front = q.rear = NULL;
}
else
{
QNode* cur = q.front->next;
delete q.front;
q.front = cur;
}
q.size--;
}
// 获取队列头部元素
QDataType QueueFront(const Queue& q)
{
return q.front->data;
}
// 获取队列队尾元素
QDataType QueueBack(const Queue& q)
{
return q.rear->data;
}
// 获取队列中有效元素个数
int QueueSize(const Queue& q)
{
return q.size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(const Queue& q)
{
return q.front == NULL && q.rear == NULL;
}
// 销毁队列
void QueueDestroy(Queue& q)
{
QNode* cur = q.front;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
q.front = NULL;
q.rear = NULL;
q.size = 0;
}
int main()
{
Queue q;
QueueInit(q);
QueuePush(q, 1);
QueuePush(q, 2);
QueuePush(q, 3);
for (int i = 0;i < 3;i++)
{
cout << QueueFront(q) << endl;
QueuePop(q);
}
printf("%d", !QueueEmpty(q));
QueueDestroy(q);
return 0;
}