练习:STL_stake和queue的运用

🍊🍊新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问 QQ号， 小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时 小哈也告诉了小哼解密规则。规则是这样的：首先将第 1个数删除，紧接着将第 2个数放到 这串数的末尾，再将第 3个数删除并将第 4个数放到这串数的末尾，再将第 5个数删除…… 直到剩下后一个数，将后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一 起就是小哈的 QQ啦。现在你来帮帮小哼吧。

样例输入：

9

6 3 1 7 5 8 9 2 4

样例输出：

6 1 5 9 4 7 2 8 3

#include<iostream>
#include<queue>

using namespace std;

int main()
{
	queue<int> a, b;
	int n,m;
	cin>>n;
	for (int i = 0; i < n; i++)
	{//入队n个元素
	cin>>m;
		a.push(m);
	}
	while (!a.empty())
	{//解密规则
		b.push(a.front());
		a.pop();
		a.push(a.front());
		a.pop();
	}
	while (!b.empty())
	{//输出b队
		cout << b.front()<<" ";
		b.pop();
	}
	cout << endl;

	return 0;
}

测试:


例2：判断回文字符串（栈）

🍊🍊所谓回文字符 串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回 文，但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。

方法一:输入一个字符串，找出中间点，然后把中间点之前的元素全部压入栈中，后续用一个循环来跟后面的字符进行对比。

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main()
{
	string str;
	cin>>str;
	stack<char> s;
	int mid=str.size()/2-1;//得到中间那个数的下标
	int next;
	if(str.size()%2==0)
	{//得到n为偶数时next的值 
		next=mid+1;
	}
	else
	{//得到n为奇数时next的值 
		next=mid;
	}
	for(int i=0;i<=mid;i++)
	{//入栈 
		s.push(str[i]); 
	 }
	for(int i=next;i<str.size();i++)
	{//比较 
		if(s.top()==str[i])
		{
			s.pop();
		}
		else
		{
			break;
		}
	 }
	if(s.empty())
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

方法二：
主要思路是:将字符串依次压入栈中,利用栈的先进后出(可以将字符串逆转),依次读栈顶,并与字符串比较。

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main()
{
	string a;
	stack<char> s;
	cin>>a;
	int l=a.size();
	for(int i=0;i<l;i++)
	{
		s.push(a[i]);
	}
	for(int i=0;i<l;i++)
	{
		if(s.top()==a[i])
		{
			s.pop();
		}
		else
		{
			cout<<"No";
			break;
		}
	}
	if(s.empty())
	{
	cout<<"Yes"<<endl;		
	}
	return 0;
}

例3:判断回文字符串。（栈）

输入字符串,遇到"(“或者”[“就入栈,遇到”)“或者”]"就与栈顶的字符进行对比,若相等删除栈顶元素,不等则退出,如此循环。emmm,一定要记得加falg标志,如果直接用栈是否空来做结果判断会不够全面。

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main()
{
	int N;
	cin>>N;
	while(N--)
	{
	string str;
	stack<char> s; 
	cin>>str;
	int l=str.size();
	bool flag=true;//定义flag是为了标记失败的情况 
	for(int i=0;i<l;i++)
	{
		flag=true;
		if(str[i]=='('||str[i]=='[')
		{//将（和[压栈 
			s.push(str[i]);
		}

		else if(str[i]==')')
		{
			if(!s.empty() && '(' == s.top())
			{//如果和栈顶元素为'(' 
				s.pop();
			}
			else
			{
				flag=false; 
				break;
			}
		}
		
		else if(str[i]==']')
		{
			if(!s.empty() && '['==s.top())
			{
				s.pop();
			}
			else
			{
				flag=false; 				
				break;
			}
		}		
	}
	if(s.empty()&& flag)
	{//如果空 ,并且flsg为true. 
		cout<<"Yes"<<endl;
	}
	else
	{//如果非空 
		cout<<"No"<<endl;
	}				
	} 
	return 0;
}