没有备案的网站怎么访问不了,ui设计自学学的出来吗,网站规划与建设需求分析,官方网站开发需要几个技术人员前言 在学过栈之后#xff0c;会了解到栈的底层是根据顺序表或者链表来构建的#xff0c;那么我们今天要学习的队列是否也是基于顺序表和链表呢#xff1f;那我们直接进入正题吧#xff01;
1. 队列的概念#xff08;图解#xff09; 还是跟上节一样#xff0c;依旧用图…前言 在学过栈之后会了解到栈的底层是根据顺序表或者链表来构建的那么我们今天要学习的队列是否也是基于顺序表和链表呢那我们直接进入正题吧
1. 队列的概念图解 还是跟上节一样依旧用图解的方式让大家更好的理解概念。
1.1 队列的组成 队列队列指的是图中黑色边框及其内部的空间 队头出元素的一边叫队头 队尾入元素的一边叫队尾 队内元素蓝色正方形 1.2 队列的进出规则先进先出 队列的进出规则跟栈不一样栈是先进后出而队列是先进先出。 队列只能从队头出队尾入所以这就造就了队列的先进先出先从队尾入的元素先从队头出。 2. 队列的架构
2.1 队列为顺序表构成舍弃方案 队列的入队列相当于尾插头插队列的出队列相当于头删尾删 我们知道顺序表的尾插尾删是非常快的很方便。但是头插头删却需要挪动数据覆盖十分麻烦。无论是我们入队列和出队列我们都必然会涉及到头的挪动。这样大大增加了我们时间复杂度所以我们队列不推荐使用顺序表构建。
2.2 队列为链表构成文末源代码 我们是选择什么样的链表呢单向链表还是双向链表是否带头是否成环不要着急我们先来看单链表是否简单可行。
2.2.1 队列为单链表构成 如图我们选择链表的头部作为了队头链表的尾部作为了队尾那么出队列就是头删入队列就是尾插。
1. 入队列 入队列就是链表的尾插先找到链表的尾再跟新节点连接就可以了。但是当我们队列中没有元素的时候就需要改变一下链表头指针指向的位置让他指向第一个节点这里我们是改变指针需要用到二级指针但是我们今天不用二级指针使用一个新的方法来解决。 2. 出队列 出队列相当于链表的头删看图就可以了。
我们会发现其实单链表已经可以几乎很好的解决队列这个数据结构了那我们就没有必要去创造什么带头啊循环啊双向啊这些结构。所以接下来就让源代码登场吧
3. 队列由单链表构成源代码
3.1 队列的定义 这里跟以往不同的点是 这里我们重新定义了一个结构体包含了队列的头节点和尾结点我们这么定义的目的是可以更改头节点和尾节点。
//如果你要更改队列元素的数据类型在这里更改一次就OK了int变成其他数据类型
typedef int QDataType;
//这里我们正常定义队列的节点因为是链表构成的和链表节点一样
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
//这里我们重新定义了一个结构体包含了队列的头节点和尾结点我们这么定义的目的是可以更改头节点和尾节点
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
3.2 队列的初始化
//初始化
void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
3.3 队列的销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
3.4 入队列
//入队列
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
3.5 出队列
//出队列
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
3.6 取队头元素
//取队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}
3.7 取队尾元素
//取队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
3.8 判断队列是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}
3.9 求队列长度
//队列的长度
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}
4. 习题
4.1 下列关于队列的叙述错误的是
A.队列可以使用链表实现
B.队列是一种“先入先出”的数据结构
C.数据出队列时一定只影响尾指针
D.数据入队列时一定从尾部插入
答案C
解析出队操作一定会影响头指针如果出队之后队列为空会影响尾指针。
4.2 用无头单链表存储队列其头指针指向队头结点尾指针指向队尾结点则在进行出队操作时
A.仅修改队头指针
B.队头、队尾指针都要修改
C.队头、队尾指针都可能要修改
D.仅修改队尾指针
答案C
解析出队操作一定会修改头指针如果出队之后队列为空需要修改尾指针。
4.3 以下不是队列的基本运算的是
A.从队尾插入一个新元素
B.从队列中删除队尾元素
C.判断一个队列是否为空
D.读取队头元素的值
答案B
解析队列只能从队头删除元素。
4.4 下面关于栈和队列的说法中错误的是 多选
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”栈是“先入后出”
答案AB
解析
A错误栈是尾部插入和删除一般使用顺序表实现队列是头部删除尾部插入一般使用链表实现
B错误栈是后进先出尾部插入和删除并不是两端队列是先进先出尾部插入头部删除。
4.5 下列关于顺序结构实现循环队列的说法正确的是
A.循环队列的长度通常都不固定
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满
C.通过设置计数的方式可以判断队列空或者满
D.循环队列是一种非线性数据结构
答案C
解析顺序结构实现循环队列是通过数组下标的循环来实现的
A错误循环队列的长度都是固定的
B错误队头和队尾在同一个位置时 队列可能是空的也可能是满的因此无法判断
C正确设置计数即添加一个字段来记录队列中有效元素的个数如果队列中有效元素个数等于空间总大小时队列满如果队列中有效元素个数为0时队列空
D错误循环队列也是队列的一种是一种特殊的线性数据结构 好啦我们关于队列的实现已经结束了谢谢大家
