队列内容整理

队列的定义

队列（queue）简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作.（先进先出）

基础概念：

队尾（rear） ：进行插入的一端 队首（front）：进行删除的一端 入队（enqueue）：插入新元素 出队（dequeue）：删除新元素 添加元素在队尾（只允许添加元素）实现，删除元素在对头（只允许删除元素）实现

队列是一种先进先出表（FIFO），而前面介绍过的栈是一种先进后出表。

队列的操作：

判断队列是否为空 入队，通常命名为push（） 出队，通常命名为pop（） 获取队头元素，通常命名为front（） 求队列中元素个数

#include <iostream>
#include <queue>//使用队列，需要引用的头文件 
using namespace std; 
/*#include <bits/stdc++.h> 万能头文件，包含队列头文件*/ 
int main() {
    queue<int> myQueue;
 
    // 在队尾插入元素
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
 
    // 访问队首元素
    cout << "Front element: " << myQueue.front() << endl;
 
    // 访问队尾元素
    cout << "Back element: " << myQueue.back() << endl;
 
    // 遍历并输出队列中的元素
    while (!myQueue.empty()) {
        cout << myQueue.front() << " ";
        myQueue.pop();
    }
 
    return 0;
}

队列的分类:

基于数组的循环队列（循环队列） 基于链表的队列（链表队列）

基于数组的循环队列

数组存储的缺点： 入队操作：在数组的末尾添加元素，时间复杂度为O（1） 出队操作：数组头部元素出队之后，头部之后的元素均需要往前移动一个位置，时间复杂度为O（n） 循环队列 为了降低时间复杂度，将数组当作一个首尾相连的圆环，分别用两个标志front、rear代表队列的头部和尾部。删除元素时，队首标志往后移，添加元素时，若队尾没有空间，考虑数组的头部空间若还有，则在队头添加元素，防止数组内存空间的流失。 判断满或空的方法： 方法一： 设置一个标志变量flag，同时满足front=rear且flag=1时为满队列 方法二: 空一个元素，保持为空 1.空队列：队首标志与队尾重合 2.满队列：队尾标志+1=队首标志

基于链表的队列

特点： 以结构体节点为单位，不存在元素移动复杂度问题以及内存的浪费问题。 链表头为队列头部，链表尾为队列尾部。 设计两个变量queueFront、queueBack记录队列的两端变化 指针queueFront为标志头指针，指针queueBack指向最后一个元素