双栈队列
取队列中的最小值的双栈队列.
- struct Queue {
- static const int MAXN = 1000000;
- static const int INF = 1061109567;
- int s1[MAXN + 5], s2[MAXN + 5];
- int s1top, s2top, s1min;
- void Clear() {
- s1top = 0;
- s2top = 0;
- s2[0] = INF;
- s1min = INF;
- }
- void Push(int x) {
- s1[++s1top] = x;
- s1min = min(s1min, x);
- }
- void Pop() {
- if(s2top)
- --s2top;
- else {
- while(s1top)
- s2[++s2top] = min(s2[s2top - 1], s1[s1top--]);
- --s2top;
- s1min = INF;
- }
- }
- int Size() {
- return s1top + s2top;
- }
- int Min() {
- return min(s2[s2top], s1min);
- }
- };
来源: http://www.bubuko.com/infodetail-3337782.html