栈与队列

最新推荐文章于 2024-11-24 10:05:38 发布

季圣斌

最新推荐文章于 2024-11-24 10:05:38 发布

阅读量176

点赞数 1

分类专栏： STL

本文链接：https://blog.csdn.net/coollend/article/details/111567181

版权

STL 专栏收录该内容

1 篇文章

订阅专栏

STL 栈与队列

第一题：Blah数集
题目：
对于以a为基的集合Ba定义如下：
(1) 是集合a的Ba基，且a是Ba的第一个元素；
(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba 中；
(3)没有其他元素在集合Ba 中了。
想知道如果将集合Ba中元素按照升序排列，第n个元素会是多少？
**分析：**我们知道一个x可以产生出2x+1和3x+1那么每次的第一个2x+1和第二个2x+1比大小，小的放前面，一样3x+1也要比，所以放到n个数是就可以了。
代码：

#include <bits/stdc++.h>
using namespace std;
queue<int> q1;
queue<int> q2;
int main()
{
	int n,m;
	int x;
	while(cin>>n>>m)
	{
		x=n; 
		q1.push(x*2+1);
		q2.push(x*3+1);
		for(int i=1;i<m;i++)
		{
			if(q1.front()<q2.front())
			{
				x=q1.front();
				q1.pop();
			}
			else if(q1.front()==q2.front())
			{
				x=q1.front();
				q1.pop();
				q2.pop();
			}
			else
			{
				x=q2.front();
				q2.pop();
			}
			q1.push(x*2+1);
			q2.push(x*3+1);
		}
		cout<<x<<endl;	 
		if(!q1.empty())
		{
			while(!q1.empty())
			{
				q1.pop();
			}
		}
		if(!q2.empty())
		{
			while(!q2.empty())
			{
				q2.pop();
			}
		}
	}
    return 0;
}

第二题：奇怪的电梯
**题目：**大楼的每一层楼都可以停电梯，而且第 i 层楼（1<=i<=N）上有一个数字Ki（0<=Ki<=N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5 代表了 Ki（K1=3,K2=3,……），从一楼开始。在一楼，按“上”可以到 4 楼，按“下”是不起作用的，因为没有-2 楼。那么，从 A 楼到 B 楼至少要按几次按钮呢？
**分析：**从这个数开始，两个方向，上和下。上/下：队列这个数加/减上这个数，并且不大于范围，判断是否是B，是就输出按了几次，不是就入队列。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef struct
{
	int step;
	int floor;
} dt;
queue<dt>lift;
bool flag[2000],f;
int main()
{
	int n,a,b,k[2000];
	dt s,e;
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)
	{
		cin>>k[i];
	}
	s.step=0;s.floor=a;
	lift.push(s);
	while(!lift.empty())
	{
		s=lift.front();
		lift.pop();
		if(s.floor==b)
		{
			cout<<s.step<<endl;
			f=1;
			break;
		}
		if(s.floor+k[s.floor]<=n&&!flag[s.floor+k[s.floor]])
		{
			e.floor=s.floor+k[s.floor];
			e.step=s.step+1;
			flag[e.floor]=1;
			lift.push(e); 
		}
		if(s.floor-k[s.floor]>=1&&!flag[s.floor-k[s.floor]])
		{
			e.floor=s.floor-k[s.floor];
			e.step=s.step+1;
			flag[e.floor]=1;
			lift.push(e); 
		}
	}
	if(f==0) cout<<"-1"<<endl;
	return 0;
}

第三题：字符串匹配
题目： 字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该输出NO。
分析： 可以用优先级下手，判断是否先是大的优先级，否则就判断下一个小的优先级，然后看ascall码表
详见:Ascall码表，发现任何括号都有规律，这样就跟着优先级判断就行了。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,i;
char c,str[300],s[300];
int main()
{
    cin>>m;
    s[0]=127;
    while(m--)
    {
        cin>>str;
        i=n=0;
        while(c=str[i++])
        {
            if(c=='<') s[++n]=c;
            else if(c=='('&&s[n]!='<') s[++n]=c;
                 else if(c=='['&&s[n]>=c) s[++n]=c;
                      else if(c=='{'&&s[n]>=c) s[++n]=c;
                           else if((c+s[n])/2+1==c) n--;
                                else
                                {
                                    n=-1;
                                    break;
                                }
        }
        if(n==0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}`

第四题：计算
**题目：**小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)。
分析： 首先要维护两个栈，我这里用数组模拟栈，其次括号优先级和运算符优先级，再是各种运算符。
代码：

#include<bits/stdc++.h>
using namespace std;
int number[301];   
char symbol[301]; 
string s,t;      
int i,j,p;   
 
int POW(int a,int b)  
{
	int j,t=1;
	for(j=1;j<=b;j++) t*=a;
	return t;
}
 
void push()       
{
    p++;
    symbol[p]=s[i];
}
 
void pop() 
{
    p--;                 
    switch(symbol[p+1])  
    {
         case '+' : number[p]+=number[p+1]; break;
         case '-' : number[p]-=number[p+1]; break;
         case '*' : number[p]*=number[p+1]; break;
         case '/' : number[p]/=number[p+1]; break;  
         case'^'  : number[p]=POW(number[p],number[p+1]);break;		        
    }
}
bool can()         
{ 
    if((s[i]=='+' || s[i]=='-') && (symbol[p]!='(' )) return true; 
    if((s[i]=='*' || s[i]=='/') && (symbol[p]=='^' ||symbol[p]=='*' || symbol[p]=='/')) return true;
    if(s[i]=='^' && symbol[p]=='^') return true;
    return false;   
}

int main()
{
    cin>>s;
    s="("+s+")";  
    i=0; p=0;
     
    while(i<s.size())      
    {
        while(s[i]=='(' )  
        {
            push();         
            i++;
        } 
        
        if(s[i]>='0' && s[i]<='9')
        {
           j=i;
           do             
           {                   
              i++;
           }while(s[i]>='0' && s[i]<='9');
     
           t=s.substr(j,i-j);                             
           sscanf(t.c_str(),"%d",&number[p]);   
        }               
        if(s[i]==')')  
        {
            while(symbol[p]!='(') pop();  
            p--;                       
            number[p]=number[p+1];       
        }
        
        else                    
        {
            while(can()) pop();  
            push();              
        }
        i++;                      
    }
    cout<<number[0]<<endl;        
    return 0;
}