PAT甲级原题：https://pintia.cn/problem-sets/994805342720868352/problems/994805417945710592

采用数组模拟一个栈用来存储输入输出的元素，之后用两个multiset来表示寻找中值的栈。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int stk[N],tt;
multiset<int> up,down;//默认从小到大排列
void jdg()
{
    if(up.size()>down.size())
    {
        down.insert(*up.begin());
        up.erase(up.begin());
    }
    while(down.size()>up.size()+1)
    {
        auto p = down.end();
        p--;
        up.insert(*p);
        down.erase(p);
    }
}
int main()
{
    int n; cin>>n;
    char op[20];
    while(n--)
    {
        scanf("%s",op);
        if(strcmp(op,"Pop")==0)
        {
            if(tt<1) puts("Invalid");
            else
            {
                int x = stk[tt];
                tt--;
                auto t = down.end();
                t--;
                if(*t<x) up.erase(up.find(x));
                else down.erase(down.find(x));
                printf("%d\n",x);
                jdg();
            }
        }
        else if(strcmp(op,"PeekMedian")==0)
        {
            if(tt<1) puts("Invalid");
            else{
                auto t = down.end();
                t--;
                printf("%d\n",*t);
            }
        }
        else{
            int k; scanf("%d",&k);
            stk[++tt]=k;
            if(up.size()<1 || *up.begin()>k) down.insert(k);
            else up.insert(k);
            jdg();
        }
    }
    return 0;
}