剑指offer之栈

一、杂话：不知不觉中就来到了栈了。哈哈，不过还是进度缓慢呀。栈之后的数据结构还有很多，有些自己都还没看完呢。路漫漫其修远兮。今天查了下，腾讯招聘的结果，不出预料，哈哈，又挂了。确实是能力不足呀。一方面编程能力不太行，另一方面相关基础知识又没学过，自个还得自学。难呀。不过现在，先不管那么多，先把数据结构与算法搞好，然后搞下操作系统，数据库，顺带再看看STL。加油吧，少年。
二、栈的相关知识点：
①首先要明白什么是栈。简单来说，就是符合先进后出的一种数据结构，就像往桶里面放东西，最先放进去的，最后才能拿出来，而最后放进去的，会在最上面，就会是最先拿出来的。
②栈的实现：学过了之前的数组和链表，就知晓了。其实无非两种方式，一种由数组实现，一种由链表实现。下面就展开讲下这两种实现方式：
1.数组实现栈：

代码如下:

const int MAXSIZE = 1000;
//定义一个栈，用结构体定义
template <class T>
struct myStack {

private:    
    int top=-1;//栈顶
    T data[MAXSIZE];//自定义最大长度为1000

public:    
    //定义入栈函数
    void push(T n ){
        data[++top]= n;

    }
    //定义出栈函数
    void pop() {
        --top;
    }
    //获取栈顶元素函数
    T mytop() {
        return data[top];
    }
    //定义判空函数
    bool isEmpty() {
        return top == -1;
    }
    //定义长度大小函数
    int mysize() {
        return top+1;
    }
};

2.链表实现栈：
图示如下：

代码如下：

//定义链表
template<class T>
struct ListNode {
    T val;
    struct ListNode* next;
    ListNode() :val(0), next(nullptr){}
    ListNode(T x) :val(x),next(nullptr ){}
};

//定义由链表构成的栈
template<class T>
struct myStack {
private:
    ListNode<T>* top=nullptr;
public:
    void push(T n) {
        ListNode<T>* newnode = new ListNode<T>(n);
        newnode->next = top;
        top = newnode;
    }
    void pop() {
        ListNode<T>* tmp = top;
        top = tmp->next;
        free(tmp);
    }
    T mytop() {
        return top->val;
    }
    bool isEmpty() {
        return !top;
    }
    int mysize() {
        if (top) {
            ListNode<T>* tmp = top; int sum = 0;
            while (tmp) {
                ++sum;
                tmp = tmp->next;
            }
            return sum;
        }
        else   return 0;
    }
};

③双栈共享空间：
即用一个数组存两个栈，这样就会一个问题，怎么判断栈满了呢，还有怎么判断出入的是哪个栈呢。
1.对于第一个问题，是通过用top1+1==top2来判断栈是否满的，因为有假设栈为空时，左边栈top1=-1，右边栈top2=n，即使左栈满了，右栈为空top2=0，top1=n-1，此时仍有top1+1=top2。所以，上面构造栈的两种方式中，要注意栈为空时top要么为-1位置，要么为空指针。
2.对于第二个问题，可以引入一个标志位，作为push，pop,isEmpty,mysize，等函数的参数，进而区分使用的是哪个栈。代码略。
④栈的应用：
理解递归：通过看了知乎大佬的讲解后，有了新的认识。其实递归就是递推加回归。其实现的基础就是栈。
递归主要掌握三点：
第一，要知道函数实现什么功能，这就要求编写者实现知道可以通过递归来解决问题，从而才能定义递归函数。
第二，明确回归点，就是递归结束的条件，容易遗漏导致死循环，可以通过递归关系式来反验证。
第三，找到递归关系式，怎么找，大佬指出，这个关系式都是将原范围一步步缩小的。因此，可以尝试缩小范围，缩小范围后需要执行什么操作才能达到结果，这些操作往往就是递归关系。
除此之外，由于递归有很多重复计算，因此可以通过记录已算值得方式减少不必要得重复，可以用数组/哈希表，一般用数组。只要额外判断下是否计算过即可。具体例子见下方链接的知乎文章。
三、刷题总结
①JZ5 用两个栈实现队列---简单

思路：容易想到，一个栈存数据，一个栈抛出数据。进入栈1，再将栈1进到栈2，通过两次反转，这时，栈2就符合队列的弹出顺序了。进栈好说，但是出栈就会有一个问题，怎么保证栈2内的元素符合队列先进先出的规则呢。例如下图，如果栈2还没pop完，栈1就往栈2放入元素，就会导致顺序变乱。为此，要注意两点：第一，把栈1元素push到栈2前需要判断，栈2是否为空。第二，必须一次性把栈1的元素全部放进去。

代码如下：
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {//注意只有当stack2为空时，才可以将stack1中的元素全部push进去
        if(stack2.empty()){
           while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
         }
            int p= stack2.top();
            stack2.pop();
            return p; 
    }

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

②JZ20 包含min函数的栈---较难

思路:用两个栈，栈1负责存数据，栈2个负责存最小的数。每一次，进入新数据，如果栈2为空就直接放进去，否则就比较新数与栈2栈顶的数哪个更小，如果新数小就放入，否则继续放栈顶的数。这样做的目的是与栈1同步，确保栈1pop完后栈2存在栈顶的元素就是栈1的最小元素。见图：

代码如下：

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

③JZ21 栈的压入、弹出序列---中等

思路：用一个栈去模拟入栈出栈的过程。同时用两个指针i,j分别指向入栈向量和出栈向量。如果说，pushV[i]==popV[j]，证明一入栈就出栈，++i和++j，否则就说明该元素入栈。如果是入栈即出栈，要注意一点，就是可能此时栈里有元素，所以得判断下popV[j]是否等于栈顶元素，如果是，就要把栈顶元素pop掉，同时++j，这里还要注意，这个过程是不断while的，直到，popV[j]不等于栈顶元素了才停止。可以尝试自行图解体会。原理大致如此。这是一个很奇妙的题目，想到了就能做出来，所以要部分记忆。
代码如下：

    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //双指针+栈模拟
        //特殊情况
        if(pushV.size()!=popV.size())    return 0;
        stack<int>pushstack;
        int i=0,j=0;
        while(i<pushV.size()&&j<popV.size()){
            if(pushV[i]!=popV[j]){//说明没有一入栈就pop掉
                //此时要把元素放进pushstack中
                pushstack.push(pushV[i++]);
            }
            else{
                ++i;++j;
                while(!pushstack.empty()&&popV[j]==pushstack.top()){//发现popV是栈顶元素，则应该把栈顶元素pop掉
                    pushstack.pop();
                    ++j;
                }
            }
        }
        return pushstack.empty();

④JZ23 二叉搜索树的后序遍历序列---较难

思路：这个题与二叉树的后序遍历有关，因此在开始前需要了解下，二叉树的后序遍历的实现方式。二叉树的后序遍历实现方式有两种，一种是直接用递归实现，一种是用非递归实现。下面分别讲这两种方式。
1.二叉树后序遍历的递归实现
先遍历左右树，在输出当前结点，递归函数即可。

//递归实现二叉树的后序遍历
void back_search(tree *head) {
    if (!head)    return;
    back_search(head->left);
    back_search(head->right);
    cout << head->val<<"  ";
}

2.非递归实现二叉树的后序遍历：
比较难。需要创建两个指针，一个指向当前结点，一个记录前一个遍历的结点，还得注意每次当前结点都必须是栈顶的结点，这一点很关键，如果没有这一点的话，函数会死循环的。原理就是，每次结点输出之前都是左右树结点先输出完了，自身才能输出。因此需要记录前一个输出的结点是否是当前结点的左右结点，或者当前结点无左右结点，如果是，则可以输出当前结点。否则，需要把结点两端的左右结点入栈。注意循环的条件是，存储树结点的栈不为空，因此需要一开始就把根节点放入栈中。还有，放入左右树时，注意必须是先放入右树，在放入左树，原因是，遍历时是先左后右，而入栈后是先进后出，所以先放右再放左。

//非递归实现二叉树的后序遍历---费解
void back_search2(tree *head) {
    stack<tree *>s; tree* cur=head;
    tree* pre=nullptr;//用来标记已经遍历的结点
    s.push(cur);
    while (!s.empty() ) {
        cur = s.top();//cur一定要始终指向栈顶
        if ((!cur->left && !cur->right)||(pre&&(pre==cur->left||pre==cur->right))) {
            cout << cur->val << "  ";
            s.pop();
            pre = cur;
        }
        else {
            if (cur->right)    s.push(cur->right);
            if (cur->left)    s.push(cur->left);
        }
    }
}

3.另外，题目提到了一种特殊的树，叫二叉搜索树，这种树与普通的二叉树不同。这种树的左子树结点的值都比根节点值小，右子树结点的值都比根节点值大，且左右子树也是二叉搜索树。
4.解题方法：
(1)递归的方式---有点费解：
有点类似快排，二分查找，归并排序，都是找到中间的位置，然后递归考虑两边的情况。鉴于二叉搜索树的特点，我们可以先就一个结点，分析它是否符合左树小于，右树大于的特点，然后再递归分析左树和右树是否也符合这个特点。引入两个指针，left和right，让探针probe=left,让其在左边找到区分左右树的临界点，然后，让probe继续移动，判断右边的数是否都大于根节点值，如果时就让其继续移动，否则就不动。这样，如果probe==right就证明该结点符合左树小于，右树大于的特点，接下来继续递归判断左树和右树即可。注意两点：第一，回归点是，left>=right，原因是要确保左边指针始终在左边，右边指针始终在右边，当出现left>=right就证明此时只剩<=1个数了，不用再判断了，肯定是true。第二，判断右树时，需要right--，因为，第一个根节点已经判断过了，所以要判断下一个，需要--right。
代码如下：

    bool VerifySquenceOfBST(vector<int> sequence) {
        //借助搜索树的特点，我们可以定位到左右树的区间
        return BST(sequence,0,sequence.size()-1);
    }
    bool BST(vector<int> v,int left,int right){
         //特例
        if(!v.size())    return 0;
        if(left>=right)    return 1;//left>righe代表没有数了
         int probe=left,mid;
        while(v[probe]<v[right])    ++probe;
        mid=probe;
        while(v[probe]>v[right])    ++probe;
        return probe==right&&BST(v,left,mid-1)&&BST(v,mid,right-1);
    }

(2) 利用单调栈解决---没太懂
首先了解下什么是单调栈。顾名思义，单调栈就是，栈内元素是有序单调的，有两种，单调增和单调减，不过它指的单调是从栈顶到栈底的，比如入栈顺序[1,2,3,4,5]那么就是一个单调递减栈。
这种解法很绕，暂且先放着：
代码如下：

bool VerifySquenceOfBST(vector<int> sequence) {
       if(!sequence.size())    return 0;
       stack<int>s;int parent=INT32_MAX;
       for(int i=sequence.size()-1;i>=0;--i){
           if(sequence[i]>parent)    return 0;//如果比父节点大，证明非搜索树 
           while(!s.empty()&&sequence[i]<s.top()){//如果小于，证明是左节点
               parent=s.top();
               s.pop();
           }

           s.push(sequence[i]);
       }
       return 1;
}

⑤JZ59 按之字形顺序打印二叉树---较难

思路：可以说自个是完全没有思路的，目前已知的有，前序遍历，中序遍历，后序遍历的递归实现，对前序遍历，中序遍历和后序遍历的非递归实现有了解，但是不熟悉，将在涉及这一板块内容时，再进一步详述。至于层序遍历，就只知道一个用队列实现，而像题目要求的之字形这种遍历方法就更不懂了。原因主要是对树的遍历并不熟悉。
因此，只好借鉴大佬的思路，尝试理解下：其实这个题用的是层序遍历的思想，而层序遍历的思想其实就是广度优先搜索，即BFS，BFS有下面两种模板，一种是不记录层数，一种是记录层数的：

//不记录层数的BFS
void BFS(){
    vist[]={0};
    quene<int>q(start_val);
    while(!q.empty()){
        int cur=q.front;q.pop();
        for(遍历cur所有相邻结点next){
            if(next存在&&vist[next]==0){
                vist[next]=1;
                q.push(next);
            }
        }
    }
}

//记录层数的BFS
void BFS(){
    vist[]={0};int level=0;
    quene<int>q(start_val);
    while(!q.empty()){
        int turns=q.size();
        while(turns--){
            int cur=q.front;q.pop();
            for(遍历cur所有相邻结点next){
                if(next存在&&vist[next]==0){
                    vist[next]=1;
                    q.push(next);
                }
            }
        }
        ++level;
    }
}

因此，有方法一，用BFS实现之字形遍历：

    vector<vector<int> > Print(TreeNode* pRoot) {
        //用BFS解
        vector<vector<int>>res;//用来存结果；
        if(!pRoot)    return res;//特殊情况
        queue<TreeNode *> q;//用队列来存每一层的结点
        int level=0;//记录遍历层数
        q.push(pRoot);//先要把根节点放入队列中
        while(!q.empty()){
            int turns=q.size();
            vector<int>ans;//用来记录每一层的遍历结果
            while(turns--){
                TreeNode* node=q.front();
                q.pop();
                ans.push_back(node->val);
                if(node->left)    q.push(node->left);
                if(node->right)    q.push(node->right);
            }
            ++level;
            //判断是否为偶数，如是，则翻转
            if(!(level&1))
                reverse(ans.begin(), ans.end());
            res.push_back(ans);

        }
        return res;
    }

还有方法二：利用两个栈来实现

稍微总结下：树的遍历中前序，中序，后序都与栈有关，而层序遍历往往与队列有关。在学树这一板块时，需要重新总结下，栈和队列的应用。

试题链接：
用两个栈实现队列
包含min函数的栈
栈的压入、弹出序列
二叉搜索树的后序遍历序列
按之字形顺序打印二叉树
参考文章：
知乎大佬的好文:对于递归有没有什么好的理解方法