长沙企业网站制作服务报价,壁纸网站模板,科技手札,wap企业网站源码目录 1.队列的介绍
2.队列工程
2.1 队列的定义
2.1.1 数组实现队列
2.1.2 单链表实现队列
2.2 队列的函数接口
2.2.1 队列的初始化
2.2.2 队列的数据插入#xff08;入队#xff09;
2.2.3 队列的数据删除#xff08;出队#xff09;
2.2.4 取队头数据
2.2.5 取队…目录 1.队列的介绍
2.队列工程
2.1 队列的定义
2.1.1 数组实现队列
2.1.2 单链表实现队列
2.2 队列的函数接口
2.2.1 队列的初始化
2.2.2 队列的数据插入入队
2.2.3 队列的数据删除出队
2.2.4 取队头数据
2.2.5 取队尾数据
2.2.6 判断队列是否为空
2.2.7 队列长度统计
2.2.8 队列的销毁 3.队列总结反思 1.队列的介绍 队列顾名思义作为有素质的新时代公民在现实生活中我们常常会遇到排队的场景而队列就是借此种情形衍生出来的数据结构形式。在需要排队的时候我们面对一个队列会自觉地站在队尾。随着当队伍中的人慢慢出队我们的位置也从队尾慢慢移动到了队头当我们成为一个队的第一个人时我们就明白终于轮到我们出队了。队列这种数据结构组织数据的形式和排队的场景十分相似均为先进先出后进后出的规则。 在掌握了栈这种数据结构的基础之上我们再来学习队列会比较轻松。栈主要实现的是“先进后出后进先出”的规则而队列遵循的则是“先进先出后进后出”的规律。因此我们可以相互类比地进行学习。
2.队列工程
2.1 队列的定义 在创建队列之前我们需要考虑队列用什么方式实现。我们依然从数组和链表两种结构去考虑优劣我们发现队列在出队和访问时需要访问队头在入队时需要找到队尾所以我们根据这一特征仔细分析一下队列最合适的实现方式。
2.1.1 数组实现队列 当我们打算用数组实现队列的时候 如果以下标小的一端为队头我们发现在入队时我们很容易可以在队尾插入数据。但是在出队的时候类似于顺序标的头删操作所有数据前移一位需要On的时间复杂度。 如果以下标大的一端为队头在出队是很容易。但是在入队时同样需要依次挪动数据也导致了O(n)的时间复杂度。
2.1.2 单链表实现队列 当使用单链表的时候头删头插数据很容易但是尾插尾删因为需要遍历链表找尾而变得复杂。这是我们只需要再引入一个指针指向单链表的尾即可解决这个问题。因为将单链表用作队列的时候队列只会对队头和队尾进行操作所以无论哪一边为队头队列实际操作的都只有链表的头结点和尾结点所以我们只需要定义指针指向头和尾即可避免遍历的冗余操作。 弄明白这一点后我们再来详细讨论一下到底以单链表的哪一边为队头哪一边为队尾。 如果以单链表头结点为队头以尾结点为队尾。在入队的时候我们需要将数据插入队尾也即在尾结点后插入数据因为我们提前存储了尾结点位置所以可以直接将新结点链接在尾结点后。在出队的时候就相当于删除队头的结点也就是单链表头删也没有问题。看来这种方案是个不错的选择。 如果以单链表头结点为队尾以尾结点为队头。那么在入队的时候我们需要将数据插入队尾也就是单链表头插我们可以做到直接链接。在出队的时候我们需要删除队头的数据即单链表尾删熟悉单链表的小伙伴们都知道单链表尾删是需要尾结点前一个结点的需要改变倒数第二个结点的next使其为空指针所以在选取这种方式时我们使用指针指示的就不该是尾结点了而应该是尾结点的前一个结点。 在这篇博客中我们采取第一种方式单链表头结点为队头以尾结点为队尾。
typedef int QDataType;typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue; 首先定义出单链表的结点结构体然后再定义出队列的结构体队列结构体之中看似有三个成员实际上都是对队列载体——单链表的信息描述分别是链表头结点队头链表尾结点队尾链表节点个数队列长度。
2.2 队列的函数接口
2.2.1 队列的初始化 新建了一个队列后我们首先需要对其进行初始化将队列结构体中队头、队尾指针置空将size置为0。
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
2.2.2 队列的数据插入入队 通过我们刚才的分析入队可以简单的视为尾插所以我们按照尾插的逻辑来写入队函数即可。 首先需要开辟空间创建新结点然后熟悉单链表的小伙伴又知道了在我们链接结点之前需要对特殊情况进行特殊处理。一般而言单链表的特殊情况就是空链表和只有一个结点的链表。当链表为空时队列中phead和ptail指针均为空指针直接链接肯定会出错所以当为空链表时需要特殊处理一下。当链表仅有一个结点时其ptail就是尾结点所以不需要特殊考虑和其余情况一样可以直接链接。
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-next NULL;newnode-val x;if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
2.2.3 队列的数据删除出队 出队操作在这里就相当于头删。对于删除操作我们要做最基本的判断排除空链表的情况这里我使用了assert断言。然后考虑特殊情况当链表只有一个结点时头删后链表为空队头指针和队尾指针都需要置空其余情况都是只需要改变队头指针即可。
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);QNode* del pq-phead;if (pq-phead pq-ptail){pq-phead pq-ptail NULL;}else{pq-phead pq-phead-next;}free(del);del NULL;pq-size--;
}
2.2.4 取队头数据 很简单的操作取出队头指针所指结点的保存的值即可。
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}
2.2.5 取队尾数据 取队尾数据在某些场景下会被使用其方法和取队头数据一样。
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}
2.2.6 判断队列是否为空 队列为空的特征很多包括队头指针、队尾指针为空队列长度为0任取一个作为判断依据即可。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}
2.2.7 队列长度统计 队列的长度由成员size指出将其作为返回值即可。
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
2.2.8 队列的销毁 队列实际上是一个链表一个记录链表信息的结构体所以在销毁链表的时候我们需要按照销毁单链表的方式先释放单链表所占用的空间然后将记录信息的结构体其中的值置0、指针置空防止野指针。
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* tmp cur;cur cur-next;free(tmp);tmp NULL;}pq-phead pq-ptail NULL;pq-size 0;
} 3.队列总结反思 栈和队列都是比较简单的数据结构分别采取数组和链表实现了“先进后出后进先出和“先进先出后进后出”的功能。只要能熟练的控制应用单链表我觉得队列应该不在话下。队列在具体实际中的用途也很广泛在广度优先搜索中队列会作为数据存储方式对所有出现的情况进行记录与拓展。
