8 solutions

  • 1
    @ 2022-4-25 22:05:53

    用数组模拟

    #include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,p[N];
vector<int>erro;
int pl=N/2,pr=N/2-1;
int main(){
	cin>>n;
	string op;
	int x;
	for(int i=1;i<=n;i++){
		cin>>op;
		if(op=="LIN"){
			cin>>x;
			p[--pl]=x;
		}else if(op=="RIN"){
			cin>>x;
			p[++pr]=x;
		}else if(op=="LOUT"){
			if(pl<=pr)pl++;
			else erro.push_back(i);
		}else{
			if(pl<=pr)pr--;
			else erro.push_back(i);
		}
	}
	for(int i=pl;i<=pr;i++)
		cout<<p[i]<<" ";
	cout<<endl;
	for(int i:erro)
		cout<<i<<" "<<"ERROR"<<endl;
	return 0;
}
    • 1
      @ 2022-1-2 22:20:18 
      #include <bits/stdc++.h>
using namespace std;
int main()
{
	string a="LIN",b="RIN",c="LOUT",d="ROUT",m;
	int n,x;
	cin>>n;
	int temp=n; 
	deque <int> s;
	queue <int> p;
	while(n--)
	{
		cin>>m;
		if(m==a)
		{
			cin>>x;
			s.push_front(x);
		}
		else if(m==b)
		{
			cin>>x;
			s.push_back(x);
		}
		else if(m==c)
		{
			if(!s.empty()) 
			{
			s.pop_front();
		    }
		    else p.push(temp-n+1);
		}
		else if(m==d)
		{
		   if(!s.empty()) 
			{
		     s.pop_back();
		    }
		    else p.push(temp-n);	
		}
	} 
	while(!s.empty())
	{
		cout<<s.front();
		s.pop_front();
		s.empty()?cout:cout<<" "; 
	}
	cout<<endl;
	while(!p.empty())
	{
		cout<<p.front();
		p.pop();
		cout<<" ERROR"<<endl; 
	}
	
	return 0;
}
      • 1
        @ 2022-1-2 11:19:47

        这里用到的是deque，并且需要一个数组来存储其错误的步骤

        #include<bits/stdc++.h>
typedef long long ll;
using namespace std;	
string s;//使用string能够直接比较字符串，比用char方便很多；
int a[100010];
int main()
{
	int t,cnt=0;
	cin>>t;
	deque<int> q;
	for(int i=1;i<=t;i++)
	{
		cin>>s;
		if(s=="LIN")
		{
			int n;
			cin>>n;
			q.push_front(n);
		}
		if(s=="RIN")
		{
			int n;
			cin>>n;
			q.push_back(n);
		}
		if(s=="ROUT")
		{
			if(q.empty()) a[cnt++]=i;//储存错的步骤
			else q.pop_back();
		}
		if(s=="LOUT")
		{
			if(q.empty()) a[cnt++]=i;
			else q.pop_front();
		}
	}
	while(!q.empty())
	{
		cout<<q.front()<<" ";
		q.pop_front();
	}cout<<endl;
	for(int i=0;i<cnt;i++)
	{
		cout<<a[i]<<" "<<"ERROR"<<endl; 
	}
	return 0;
}
        • 0
          @ 2022-3-29 14:58:04

          不知道有deque,手写的倒序queue解决

          #include <bits/stdc++.h>
using namespace std;

queue<int> q1,q2;

int main(){
    int n,total,num,error[10005] = {0};
    cin>>n;
    total = n;
    while(n--){
        string ask;
        cin>>ask;
        if(ask == "LIN"){
            cin>>num;
            q2.push(num);
        }
        else if(ask == "RIN"){
            cin>>num;
            q1.push(num);
        }
        else if(ask == "LOUT"){
            if(q2.empty() == false){
                int chance = q2.back();
                while(q2.front() != chance){
                    num = q2.front();
                    q2.pop();
                    q2.push(num);
                }
                q2.pop();
                continue;
            }
            if(q1.empty() == false){
                q1.pop();
                continue;
            }
            error[total - n] = 1;
        }
        else if(ask == "ROUT"){
            if(q1.empty() == false){
                int chance = q1.back();
                while(q1.front() != chance){
                    num = q1.front();
                    q1.pop();
                    q1.push(num);
                }
                q1.pop();
                continue;
            }
            if(q2.empty() == false){
                q2.pop();
                continue;
            }
            error[total - n] = 1;
        }
        else{
            error[total - n] = 1;
        }
    }

    int size = q2.size();
    int left[size] = {0};
    for(int i = size - 1 ; i >= 0 ; i--){
        left[i] = q2.front();
        q2.pop();
    }
    for(int i = 0 ; i < size ; i++){
        cout<<left[i]<<" ";
    }
    while(q1.empty() == false){
        cout<<q1.front()<<" ";
        q1.pop();
    }
    cout<<endl;
    for(int i = 1 ; i <= total ; i++){
        if(error[i] == 1){
            cout<<i<<" ERROR"<<endl;
        }
    }
    return 0;
}
          • 0
            @ 2022-3-27 20:33:56

            双向队列的基本操作

            #include<bits/stdc++.h>
#include<string> 
int t,x;
using namespace std;
int main(){
	std::ios::sync_with_stdio(false);
	deque <int> num;//操作双向队列 
	queue <int> error;//记录error命令行数的队列
	cin>>t;
	for(int i=1;i<=t;i++){
		string order;
		cin>>order; 
		if(order=="LIN"){//从头部入队一个元素 
			cin>>x;
			num.push_front(x);
		}else if(order=="RIN"){//从尾部入队一个元素
			cin>>x;
			num.push_back(x);
		}else if(order=="ROUT"){//从头部出队一个元素
			if(!num.empty())
				num.pop_back();
			else
				error.push(i);	
		}else if(order=="LOUT"){//从尾部出队一个元素
			if(!num.empty())
				num.pop_front();
			else
				error.push(i);
		}
	}
	while(!num.empty()){
		cout<<num.front()<<" ";
		num.pop_front();
	}
	cout<<endl;
	while(!error.empty()){
		cout<<error.front()<<" "<<"ERROR"<<endl;;
		error.pop();
	}
	return 0;
}
            • 0
              @ 2022-1-14 15:09:50 
              #include<queue>
#include<deque>
#include<iostream>
#include<string.h>
using namespace std;

int main()
{
	int n,a;
	scanf("%d",&n);
	char arr[10];
	deque<int>que;
	int num[10007];
	for(int i = 1; i <= n; i++)
	{
		scanf("%s",arr);
		if(strcmp(arr,"LIN") == 0)
		{
		scanf("%d",&a);
		que.push_front(a);	
		}
		else if(strcmp(arr,"RIN") == 0)
		{
			scanf("%d",&a);
			que.push_back(a);
		}
		else if(strcmp(arr,"ROUT") == 0)
		{
			if(!que.empty())
			{
				que.pop_back();
			}
			else
			{
				num[i]++;
			}
		}
		else if(strcmp(arr,"LOUT") == 0)
		{
			if(!que.empty())
			{
				que.pop_front();
			}
			else
			{
				num[i]++;
			}
		}
		
	}
	while(!que.empty())
	{
		printf("%d ",que.front());
		que.pop_front();
	}
	puts("");
	for(int i = 1;i <= n;i ++)
	{
		if(num[i] == 1)
		{
			printf("%d ERROR\n",i);
		}
	}
	return 0;
}
              • 0
                @ 2022-1-3 16:20:24

                一道入门的双向队列，没啥思路，就是模拟

                #include<stdio.h>
#include<deque>
#include<cstring>
using namespace std;
const int N=1e6+7;
deque<int>s; 
bool v[N];
char a[N];
int n;
int main(){
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++){
		scanf("%s",&a);
		if(s.empty()){
			if(a[1]=='O')v[i]=true;
			else {
				int h;
				scanf("%d",&h);
				if(a[0]=='L') s.push_front(h);
				else s.push_back(h);//可以在每段最后面加一个输出队首队尾用于调试
			}
		}
		else{
			if(a[1]=='O'){
				if(a[0]=='L') s.pop_front();
				else s.pop_back();
			}
			else {
				int h;
				scanf("%d",&h);
				if(a[0]=='L') s.push_front(h);
				else s.push_back(h);
			}
		}
	}
	int t=0;
	for(int i=1;i<=s.size()+t;i++){
		printf("%d ",s.front());
		s.pop_front();
		t++; 
	}
	printf("\n");
	for(int i=1;i<=n;i++)if(v[i])printf("%d ERROR\n",i);
	return 0;
}
                • 0
                  @ 2022-1-2 9:56:42

                  主要不会就上网查资料，多写几遍，就应该懂了

                  #include <cstdio>
#include <cstring>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
const int N=1e6+7;
int main()
{
    deque<int>q;//创建一个双向队列 
    while(!q.empty())//将这个双向队列清空
        q.pop_front();
    int n,a,i,m[N]= {0};
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        char s[10];
        scanf(" %s",s);
        if(!strcmp(s,"LIN"))//将输入的字符串与“LIN”进行匹配，成功就进行下列操作
        {
            scanf("%d",&a);
            q.push_front(a);//将输入的数从左边放入，也就是从头部放入
        }
        else if(!strcmp(s,"RIN"))//与上面类似
        {
            scanf("%d",&a);
            q.push_back(a);//从右边放入，也就是从尾部放入
        }
        else if(!strcmp(s,"LOUT"))
        {
            if(!q.empty())
                q.pop_front();//从左边（头部）删除
            else
                m[i]++;//记录位置
        }
        else if(!strcmp(s,"ROUT"))
        {
            if(q.empty())
                m[i]++;   
            else
                q.pop_back();//从右边（尾部）删除
        }
    }
    printf("%d",q.front()); //输出队列中的数
    q.pop_front();//同时删除
    while(!q.empty())//当队列不为空时继续输出然后删除直到队列中为空
    {
        printf(" %d",q.front());
    q.pop_front();
    }
    printf("\n");
    for(i=1; i<=n; i++)//输出不合法的操作
        if(m[i])
            printf("%d ERROR\n",i);
    return 0;
}
                  • 1

                  【入门】双向队列

                  Information

                  ID
                  1125
                  Time
                  1000ms
                  Memory
                  128MiB
                  Difficulty
                  6
                  Tags
                  # Submissions
                  136
                  Accepted
                  43
                  Uploaded By
                  1. About
                  2. Contact Us
                  3. Privacy
                  4. Terms of Service
                  5. Copyright Complaint
                  6. Language
                  7. Legacy mode
                  8. Theme
                  2. 蜀ICP备2021003932号-1
                  3. Worker 0, 58ms
                  4. Powered by Hydro v4.18.0 Community