STL初步：栈，队列和优先队列-蒲公英云

集合栈计算机(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;
 }