PAT4：MyStack

请设计这样的一个栈 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;
}