猪八戒网做网站如何付款,不用网站做淘宝客,网页设计用什么尺寸的画布,网站需要的技术现在我们来掌握一下队列#xff01;如果有对往期知识有不足地方#xff0c;可翻阅之前文章哦#xff01; 个人主页#xff1a;小八哥向前冲~-CSDN博客 所属专栏#xff1a;数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客 栈和队列的实现其实都是对你顺序表和链表的检验…现在我们来掌握一下队列如果有对往期知识有不足地方可翻阅之前文章哦 个人主页小八哥向前冲~-CSDN博客 所属专栏数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客 栈和队列的实现其实都是对你顺序表和链表的检验只有一些新的概念罢了
哈哈不信就往下看吧
目录
什么是队列
扩展--循环队列
队列的实现
初始化
队列的插入
队列的判空
队列的删除
队列的尾数据
队列的头数据
队列的销毁
总代码
Queue.h文件
Queue.c文件 什么是队列 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 。入队列进行插入操作的一端称为队尾。出队列进行删除操作的一端称为队头。 上图理解 注意遵循先进先出的原则这个原则就是区分栈后进先出和队列先进先出方法
我们来看看一个队列需要有的最基本要求详情见--queue - C Reference 了解了队列的基本概念我们来扩展一下
扩展--循环队列
生活中队列很常用而在实际的生活中有时我们会用到循环队列。
循环队列它也有一些应用场景。如在操作系统中的生产者消费者模型这个我们后续提到
在这种问题中环形队列可以使用数组实现也可以使用循环链表实现。
我们图上了解 空的环形队列 满的环形队列 注意为了能区别Q.frontQ.rear为队满还是队空我们通常认为Q.rear1Q.front为满
ok!了解了队列的基本我们来巩固一下 3.循环队列的存储空间为 Q(1:100) 初始状态为 frontrear100 。经过一系列正常的入队与退队操作 后 frontrear99 则循环队列中的元素个数为 A .1 B.2 C.99 D.0或者100 4.以下( )不是队列的基本运算 A.从队尾插入一个新元素 B.从队列中删除第i个元素 C.判断一个队列是否为空 D.读取队头元素的值 5.现有一循环队列其队头指针为front队尾指针为rear循环队列长度为N。其队内有效长度为( )(假设 队头不存放数据) A.(rear - front N) % N 1 B.(rear - front N) % N C.ear - front) % (N 1) D.(rear - front N) % (N - 1) 答案3.D 4.B 5.B
参考
3.我们肯定知道元素个数为空时frontrear可当frontrear时也有元素为满的情况
5.因为是循环队列单纯尾指针和头指针相减并不能求出总长。
现在我们来实现一下队列按照一个队列的基本要求。
当然队列像栈一样都可以写成链表和顺序表的底层这里主要了解链表
队列的实现
还是老样子我们创建Queue.h文件声明各种变量和函数创建Queue.c文件来将函数实现。
思路 我们在实现一个函数时要先弄清楚参数。
既然底层是链表那么就得定义节点
typedef int QDataType;
//队列节点
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;
我们来看看我们的底层逻辑需要头指针记录头尾指针记录尾一个计数变量。
既然需要这几个变量时刻记录不如我们直接定义一个结构体来管理这些参数。
作用
这里将参数管理起来可以避免插入和删除函数参数二级指针的使用下面会有体现。
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;ok! 我们来将这些函数一一实现。
初始化
我们得先将记录的参数初始化一下以便后续参数的更新
//队列的初始化
void QInit(Queue* p)
{assert(p);p-phead p-ptail NULL;p-size 0;
}
队列的插入
这里谨记队列是先进先出栈是后进先出不要搞混了
这里由于记录好了尾指针我们直接在尾后面插入就行这样看是不是觉得很方便避免了二级指针的使用。
在插入之前需要开辟一个节点然后开始插入
//队列的插入
void Qpush(Queue* p, QDataType x)
{assert(p);QNode* node (QNode*)malloc(sizeof(QNode));if (node NULL){perror(malloc failed!);return;}//初始化节点node-next NULL;node-val x;//开始插入if (p-phead NULL){p-phead p-ptail node;}else{p-ptail-next node;p-ptail node;}
}
队列的判空
我们只需要在管理的数据变量中判断计数器的值是否为空就行这也侧面体现了我们用一个结构体管理变量的好处
//队列的判空
bool QEmpty(Queue* p)
{assert(p);return p-size0;
}
队列的删除
在删除之前我们要先判断队列是否为空如果为空的话不能删除。因为队列是先进先出原则既然尾部进数据那么头部出数据。所以我们删除数据要在头部删除
而在删除时要讨论队列中一个节点还是多个节点问题。本来不讨论我们也能删除数据那么是为什么要讨论呢
当队列中只有一个节点时头指针等于尾指针一起指向这一个节点当删除时头指针移向空然后将这个节点释放掉但尾指针仍然指向那个节点当我们访问尾指针指向的那个值时程序出现错误
我们上图理解 于是我们能这样写代码
//队列的删除
void Qpop(Queue* p)
{assert(p);//删除之前不能为空assert(!QEmpty(p));//讨论队列只有一个节点的情况if (p-phead-next NULL){free(p-phead);p-phead p-ptail NULL;}else{QNode* next p-phead-next;free(p-phead);p-phead next;}p-size--;
}
队列的尾数据
有了前面的基础我们访问队列尾数据十分简单但需要注意的是判断队列是否为空。
//队列的尾数据
QDataType QBack(Queue* p)
{assert(p);assert(!QEmpty(p));return p-ptail-val;
}
队列的头数据
能十分访问尾数据访问头数据也是如此但是别忘了要判断队列是否为空。
//队列的头数据
QDataType QFront(Queue* p)
{assert(p);assert(!QEmpty(p));return p-phead-val;
}
队列的销毁
我们动态开辟了内存节点那么当我们不用了这个队列时不要忘了销毁它
//队列的销毁
void QDestroy(Queue* p)
{assert(p);QNode* cur p-phead;while (cur){QNode* next cur-next;free(cur);cur next;}
}
总代码
Queue.h文件
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int QDataType;
//队列节点
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;//队列相关变量
//先进先出
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//队列的初始化
void QInit(Queue* p);
//队列的插入
void Qpush(Queue* p, QDataType x);
//队列的判空
bool QEmpty(Queue* p);
//队列的删除
void Qpop(Queue* p);
//队列的尾数据
QDataType QBack(Queue* p);
//队列的头数据
QDataType QFront(Queue* p);
//队列的销毁
void QDestroy(Queue* p);
Queue.c文件
#includeQueue.h
//队列的初始化
void QInit(Queue* p)
{assert(p);p-phead p-ptail NULL;p-size 0;
}
//队列的插入
void Qpush(Queue* p, QDataType x)
{assert(p);QNode* node (QNode*)malloc(sizeof(QNode));if (node NULL){perror(malloc failed!);return;}//初始化节点node-next NULL;node-val x;//开始插入if (p-phead NULL){p-phead p-ptail node;}else{p-ptail-next node;p-ptail node;}
}
//队列的判空
bool QEmpty(Queue* p)
{assert(p);return p-phead NULL;
}
//队列的删除
void Qpop(Queue* p)
{assert(p);//删除之前不能为空assert(!QEmpty(p));//讨论队列只有一个节点的情况if (p-phead-next NULL){free(p-phead);p-phead p-ptail NULL;}else{QNode* next p-phead-next;free(p-phead);p-phead next;}p-size--;
}
//队列的尾数据
QDataType QBack(Queue* p)
{assert(p);assert(!QEmpty(p));return p-ptail-val;
}
//队列的头数据
QDataType QFront(Queue* p)
{assert(p);assert(!QEmpty(p));return p-phead-val;
}
//队列的销毁
void QDestroy(Queue* p)
{assert(p);QNode* cur p-phead;while (cur){QNode* next cur-next;free(cur);cur next;}
}
好了现在你已经掌握了队列快去题海感受一下吧
我们下期见
