【剑指offer】队列&栈篇-含题目代码思路解析

1.JZ9 用两个栈实现队列

C++

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int node=stack2.top();
        stack2.pop();
        return node;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

注意

• stack是标准库中的一个容器适配器，是个类模板，使用的时候需要实例化，int是模板实参。
  stack st声明了1个存储int型元素的栈，栈名是st。
• $stack<int>$的方法函数原型

1. empty()	堆栈为空则返回真
2. pop()	移除栈顶元素
3. push()	在栈顶增加元素
4. size()	返回栈中元素数目
5. top()	返回栈顶元素

• 栈出，和返回栈出值，两码事儿【要在栈出前，记录栈出值】

 int node=stack2.top();
 stack2.pop();
 return node;

2. JZ30 包含min函数的栈

C++

class Solution {
public:
    stack<int> s1;
    stack<int> s2;
    void push(int value) {
        s1.push(value);
        if(s2.empty()||s2.top()>value){
            s2.push(value);
        }else{
            s2.push(s2.top());
        }
    }
    void pop() {
        s1.pop();
        s2.pop();
    }
    int top() {
        return s1.top();
    }
    int min() {
        return s2.top();
    }
};

注意

3.JZ31 栈的压入、弹出序列

4.JZ73 翻转单词序列

C++【反转两次】

class Solution {
public:
    string ReverseSentence(string str) {
        int n=str.length();
        reverse(str.begin(),str.end());
        for(int i=0;i<n;i++){
            int j=i;
            while(j<n&&str[j]!=' '){
                j++;//计数这个单词
            }
            reverse(str.begin()+i,str.begin()+j);
            i=j;
        }
        return str;
    }
};

C++【栈】

class Solution {
public:
    string ReverseSentence(string str) {
        int n = str.length();
        stack<string> st;
        //遍历字符串，找到单词并入栈
        for(int i = 0; i < n; i++){ 
            int j = i;
            //以空格为界，分割单词
            while(j < n && str[j] != ' ')  
                j++;
            //单词进栈
            st.push(str.substr(i, j - i));  
            i = j;
        }
        str = "";
        //栈遵循先进后厨，单词顺序是反的
        while(!st.empty()){   
            str += st.top();
            st.pop();
            if(!st.empty())
                str += " ";
        }
        return str;
    }
};

注意

• substr函数的形式为s.substr(pos, n)；
  需要两个参数，第一个是开始位置，第二个是获取子串的长度。

假设：string s = “0123456789”;
string sub1 = s.substr(5);
//只有一个数字5表示从下标为5开始一直到结尾：sub1 = “56789” string sub2 = s.substr(5, 3);
//从下标为5开始截取长度为3位：sub2 = “567”

JZ59 滑动窗口的最大值