【C++ 棧，隊列，堆】

1. 使用隊列實作棧（LeetCode 225.）

class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> qi;
    queue<int> qt;

    MyStack() {

    }
    
    /** Push element x onto stack. */
    void push(int x) {
       while(qi.size()){
           qt.push(qi.front());
           qi.pop();
       }
       qi.push(x);
       while(qt.size()){
           qi.push(qt.front());
           qt.pop();
       }

    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int temp=qi.front();
        qi.pop();
        return temp;
    }
    
    /** Get the top element. */
    int top() {
        return qi.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return qi.empty();
    }
};
           

1. 使用棧實作隊列（LeetCode 232.）

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> si;
    stack<int> st;
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        if(si.empty()){
            si.push(x);
        }
        else{
            while(si.empty()==false){
                st.push(si.top());
                si.pop();
            }
            si.push(x);
            while(st.empty()==false){
                si.push(st.top());
                st.pop();
            }
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int t=si.top();
        si.pop();
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        return si.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return si.empty();
    }
};
           

3.最小值棧(LeetCode 155.)

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> _data;
    stack<int> _min;
    MinStack() {
        
    }
    
    void push(int x) {
        _data.push(x);
        if(_min.empty()){
            _min.push(x);
        }
        else{
            if(x>_min.top()){
                x=_min.top();
            }
            _min.push(x);
        }
    }
    
    void pop() {
        _data.pop();
        _min.pop();
    }
    
    int top() {
        return _data.top();
    }
    
    int getMin() {
        return _min.top();
    }
};
           

#include<stack>
#include<queue>
using namespace std;

bool check_is_vaild_order(queue<int> &order){
	stack<int> s;
	int n=order.size();
	
	for(int i=1;i<=n;i++){
		s.push(i);
		while(!s.empty() && order.front()==s.top()){
			s.pop();
			order.pop();
		}
	}
	
	if(!s.empty()){
		return false;
	}
	return true;
} 
           

1. 簡單的電腦（LeetCode 224.）

void compute(stack<int> &number_stack,stack<char> &operation_stack){
    if(number_stack.size() < 2){
        return;
    }
    int num2 = number_stack.top();
    number_stack.pop();
    int num1 = number_stack.top();
    number_stack.pop();
    if(operation_stack.top() == '+'){
        number_stack.push(num1 + num2);
    }
    else if(operation_stack.top() == '-'){
        number_stack.push(num1 - num2);
    }
    operation_stack.pop();
}

class Solution {
public:
    int calculate(string s) {
        static const int STATE_BEGIN = 0;
        static const int NUMBER_STATE = 1;
        static const int OPERATION_STATE = 2;
        stack<int> number_stack;
        stack<char> operation_stack;
        int number = 0;
        int STATE = STATE_BEGIN;
        int compuate_flag=0;

        for(int i=0;i<s.length();i++){
            if(s[i] == ' '){
                continue;
            }
            switch(STATE){
                case STATE_BEGIN:
                    if(s[i]>='0' && s[i]<='9'){
                        STATE = NUMBER_STATE;
                    }
                    else{
                        STATE = OPERATION_STATE;
                    }
                    i--;
                    break;
                case NUMBER_STATE:
                if(s[i]>='0' && s[i]<='9'){
                    number = number *10 +(s[i]-'0');
                }
                else{
                    number_stack.push(number);
                    if(compuate_flag == 1){
                        compute(number_stack,operation_stack);
                    }
                    number=0;
                    i--;
                    STATE = OPERATION_STATE;
                }
                break;
                case OPERATION_STATE:
                    if(s[i] == '+' || s[i] == '-'){
                        operation_stack.push(s[i]);
                        compuate_flag = 1;
                    }
                    else if(s[i]=='('){
                        STATE = NUMBER_STATE;
                        compuate_flag = 0;
                    }
                    else if(s[i]>='0' && s[i]<='9'){
                        STATE = NUMBER_STATE;
                        i--;
                    }
                    else if(s[i] == ')'){
                        compute(number_stack,operation_stack);
                    }
                    break;
            }
        }
        if(number != 0){
            number_stack.push(number);
            compute(number_stack,operation_stack);
        }
        if(number == 0 && number_stack.empty()){
            return 0;
        }
        return number_stack.top();
    }
};


           

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority queue<int,vector<int>,greater<int> > q;
        for(int i=0;i<nums.size(),i++){
            if(q.size() < k){
                q.push(nums[i]);
            }
            else if(q.top() < nums[i]){
                q.pop();
                q.push(nums[i]);
            }
        }
        return q.top();
    }
};
           

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> big_queue;
    priority_queue<int,vector<int>,greater<int>> small_queue;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(big_queue.empty()){
            big_queue.push(num);
            return ;
        }
        if(big_queue.size() == small_queue.size()){
            if(num < big_queue.top()){
                big_queue.push(num);
            }
            else{
                small_queue.push(num);
            }
        }
        else if(big_queue.size() > small_queue.size()){
            if(num >big_queue.top()){
                small_queue.push(num);
            }
            else{
                small_queue.push(big_queue.top());
                big_queue.pop();
                big_queue.push(num);
            }
        }
        else if(big_queue.size() < small_queue.size()){
            if(num <small_queue.top()){
                big_queue.push(num);
            }
            else{
                big_queue.push(small_queue.top());
                small_queue.pop();
                small_queue.push(num);
            }
        }
    }
    
    double findMedian() {
        if(big_queue.size() == small_queue.size()){
            return (double)(big_queue.top() +small_queue.top()) /2;
        }
        else if(big_queue.size() > small_queue.size()){
            return big_queue.top();
        }
        else return small_queue.top();
    }
};