刷题-栈和队列

1. [Leetcode 232] 用栈实现队列 （剑指OFFER面试题 9）

• 解法：一个栈(push栈)用于接收push，一个栈(pop栈)用于top(peek)和pop
  1. 当pop栈为空，且push栈不为空时，将push栈的元素转移到pop栈中
  2. 当pop栈不为空时，将pop栈的数据pop出去
  3. push操作只在push栈进行
• 注意：
  • leetcode上可以不进行异常处理，能a过，但是面试时候最好还是加上空栈的异常处理。
  • 泛型支持。
  • 线程安全。

    class MyQueue {
    private:
         stack<int>  spush;
         stack<int> spop;
    public:
        /** Initialize your data structure here. */
        MyQueue() {
           
        }
    
        /** Push element x to the back of queue. */
        void push(int x) {
            spush.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
        	if (spop.empty()){
            	while (!spush.empty()) {
    				spop.push(spush.top());
    				spush.pop();
            	}
         	}
            int res = spop.top();
    		spop.pop();
    		return res;
        }
        
        /** Get the front element. */
        int peek() {
        	if (spop.empty()){
          		while (!spush.empty()) {
    				spop.push(spush.top());
    				spush.pop();
          		}  
        	}
        	return spop.top();
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return spush.empty()&&spop.empty();
        }
    };

2.[Leetcode 155] 最小栈 (剑指Offer面试题30)

• 解法：双栈实现，一个栈用于正常的入栈出栈，一个栈用于记录最小值

• 代码：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        mainStack.push(x);
        if(subStack.empty() || x <= subStack.top()){
            subStack.push(x);
        }
    }
    
    void pop() {
        int tmp = mainStack.top();
        mainStack.pop();
        if(tmp == subStack.top()){
            subStack.pop();
        }
    }
    
    int top() {
        int res = mainStack.top();
        return res;
    }
    
    int getMin() {
        //if(subStack.empty()) return 0;
        return subStack.top();
    }

private:
    stack<int> mainStack;
    stack<int> subStack;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

3. [Leetcode 946] 验证栈序列 （剑指Offer面试题31）

• 解法：双栈模拟，或者通过判断输入栈栈顶元素是否与验证栈当前指针所指元素相等。
• 代码：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack <int>s;
        int count=0;
        for(int i=0;i<pushed.size();i++){
                s.push(pushed[i]);
            while(!s.empty()&&s.top()==popped[count]){
                s.pop();
                count++;
            }
        }
        if(!s.empty())
            return false;
        else
            return true;
    }
};