队栈

news/2024/7/23 23:21:43 标签: c++, 算法

题目描述

Yazid 是一名 OI 初学者。他最近在研究基础数据结构:队列和栈。某天,Yazid 脑洞大开,发明了一种叫做“队栈”的数据结构。众所周知,队列是先进先出的数据结构,而栈是先进后出的数据结构。而 Yazid 发明的队栈则同时支持查询并删除其中最早被插入的元素和最晚被插入的元素。Yazid 有一个初始为空的队栈和一个黑盒(这是一个存放数字的盒子),接下来,他要依次执行 Q 个操作。操作分为 4 种:
1. push:将一个非负整数加入队栈。
2. pop_queue:找出队栈中最早被插入的元素,将其取出放入黑盒,并从队栈中删除。
3. pop_stack:找出队栈中最晚被插入的元素,将其取出放入黑盒,并从队栈中删除。
4. print:将黑盒中的所有数取出,并按被放入的先后顺序从左到右排列得到一个整数。
例如:
黑盒中依次被放入了 0, 23, 330, 6,
那么获得并打印的整数即是 233306。
由于 Yazid 懒得在每次 push 操作时想插入的数,因此他提前写好了一个长度为 n 的插入序列 A(下标从 1 开始)。在接下来的所有 push 操作中,Yazid 会依次地、循环地将这些数加入队栈。具体来说:
• 在首次 push 操作时,Yazid 会将 A 1 加入队栈。
• 在之后的每次 push 操作中,假设 Yazid 上次 push 时加入的数是 A i ,则本次他会将 A i+1 加入队栈。特别地,如果 i = n,则 Yazid 本次会将 A 1 加入队栈。
请你依次输出 Yazid 通过 print 操作获得的整数。

输入格式

从文件 staqueue.in 中读入数据。
第 1 行一个整数 n,表示插入序列的长度。
第 2 行 n 个用单个空格隔开的非负整数 A 1 , A 2 , . . . , A n ,描述插入序列。
第 3 行一个整数 Q,表示操作数目。
第 4 行 Q 个紧挨着的 1 ∼ 4 之间的数字,依次描述每个操作,每个数字表示操作
的编号(各操作对应的编号见题目描述)
。
• 保证所有操作的合法性。即保证:
– 执行任意 pop_queue 和 pop_stack 操作时队栈不为空。
– 执行任意 print 操作时黑盒不为空。

输出格式

对于所有 print 操作,输出一行一个整数,表示该 print 操作中 Yazid 获得的数。

样例输入#1

1 2

1112324

样例输出#1

112

样例输入#2

0 23 330 6

121313124134

样例输出#2

23306

参考代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

vector <int> v;
queue <int> c;
vector <int> ans;

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
	{
    	int x;
		cin>>x;
		c.push(x);
	}

	int Q;
	cin>>Q;
	string s;
	cin>>s;

	for(int i = 0; i < Q; i++)
	{
		int x = s[i] - '0';
		if(x == 1)
		{
			v.push_back(c.front());
			int t = c.front();
			c.pop();
			c.push(t);
		}
		else if(x == 2)
		{
		    ans.push_back(*(v.begin()));
            v.erase(v.begin());
        }
        else if(x == 3)
		{
            ans.push_back(*(v.end() - 1));
            v.erase(v.end() - 1);
		}
		else
		{
			bool flag = false;

			for(vector<int>::iterator iter = ans.begin(); iter != ans.end(); iter++)
			{
				if(*iter != 0)
				{
					flag = true;
					break;
				}
			}

			if(flag)
			{
				bool f = false;
	            for(vector<int>::iterator iter = ans.begin(); iter != ans.end(); iter++)
				{
	            	if(*iter != 0)
						f = true;
	            	if(f)
						cout<<*iter;
				}
			}
			else
				cout<<0;

			cout<<endl;
			ans.clear();
        }
	}

    return 0;
}