PTA特殊堆栈

题目

堆栈是一种经典的后进先出的线性结构&＃xff0c;相关的操作主要有“入栈”&＃xff08;在堆栈顶插入一个元素&＃xff09;和“出栈”&＃xff08;将栈顶元素返回并从堆栈中删除&＃xff09;。本题要求你实现另一个附加的操作&＃xff1a;“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素&＃xff0c;如果 N 是偶数&＃xff0c;则中值定义为第 N/2 小元&＃xff1b;若是奇数&＃xff0c;则为第 (N&＃43;1)/2 小元。

输入

输入的第一行是正整数 N&＃xff08;≤105&＃xff09;。随后 N 行&＃xff0c;每行给出一句指令&＃xff0c;为以下 3 种之一&＃xff1a;

Push key
Pop
PeekMedian


其中 key 是不超过 10510^5105 的正整数&＃xff1b;Push 表示“入栈”&＃xff1b;Pop 表示“出栈”&＃xff1b;PeekMedian 表示“取中值”。

输出

对每个 Push 操作&＃xff0c;将 key 插入堆栈&＃xff0c;无需输出&＃xff1b;对每个 Pop 或 PeekMedian 操作&＃xff0c;在一行中输出相应的返回值。若操作非法&＃xff0c;则对应输出 Invalid。

输入样例

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop


输出样例

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid


题目分析

由题目分析可以知道&＃xff0c;此题需要对数据进行堆栈和排序的处理。通过堆栈实现后进先出的功能&＃xff0c;同时排序后的序列达到寻找中值。对排序的处理可以使用优先队列&＃xff0c;也可以采用vector数组&＃xff0c;在对数据输入&＃xff0c;弹出时通过二分查找到对应位置再插入或者删除。应用了lower_bound函数二分查找不小于输入该数的第一个数&＃xff0c;在对应位置插入或者删除。

代码

#include
#include
#include
#include
#include
using namespace std;
string op;
stack<int> st;//栈
vector<int> v;//数组排序void push(){int data;scanf("%d",&data);st.push(data);v.insert(lower_bound(v.begin(),v.end(),data),data);//对应位置插入
}
void pop(){if(st.empty()){//是否栈空cout << "Invalid"<<endl;return ;}int k &＃61; st.top();//用于查找数组中元素并删除cout << k<<endl;st.pop();v.erase(lower_bound(v.begin(),v.end(),k));//删除对应位置元素
}
void peekm(){if(v.size()&＃61;&＃61;0){cout << "Invalid"<<endl;return ; }int len &＃61; v.size();len&＃61;(len&＃43;1)/2-1;cout << v[len]<<endl;
}int main(){int n;cin >> n;for(int i &＃61; 0;i<n;&＃43;&＃43;i){cin >> op;//输入操作&＃xff0c;对应处理if(op &＃61;&＃61; "Push") push();else if(op &＃61;&＃61; "Pop") pop();else if(op &＃61;&＃61; "PeekMedian") peekm();}return 0;
}


运行结果