笔记·队列

一、什么是队列

队列是一种先进先出（First In First Out，FIFO）的线性数据结构。就像排队买票，先来的人先买到票先离开，后来的人排在队尾后离开。

核心操作：

• 入队（push/enqueue）：在队尾添加元素
• 出队（pop/dequeue）：移除队头元素
• 取队头（front）：查看队头元素但不移除
• 取队尾（back）：查看队尾元素但不移除
• 判空（empty）：判断队列是否为空
• 获取大小（size）：获取队列中元素个数

---

二、队列的两种实现方式

1. 数组实现队列（循环队列）

原理：用数组存储元素，用head指向队头位置，tail指向队尾位置。为了高效利用空间，采用循环队列，当tail到达数组末尾时回到开头。

优点：简单高效，访问速度快
缺点：大小固定，需要处理循环逻辑

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int q[MAXN],head,tail;
int main() {
    head=1;
    tail=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            if((tail+1)%MAXN!=head) {
                tail=(tail+1)%MAXN;
                q[tail]=x;
                printf("入队成功：%d\n",x);
            } else {
                printf("队列已满\n");
            }
        } else if(op==2) {
            if(head!=tail+1) {
                printf("出队元素：%d\n",q[head]);
                head=(head+1)%MAXN;
            } else {
                printf("队列为空\n");
            }
        } else if(op==3) {
            if(head!=tail+1) {
                printf("队头元素：%d\n",q[head]);
            } else {
                printf("队列为空\n");
            }
        } else if(op==4) {
            if(head!=tail+1) {
                printf("队尾元素：%d\n",q[tail]);
            } else {
                printf("队列为空\n");
            }
        } else if(op==5) {
            if(head<=tail) {
                printf("队列中元素个数：%d\n",tail-head+1);
            } else if(head>tail&&!(head==1&&tail==0)) {
                printf("队列中元素个数：%d\n",MAXN-head+tail+1);
            } else {
                printf("队列中元素个数：0\n");
            }
        }
    }
    return 0;
}

2. STL队列（标准模板库）

C++的STL提供了现成的队列容器，方便使用。

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main() {
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            q.push(x);
            printf("入队成功：%d\n",x);
        } else if(op==2) {
            if(!q.empty()) {
                printf("出队元素：%d\n",q.front());
                q.pop();
            } else {
                printf("队列为空\n");
            }
        } else if(op==3) {
            if(!q.empty()) {
                printf("队头元素：%d\n",q.front());
            } else {
                printf("队列为空\n");
            }
        } else if(op==4) {
            if(!q.empty()) {
                printf("队尾元素：%d\n",q.back());
            } else {
                printf("队列为空\n");
            }
        } else if(op==5) {
            printf("队列中元素个数：%d\n",q.size());
        } else if(op==6) {
            printf("队列是否为空：%s\n",q.empty()?"是":"否");
        }
    }
    return 0;
}

---

三、队列的经典应用

1. 广度优先搜索（BFS）

原理：利用队列的先进先出特性，逐层遍历图或树的节点，先访问的节点先扩展。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int g[MAXN][MAXN],vis[MAXN],q[MAXN];
int head,tail;
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        g[u][v]=1;
        g[v][u]=1;
    }
    head=1;
    tail=0;
    int start=1;
    q[++tail]=start;
    vis[start]=1;
    printf("BFS遍历顺序：");
    while(head<=tail) {
        int u=q[head++];
        printf("%d ",u);
        for(int v=1;v<=n;v++) {
            if(g[u][v]&&!vis[v]) {
                q[++tail]=v;
                vis[v]=1;
            }
        }
    }
    printf("\n");
    return 0;
}

2. 二叉树的层序遍历

原理：利用队列按层次输出二叉树的节点，先入队的节点先处理。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
struct Node {
    int data;
    Node* left;
    Node* right;
};
Node* q[MAXN];
int head,tail;
Node* createTree() {
    int x;
    scanf("%d",&x);
    if(x==-1) return NULL;
    Node* p=new Node();
    p->data=x;
    p->left=createTree();
    p->right=createTree();
    return p;
}
int main() {
    Node* root=createTree();
    if(root==NULL) return 0;
    head=1;
    tail=0;
    q[++tail]=root;
    printf("层序遍历：");
    while(head<=tail) {
        Node* cur=q[head++];
        printf("%d ",cur->data);
        if(cur->left!=NULL) {
            q[++tail]=cur->left;
        }
        if(cur->right!=NULL) {
            q[++tail]=cur->right;
        }
    }
    printf("\n");
    return 0;
}

3. 循环队列（约瑟夫环）

原理：用队列模拟报数过程，每报到指定数字的人出队，直到只剩一个人。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int q[MAXN];
int head,tail;
int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    head=1;
    tail=0;
    for(int i=1;i<=n;i++) {
        q[++tail]=i;
    }
    int cnt=0;
    while(head<=tail) {
        cnt++;
        int cur=q[head++];
        if(cnt==k) {
            printf("%d ",cur);
            cnt=0;
        } else {
            q[++tail]=cur;
        }
    }
    printf("\n");
    return 0;
}

4. 优先队列（堆）

原理：优先队列是一种特殊的队列，出队顺序不是按照入队顺序，而是按照优先级（最大或最小）出队。

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> maxHeap;
priority_queue<int,vector<int>,greater<int>> minHeap;
int main() {
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            maxHeap.push(x);
            minHeap.push(x);
            printf("入堆成功：%d\n",x);
        } else if(op==2) {
            if(!maxHeap.empty()) {
                printf("最大堆出堆：%d\n",maxHeap.top());
                maxHeap.pop();
            }
            if(!minHeap.empty()) {
                printf("最小堆出堆：%d\n",minHeap.top());
                minHeap.pop();
            }
        } else if(op==3) {
            if(!maxHeap.empty()) {
                printf("最大堆堆顶：%d\n",maxHeap.top());
            }
            if(!minHeap.empty()) {
                printf("最小堆堆顶：%d\n",minHeap.top());
            }
        } else if(op==4) {
            printf("最大堆大小：%d，最小堆大小：%d\n",maxHeap.size(),minHeap.size());
        }
    }
    return 0;
}

5. 单调队列（滑动窗口最值）

原理：维护一个单调递增或递减的队列，用于在O(n)时间内求出滑动窗口的最值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],q[MAXN];
int head,tail;
int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    head=1;
    tail=0;
    printf("滑动窗口最小值：");
    for(int i=1;i<=n;i++) {
        while(head<=tail&&q[head]<=i-k) {
            head++;
        }
        while(head<=tail&&a[q[tail]]>=a[i]) {
            tail--;
        }
        q[++tail]=i;
        if(i>=k) {
            printf("%d ",a[q[head]]);
        }
    }
    printf("\n");
    head=1;
    tail=0;
    printf("滑动窗口最大值：");
    for(int i=1;i<=n;i++) {
        while(head<=tail&&q[head]<=i-k) {
            head++;
        }
        while(head<=tail&&a[q[tail]]<=a[i]) {
            tail--;
        }
        q[++tail]=i;
        if(i>=k) {
            printf("%d ",a[q[head]]);
        }
    }
    printf("\n");
    return 0;
}

6. 双端队列（deque）

原理：双端队列允许在队列两端进行插入和删除操作，比普通队列更灵活。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int dq[MAXN];
int head,tail;
int main() {
    head=1;
    tail=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            dq[++tail]=x;
            printf("队尾入队：%d\n",x);
        } else if(op==2) {
            scanf("%d",&x);
            dq[--head]=x;
            printf("队头入队：%d\n",x);
        } else if(op==3) {
            if(head<=tail) {
                printf("队头出队：%d\n",dq[head++]);
            }
        } else if(op==4) {
            if(head<=tail) {
                printf("队尾出队：%d\n",dq[tail--]);
            }
        } else if(op==5) {
            if(head<=tail) {
                printf("队头：%d，队尾：%d\n",dq[head],dq[tail]);
            }
        }
    }
    return 0;
}

---

四、队列的常见题型

1. 用栈实现队列

原理：使用两个栈，一个用于入队，一个用于出队，利用栈的后进先出特性模拟队列的先进先出。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk1[MAXN],stk2[MAXN];
int top1,top2;
int main() {
    top1=0;
    top2=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            stk1[++top1]=x;
            printf("入队：%d\n",x);
        } else if(op==2) {
            if(top2==0) {
                while(top1>0) {
                    stk2[++top2]=stk1[top1--];
                }
            }
            if(top2>0) {
                printf("出队：%d\n",stk2[top2--]);
            } else {
                printf("队列为空\n");
            }
        } else if(op==3) {
            if(top2==0) {
                while(top1>0) {
                    stk2[++top2]=stk1[top1--];
                }
            }
            if(top2>0) {
                printf("队头：%d\n",stk2[top2]);
            } else {
                printf("队列为空\n");
            }
        }
    }
    return 0;
}

2. 用队列实现栈

原理：使用两个队列，一个用于存储元素，另一个用于辅助操作，利用队列的先进先出特性模拟栈的后进先出。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int q1[MAXN],q2[MAXN];
int h1,t1,h2,t2;
int main() {
    h1=1;t1=0;
    h2=1;t2=0;
    int n,op,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&op);
        if(op==1) {
            scanf("%d",&x);
            q2[++t2]=x;
            while(h1<=t1) {
                q2[++t2]=q1[h1++];
            }
            h1=1;t1=0;
            while(h2<=t2) {
                q1[++t1]=q2[h2++];
            }
            h2=1;t2=0;
            printf("入栈：%d\n",x);
        } else if(op==2) {
            if(h1<=t1) {
                printf("出栈：%d\n",q1[h1++]);
            } else {
                printf("栈为空\n");
            }
        } else if(op==3) {
            if(h1<=t1) {
                printf("栈顶：%d\n",q1[h1]);
            } else {
                printf("栈为空\n");
            }
        }
    }
    return 0;
}

---

五、队列的总结

特性	数组实现	STL实现
时间复杂度	O(1)	O(1)
空间限制	固定大小	动态扩展
操作直观	需要手动管理head和tail	封装完善
适用场景	已知最大大小，需要循环队列	大小不确定

队列的核心思想：

1. 先进先出是根本特性
2. 适用于需要层次遍历的场景
3. 常用于广度优先搜索（BFS）
4. 线程安全的队列常用于生产者-消费者模式
5. 优先队列用于任务调度、最短路径等算法

队列 vs 栈对比：

对比项	栈	队列
操作原则	先进后出（LIFO）	先进先出（FIFO）
操作端	只在一端操作	在两端操作
应用场景	递归、回溯、表达式求值	BFS、缓存、任务调度
实现方式	数组、链表	数组、链表、循环队列

注意事项：

1. 使用数组实现时注意head和tail的边界条件
2. 循环队列中判断空和满的条件要准确
3. BFS时注意标记已访问节点避免重复
4. 单调队列适合处理滑动窗口问题
5. 优先队列默认是大顶堆，使用greater<int>()可以转为小顶堆