剑指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函数的栈
栈的压入、弹出序列
二叉搜索树的后序遍历序列
按之字形顺序打印二叉树
参考文章：
知乎大佬的好文:对于递归有没有什么好的理解方法
