STL初步：栈，队列和优先队列

一时失言乱红尘 2022-11-27 12:15 226阅读 0赞

### 集合栈计算机(The SetStack Computer） ###

有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：

*  PUSH：空集“\{\}”入栈
 *  DUP：把当前栈顶元素复制一份后再入栈
 *  UNION：出栈两个集合，然后把两者的并集入栈
 *  INTERSECT：出栈两个集合，然后把二者的交集入栈
 *  ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈

每次操作后，输出栈顶集合的大小（即元素个数）。例如栈顶元素是A=\{ \{\}， \{ \{\}\} \}， 下一个元素是B=\{ \{\}， \{ \{ \{\}\}\} \}，则：

*  UNION操作将得到\{ \{\}， \{ \{\}\}， \{ \{ \{\}\}\} \}，输出3.
 *  INTERSECT操作将得到\{ \{\} \}，输出1
 *  ADD操作将得到\{ \{\}， \{ \{ \{\}\}\}， \{ \{\}， \{ \{\}\} \} \}，输出3.

样例输入

6
    PUSH
    PUSH
    UNION
    PUSH
    PUSH
    ADD

样例输出

0
    0
    0
    0
    0
    1

#include<set>
    #include<stack>
    #include<iostream>
    #include<map>
    #include<vector>
    #include<algorithm> 
    using namespace std;
    typedef set<int> Set;
    map<Set,int> IDcache; //把集合映射为id 
    vector<Set> SetCache; //根据id取集合 
    stack<int> s;  //题目中的栈 
    int ID(Set x)  //查找给定集合的id。如果找不到，分配一个新id 
    {  
        if(!IDcache.count(x))
        { 
            SetCache.push_back(x);  //添加新集合 
            IDcache[x]=SetCache.size()-1;
        }
        return IDcache[x];
    }
    int n;
    int main()
    { 
        cin>>n;
        while(n--)
        { 
            string exec;
            cin>>exec;
            if(exec[0] == 'P') s.push(ID(Set()));
            else if(exec[0] == 'D') s.push(s.top());
            else
      	{ 
                Set x1 = SetCache[s.top()];
                s.pop();
                Set x2 = SetCache[s.top()];
                s.pop();
                Set x;
                if(exec[0] == 'U') set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));//!!!inserter
                if(exec[0] == 'I') set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));//!!!inserter
                if(exec[0] == 'A'){ 
                    x=x2;
                    x.insert(ID(x1));
                }
                s.push(ID(x));
            }
            cout<<SetCache[s.top()].size()<<endl;
        }
    }

队列是符合“先进先出”原则的“公平队列”。  
STL队列定义在头文件`<queue>`中，可用`queue<int>s`方式定义，用push()和pop()进行元素的入队和出队操作，front（）取队首元素，但不删除。

### 团体队列（Team Queue) ###

有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，则他会排到长队的队尾。  
输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）

*  ENQUEUE x：编号为x的人进入长队
 *  DEQUEUE： 长队列队首出队
 *  STOP： 停止模拟

对于每一个DEQUEUE指令，输出出对人的编号.

#include<cstdio>
    #include<queue> 
    #include<map>
    using namespace std;
    const int maxt = 1000 + 10;
    int main()
    { 
        int t, kase = 0;
        while (scanf("%d", &t) == 1 && t) 
        {          
      	map<int, int>team;         //记录所有人的团队编号 
      	for (int i = 0; i<t; i++)  //team[x]表示编号为x的人所在的团队编号 
      	{ 
                int n, x;
                scanf("%d", &n);   
                while (n--) 
                { 
        		scanf("%d", &x);
        		team[x] = i;
                }
            }
            printf("Scenario #%d\n", ++kase);
            queue<int>q, q2[maxt];  //模拟 
            for(;;)
            { 
       	     int x;
       	     char cmd[10];
       	     scanf("%s", cmd);
                 if (cmd[0] == 'S')
                 { 
        		  break;
                 }
                 else if (cmd[0] == 'D') 
                 { 
        		  int t = q.front();              
                      printf("%d\n", q2[t].front()); //打印首元素
                      q2[t].pop();   //首元素出队（先进先出） 
                      if (q2[t].empty()) q.pop();  //团队t全体出队列 
                  }
                  else if (cmd[0] == 'E') 
                 {  
        		 scanf("%d", &x);
        	      	 int t = team[x]; 
        		 if (q2[t].empty()) //团队t进入队列 
        		 { 
         			q.push(t);   
        		 } 
        		 q2[t].push(x);         
       	     }
      	}
      	printf("\n");
        }
        return 0;
    }

###### 优先队列 ######

先出队列是队列中优先级最高的元素，STL中用`priority_queue<int>pq`来声明，出队方法为top()。  
自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。  
例如，要实现一个“个位数大的整数优先级反而小”的优先队列，可以定义一个结构体cmp，重载“（）”运算符，用`priority_queue<int,vector<int>,cmp> pq`的方式定义。

struct cmp
    { 
    	bool operator() (const int a,const int b)const		//a的优先级比b小时返回true
    	{ 
    		return a%10>b%10;
    	}
    };

简便定义方法：

priority_queue<int,vector<int>,great<int> >pq

注：可用push()和pop()进行元素的入队和出队操作，top()取队首元素，但不删除。

### 丑数 ###

丑数指不能被2，3，5以外其他素数整除的数。把丑数从小到大排列起来，结果如下：  
1，2，3，4，5，6，8，9，10，12，15…  
求第1500个丑数。

/*最小的丑数是1，而对于任意丑数，2x,3x,5x也都是丑数。可以用一个优先队列保存所有已生成的丑数，每次取出最小的丑数，生成3个新的丑数。 */
    #include<iostream>
    #include<vector>
    #include<queue>
    #include<set>
    using namespace std;
    typedef long long ll;
    const int coeff[3]={ 2,3,5};
    int main()
    { 
        priority_queue<ll,vector<ll>,greater<ll> > pq;
        set<ll> s;
        pq.push(1);
        s.insert(1);
        for(int i=1;;i++)
        { 
      	ll x=pq.top();
      	pq.pop();
      	if(i==1500)
      	{ 
                cout<<"The 1500'th ugly number is "<<x<<".\n";
                break;
      	}
      	for(int j=0;j<3;j++)
      	{ 
                ll x2=x*coeff[j];
                if(!s.count(x2))
                { 
        		s.insert(x2);
        		pq.push(x2); 
                }
      	}
        }
        return 0;
     }