请设计这样的一个栈 class MyStack,实现普通栈的操作:pop(),push(),size(),另外,再设计一个友元函数,PeekMedian() ,返回栈中的中位数。(中位数定义:N为偶数时,栈中第(N/2)小的元素,N为奇数时第 ((N+1)/2) 小的数)
Input Specification:
每个输入文件包含一组case. 对于每个case,第一行一个整数N(<= 105),接下去N行,每一个行如下操作中的一种:
Push key(0 <= key <= 105)
Pop
PeekMedian
Output Specification:
对于每个Push命令,插入key到栈中。对于每个Pop命令,输出栈定元素,并将其出栈,对于每个peekMedian命令,输出中位数。如果命令非法(栈为空时Pop,或PeekMedian)输出"Invalid".
Sample Input:
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
Sample Output:
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid
#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int num;
Node * next;
};
class MyStack {
public:
MyStack(){
this->stackSize = 0;
this->Stack = NULL;
}
void push(int num) {
if(this->stackSize == 0) {
this->Stack = new Node;
this->Stack->num = num;
this->Stack->next = NULL;
} else {
Node * newNode = new Node;
newNode->num = num;
newNode->next = this->Stack;
this->Stack = newNode;
}
this->stackSize++;
}
void pop() {
if(this->stackSize == 0) {
cout << "Invalid";
} else {
int deletedNum = this->Stack->num;
this->Stack = this->Stack->next;
this->stackSize--;
cout << deletedNum;
}
cout << endl;
}
int size() {
return this->stackSize;
}
friend void PeekMedian(MyStack &);
private:
int stackSize;
Node * Stack;
};
void PeekMedian(MyStack & ms) {
if(ms.size() == 0) {
cout << "Invalid";
} else {
int i=0, *nums = new int[ms.size()];
Node *p = ms.Stack;
do {
nums[i] = p->num;
i++;
p = p->next;
} while(p!=NULL);
sort(nums, nums+ms.size());
if(ms.size()%2==0) {
cout << nums[ms.size()/2-1];
} else {
cout << nums[(ms.size()+1)/2-1];
}
}
cout << endl;
}
int main() {
int N;
string opt;
MyStack mystack;
cin >> N;
while(N > 0) {
cin >> opt;
if(opt == "Push") {
int num;
cin >> num;
mystack.push(num);
} else if(opt == "Pop") {
mystack.pop();
} else if(opt == "PeekMedian") {
PeekMedian(mystack);
}
N--;
}
return 0;
}