内设网站,vpn免流网站建设,网站开发五人分工,公司注册地址和办公地址不一样前言#xff1a;上次我们已经学习了数据结构中一个重要的线性表—栈#xff0c;那么我们这一次就来学习另外一个重要的线性表—队列。 目录#xff1a;
一、 队列的概念 二、 队列的实现#xff1a; 1.队列的创建 三、 队列的操作 1.初始化队列 2.队尾入队列 3.队头出队列… 前言上次我们已经学习了数据结构中一个重要的线性表—栈那么我们这一次就来学习另外一个重要的线性表—队列。 目录
一、 队列的概念 二、 队列的实现 1.队列的创建 三、 队列的操作 1.初始化队列 2.队尾入队列 3.队头出队列 4.获取队列头部元素 5.获取队列队尾元素 6.获取队列中有效元素个数 7.检测队列是否为空如果为空返回非零结果如果非空返回0 8.销毁队列 四、 完整代码展示
队列的概念 队列的概念及结构队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头。 队列的实现 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 我们用三个文件来完成对它的操作。 队列的创建
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)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}队列里的头和尾都为空。 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}如果我们的队尾元素为空那么我们的队尾就是newnode如果我们的队尾不为空我们的ptail的下一个指向newnode现在的队尾就为newnode。 队头出队列
void QueuePop(Queue* pq)
{assert(pq);// assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}如果我们直接删除队头元素那么我们就无法访问下一个元素所以我们先把队头元素保存起来让现在的队头元素为原来队头元素的下一个元素在给原来的队头元素删除。 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq-phead);return pq-phead-val;
}获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);// assert(pq-ptail);return pq-ptail-val;
}获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}size就是我们有效元素的个数这里返回size就可以了。 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}队列为空返回0不为空返回非0后面测试代码的循环条件就是不为0就输出为0就跳出循环。 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}完整代码展示
Queue.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef 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);
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.c
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);// assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL)pq-ptail NULL;pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);// assert(pq-ptail);return pq-ptail-val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}代码测试 test.c:
#includeQueue.h
int main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);printf(%d , QueueFront(q));QueuePop(q);printf(%d , QueueFront(q));QueuePop(q);QueuePush(q, 4);QueuePush(q, 5);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}QueueDestroy(q);return 0;
}这里我们先入队1,23队头就是1队尾就是3我们在出队先输出1在把1出队这样我们就访问2在输出2之后把2出队入队4,5如果我们的队列不为0就输出3,45。最后输出的结果如下图 相信大家一定可以完美的拿捏队列感谢各位小伙伴的支持我们下期再见
