带你深入了解队列(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;
}