STL专项：queue 队列

queue

queue提供了先进先出（First In First Out）的数据结构。队列在尾部添加元素，在头部删除元素。

常见的应用有：模拟、约瑟夫环、bfs、分支限界搜索、单调队列等算法。

创建队列

queue<int> q;//创建一个 int 类型的队列

入队（添加元素）

//使用 push() 函数将元素添加到队列的尾部。

q.push(10)//将10添加到队列尾部

q.push(20)

q.push(30)

出队（删除元素）

//使用 pop() 函数删除队列的头部元素

q.pop();//删除头部元素，即10

访问队列头部元素

//使用 front() 函数获取队列头部元素的引用

int frontElement = q.front();// frontElement 现在是20

访问队列尾部元素

//使用 back() 函数获取队列尾部元素的引用

int backElement = q.back();// backElement 现在是30

检查队列是否为空/获取队列大小

//使用 empty() 函数检查队列是否为空

if(q.empty())//队列为空

if(q.size())//队列不为空

手写队列

//queue和stack一样不允许遍历

int q[N];

int qh=1,qt=0;//qh队头，qt队尾

//入队

q[++qt]=x;

//出队

qh++;

//大小

qt-qh+1

约瑟夫环

约瑟夫环（easy） | 星码StarryCoding 算法竞赛新手村

代码

#include<bits/stdc++.h> using namespace std; void solve(){ int n,m;cin>>n>>m; queue<int> q; for(int i=1;i<=n;i++){ int x;cin>>x; q.push(x); } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ int x=q.front(); q.pop(); q.push(x); } q.pop(); } cout<<q.front()<<'\n'; } int main(){ int _;cin>>_; while(_--) solve(); return 0; }

区别对待

区别对待 | 星码StarryCoding 算法竞赛新手村

代码

#include<bits/stdc++.h> using namespace std; const int N = 1e5+9; void solve(){ char s[N];cin>>s+1; int n=strlen(s+1); queue<char> q1,q2; for(int i=1;i<=n;i++){ if(s[i]>='0'&&s[i]<='9') q1.push(s[i]); else q2.push(s[i]); } while(q1.size()){ cout<<q1.front(); q1.pop(); } cout<<'#'; while(q2.size()){ cout<<q2.front(); q2.pop(); } cout<<endl; } int main(){ int _;cin>>_; while(_--) solve(); return 0; }