L3-002. 堆栈

川长思鸟来 2022-05-29 01:39 99阅读 0赞

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。  
输入格式：  
输入第一行给出正整数N（<= 105）。随后N行，每行给出一个操作指令，为下列3种指令之一：  
Push key  
Pop  
PeekMedian  
其中Push表示入栈，key是不超过105的正整数；Pop表示出栈；PeekMedian表示查中值。  
输出格式：  
对每个入栈指令，将key入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“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

代码只能部分正确，希望有大佬可以改对

#include <iostream>
    #include <stdio.h>
    #include <string>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    vector<int>st(100005);
    int main()
    {
    
        int top = 1;
        int base = 0;
        int n;
        cin >> n;
        string cmd;
    
        while (n--)
        {
            cin >> cmd;
            if (cmd == "Push")
            {
                int t;
                cin >> t;
                st[top++] = t;
            }
            else if (cmd == "Pop")
            {
                if (top != 1)
                {
                    top--;
                    cout << st[top] << endl;
                }
                else
                    cout << "Invalid" << endl;
            }
            else if (cmd == "PeekMedian")
            {
                //stack<int>::iterator it
                if (top == 1)
                {
                    cout << "Invalid" << endl;
                }
                else
                {
                    vector<int> t;
                    t.assign(st.begin(), st.begin() + top);
                    sort(t.begin() + 1, t.end());
                    int tp = top - 1;
                    if (tp % 2 == 0)
                        cout << t[tp / 2] << endl;
                    else cout << t[(tp + 1) / 2] << endl;
                }
    
            }
        }
    
        return 0;
    }

![这里写图片描述][Image 1]

[Image 1]: