class Queue {
public:
    stack<int> stk1;    // push
    stack<int> stk2;    // pop
    // Push element x to the back of queue.
    void push(int x) {
        stk1.push(x);
    }
    // Removes the element from in front of queue.
    void pop(void) {
        if(stk2.empty())
        {
            while(!stk1.empty())
            {
                int top = stk1.top();
                stk1.pop();
                stk2.push(top);
            }
        }
        stk2.pop();
    }
    // Get the front element.
    int peek(void) {
        if(stk2.empty())
        {
            while(!stk1.empty())
            {
                int top = stk1.top();
                stk1.pop();
                stk2.push(top);
            }
        }
        return stk2.top();
    }
    // Return whether the queue is empty.
    bool empty(void) {
        return stk1.empty()&&stk2.empty();
    }
};

class Stack {  
public:  
    // Push element x onto stack.  
    queue<int> queue1;  
    queue<int> queue2;  
    void push(int x) {  
        if (queue1.empty())  
        {  
            queue1.push(x);  
            while(!queue2.empty()){  
                int tmp = queue2.front();  
                queue2.pop();  
                queue1.push(tmp);  
            }  
        }else{  
            queue2.push(x);  
            while(!queue1.empty()){  
                int tmp = queue1.front();  
                queue1.pop();  
                queue2.push(tmp);  
            }  
        }  
    }  
  
    // Removes the element on top of the stack.  
    void pop() {  
        if (!queue1.empty())  
            queue1.pop();  
        if (!queue2.empty())  
            queue2.pop();  
    }  
  
    // Get the top element.  
    int top() {  
        if (!queue1.empty())  
            return queue1.front();  
        if (!queue2.empty())  
            return queue2.front();  
    }  
  
    // Return whether the stack is empty.  
    bool empty() {  
        return queue1.empty() && queue2.empty();  
    }  
};  

class MinStack {
public:
    stack<int> allStack;
    stack<int> minSta;

    void push(int x) {
        if (allStack.empty()) {
            allStack.push(x);
            minSta.push(x);
        }
        else {
            allStack.push(x);
            if (x <= minSta.top()) minSta.push(x);
        }
    }

    void pop() {
        if (allStack.top() == minSta.top()) {
            minSta.pop();
        }
        allStack.pop();
    }

    int top() {
        return allStack.top();
    }

    int getMin() {
        return minSta.top();
    }                                  
};

//第一種
class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            //max heap method
            //min heap method
            //order statistics
            make_heap(nums.begin(), nums.end());
            int result;
            for(int i=0; i<k; i++){
                result=nums.front();
                pop_heap(nums.begin(), nums.end());
                nums.pop_back();
            }
            return result;
        }
    };
//第二種
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int high = nums.size();
        int low = 0;
        while (low < high) {
            int i = low;
            int j = high-1;
            int pivot = nums[low];
            while (i <= j) {
                while (i <= j && nums[i] >= pivot)
                    i++;
                while (i <= j && nums[j] < pivot)
                    j--;
                if (i < j)
                    swap(nums[i++],nums[j--]);
            }
            swap(nums[low],nums[j]);

            if (j == k-1)
                return nums[j];
            else if (j < k-1)
                low = j+1;
            else
                high = j;
        }
    }
};

class MedianFinder {  
private:  
    priority_queue<int,vector<int> ,less<int>> maxHeap;           // 保存較小數(shù)  
    priority_queue<int, vector<int>,greater<int>> minHeap;        // 保存較大數(shù)  
public:  
  
    // Adds a number into the data structure.  
    void addNum(int num) {  
        maxHeap.push(num);//往較小的數(shù)中添加  
        int t = maxHeap.top(); //返回較小數(shù)中的最大數(shù)  
        maxHeap.pop();  
        minHeap.push(t);//并將其添加到較大數(shù)中  
        int maxLen = maxHeap.size();  
        int minLen = minHeap.size();  
        if (minLen - maxLen > 0)  
        {  
            int t = minHeap.top();  
            maxHeap.push(t);  
            minHeap.pop();  
        }  
    }  
  
    // Returns the median of current data stream  
    double findMedian() {  
        if (maxHeap.size() > minHeap.size())  
            return maxHeap.top()*1.0;  
        else if (maxHeap.size() < minHeap.size())  
            return minHeap.top()*1.0;  
        else  
            return (minHeap.top() + maxHeap.top()) / 2.0;  
    }  
};