[AcWing] 829. 模拟队列

算法标签 队列

题目简叙

思路

后进先出的原则
我们用 st,ed两个变量表示队列的对头和队尾

push

	queue[++ed]=tmpn;

插入时，队尾开始移动并添加数据
pop

	start++;

弹出队头数据时，我们用指针略过当前数据表示弹出
于是队头++，这样我们就不会扫描到队头元素，相当于弹出
empty

	cout<<queue[start]<<endl;

直接查询队头元素
query

	cout<<(start>ed?"YES":"NO")<<endl;

如果队头指针超过队尾指针，表明没有任何数据

值得注意的是队列初始化的时候，队尾元素下标应该是-1，
这样第一次插入下标就会变为0
第一次弹出也可以正常显示1>0，队伍变为没有元素
第一次返回队头元素也可以直接用下标0返回
如果是空值，就直接能用（初始化队头的）0>（初始对尾的）-1返回

代码

数组模拟

#include<iostream>
#include<string>

using namespace std;

const int N = 100000 +10;
int queue[N];
int start,ed=-1;

int main(){
    int n;
    cin>>n;
    
    string op;
    int tmpn;
    while(n--){
         cin>>op;
         if(op=="push"){
             cin>>tmpn;
             queue[++ed]=tmpn;
         }
         else if(op=="pop"){
             start++;
         }
         else if(op=="query"){
             cout<<queue[start]<<endl;
         }
         else if(op=="empty"){
             cout<<(start>ed?"YES":"NO")<<endl;
         }
    }
    return 0;
}

STL

#include<iostream>
#include<string>
#include<queue>

using namespace std;

const int N = 100000 +10;
queue<int>q;

int main(){
    int n;
    cin>>n;
    
    string op;
    int tmpn;
    while(n--){在这里插入代码片
         cin>>op;
         if(op=="push"){
             cin>>tmpn;
             q.push(tmpn);
         }
         else if(op=="pop"){
             q.pop();
         }
         else if(op=="query"){
             cout<<q.front()<<endl;
         }
         else if(op=="empty"){
             cout<<(q.empty()?"YES":"NO")<<endl;
         }
    }
    return 0;
}