幼儿园门户网站建设泰安seo
目录
一.队列的概念及结构
二.队列的实现
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;
}