一站式网络推广服务,有实力的网站排名优化软件,网站建设论文的开题报告,站长统计 wordpress一.概念与结构
1.概念
只允许在⼀端进行插⼊数据操作#xff0c;在另⼀端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出FIFO(First In First Out)
入队列#xff1a;进⾏插⼊操作的⼀端称为队尾
出队列#xff1a;进⾏删除操作的⼀端称为队头
注意在另⼀端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)
入队列进⾏插⼊操作的⼀端称为队尾
出队列进⾏删除操作的⼀端称为队头
注意与上文讲到的栈对比栈是先进后出队列是先进先出。
2.结构 队列也可以数组和链表的结构实现使⽤链表的结构实现更优⼀些因为如果使⽤数组的结构出队列在数组头上出数据效率会⽐较低。 数组头删时间复杂度O(N) ** 数组尾插时间复杂度O(1) 单链表头删时间复杂度O(1) 单链表尾插时间复杂度O(N) 因此下午队列的实现中我们采用链表的结构来进行。
二.队列的实现
queue.h
完整头文件如下。
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int QDataType;
typedef struct QueueNode//队列节点的结构,即单链表节点的结构
{QDataType data;struct QueueNode* next;
}QNode;
typedef struct Queue//队列的结构,定义指向队列头尾的指针,以及队列节点的个数
{QNode* phead;QNode* ptail;QDataType size;
}Q;void QueueInit(Q*);//入队列,队尾
void QueuePush(Q*, QDataType);//出队列,队头
void QueuePop(Q*);//队列判空
bool QueueEmpty(Q*);//取队头数据
QDataType QueueFront(Q*);//取队尾数据
QDataType QueueBack(Q*);//队列有效元素个数
int QueueSize(Q*);void QueueDestroy(Q*);
分析
1.此处我们定义了两个结构体一个是队列的基本结构QNode一个是用来表示队列的队头队尾和元素个数的Q。
2.Q存在的意义主要是为了便于后续表示队列的队头队尾时可以简化二级指针的个数且更加清晰。 test.c
相关测试代码如下。
#define _CRT_SECURE_NO_WARNINGS 1
#include Queue.h
void QueueTest01()
{Q q;//定义队列QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);///printf(head:%d\n, QueueFront(q));printf(tail:%d\n, QueueBack(q));printf(size:%d\n, QueueSize(q));QueuePop(q);QueueDestroy(q);
}int main()
{QueueTest01();return 0;
}队列的初始化
#define _CRT_SECURE_NO_WARNINGS 1
#include Queue.h
void QueueInit(Q* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}分析
1.需注意我们此处传入的是指针Q*而非QNode*。
2.其余置空断言操作如常。
队列的销毁
void QueueDestroy(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}分析
1.由于每个节点与之前的链表类似都是动态开辟的因此我们通过Q*找到队列头phead之后逐个释放节点即可。
2.依次释放之后置空并将元素个数置为0即可。
节点的创建
首先创建一个专门用来生产节点的函数避免后续插入时代码的冗余。 QNode* BuyNode(QDataType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}注意在创建节点后记得把size。 队尾插入数据——入队列
void QueuePush(Q* pq, QDataType x)
{assert(pq);if (pq-phead NULL)pq-phead pq-ptail BuyNode(x);else{pq-ptail-next BuyNode(x);pq-ptail pq-ptail-next;}pq-size;
}分析与链表的尾插原理基本相同。
队列判空
在进入删除之前首先需要判断队列数据个数是否为空。
bool QueueEmpty(Q* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}此处通过使用size个数是否为0进行判空也可。
队头删除数据——出队列
void QueuePop(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个节点的情况,避免ptail变成野指针if (pq-ptail pq-phead){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}分析
1.首先判断队列数据是否为空。
2.之后考虑两种情况如果队列只有一个节点那么直接删除之后需要将队头和队尾都置为空。
3如果队列不止存在一个节点同链表的删除原理类似。 返回队头数据
QDataType QueueFront(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}
返回队尾数据
QDataType QueueBack(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}输出队列数据个数
int QueueSize(Q* pq)
{assert(pq);//不规范且时间复杂度O(n)//int size 0;//QNode* pcur pq-phead;//while (pcur)//{// size;// pcur pcur-next;//}//return size;return pq-size;}分析
1.如果我们不在最初引入变量size记录数据个数由于队列是链表结构无法直接通过下标访问元素个数需要逐个遍历记录时间复杂度为On。
2.直接返回size的话就可以减少时间消耗。
三.完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include Queue.h
void QueueInit(Q* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}QNode* BuyNode(QDataType x)
{QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}void QueuePush(Q* pq, QDataType x)
{assert(pq);if (pq-phead NULL)pq-phead pq-ptail BuyNode(x);else{pq-ptail-next BuyNode(x);pq-ptail pq-ptail-next;}pq-size;
}bool QueueEmpty(Q* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}
void QueuePop(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个节点的情况,避免ptail变成野指针if (pq-ptail pq-phead){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}QDataType QueueBack(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;
}int QueueSize(Q* pq)
{assert(pq);//不规范且时间复杂度O(n)//int size 0;//QNode* pcur pq-phead;//while (pcur)//{// size;// pcur pcur-next;//}//return size;return pq-size;}void QueueDestroy(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}以上就是关于队列的概念结构和用链表方式实现队列的讲解欢迎各位大佬前来支持斧正
