HDU5818 - 合并栈操作

题设

【问题描述】

栈是一种具有后进先出的数据结构。可合并栈是支持“merge”操作的栈。三种操作的说明如下：

① push A x：将x插入栈A中。

② pop A：删除栈A的顶部元素。

③ merge A B：合并栈A和B。

其中，“merge A B”操作后栈A包含A和B之前的所有元素，B变为空，新栈中的元素根据先前的进栈时间重新排列，就像在一个栈中重复”push”操作一样。给定两个可合并栈A和B，请执行上述操作。

【输入形式】

测试用例的第一行包含一个整数n（0<n≤10^5）表示操作个数，接下来的n行每行包含一条指令push、pop或merge，栈元素是32位整数。A和B最初都是空的，并且保证不会对空栈执行pop操作。以n=0表示输入结束。

【输出形式】

对于每个pop操作，在一行中输出对应的出栈元素。

【样例输入】

9

push A 0

push A 1

push B 3

pop A

push A 2

merge A B

pop A

pop A

pop A

【样例输出】

1

2

3

0

题解

本题是作者数据结构与算法课上的一道习题，主要难点在于记录每一个数据的时间戳，以便merge操作的比较。作者使用了非常直接的办法，即将数据和时间戳用一个pair来记录，并为其单独写了一个comp比较函数，作为sort函数的传参。每次merge操作时，将A和B中的元素都弹出至vector中，并根据时间戳排序，再全部压入栈中。考虑到该题对算法的性能要求不高，该法可以达到目的。

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

stack<pair<int, int>> A;
stack<pair<int, int>> B;

bool comp(const pair<int, int>& p1, const pair<int, int>& p2) {
  return p1.first < p2.first;
}

void merge(stack<pair<int, int>>& s1, stack<pair<int, int>>& s2) {
  vector<pair<int, int>> v;
  while (!s1.empty()) {
    v.push_back(s1.top());
    s1.pop();
  }
  while (!s2.empty()) {
    v.push_back(s2.top());
    s2.pop();
  }
  sort(v.begin(), v.end(), comp);
  for (auto i : v) {
    s1.push(i);
  }
}

int main() {
  // freopen("in.txt", "r", stdin);
  int n, m = 0;
  cin >> n;
  cin.ignore();
  while (n--) {
    string line;
    getline(cin, line);
    switch (line[1]) {
      case 'u':
        if (line[5] == 'A') {
          A.push(make_pair(m++, line[7] - '0'));
        } else {
          B.push(make_pair(m++, line[7] - '0'));
        }
        break;
      case 'o':
        if (line[4] == 'A') {
          cout << A.top().second << endl;
          A.pop();
        } else {
          cout << B.top().second << endl;
          B.pop();
        }
        break;
      case 'e':
        if (line[6] == 'A') {
          merge(A, B);
        } else {
          merge(B, A);
        }
        break;
    }
  }
  return 0;
}