栈

概念

正如标题所述，栈是一种被约束的线性结构。我们在一个线性结构上给出了一个规定：第一个进去的最后一个出来。这就像有一摞书放在地面上，不允许从中间抽出来，只能从上面一本一本拿一样。这样的线性就是栈。

所谓栈：限定仅在表头进行插入删除的线性结构。因为是后进先出（Last In First Out）

不像普通的线性结构有 CRUD（增删改查）那样丰富的操作。栈仅仅只有进和出两个操作。

栈的顺序存储

压栈 Push

bool Push(T data){if (IsFull() == true)
            return false;
        array[++top] = data;
        return true;
}

出栈 Pop

bool Pop() {if (IsEmpty() == true)
            return false;
        this->temp = array[top--];
        return true;
}

完整代码

#pragma once
using namespace std;
/*
栈的基本操作(C 语言实现)
    Stack CreateStack(int MaxSize); // 生产堆栈，其最大长度是 MaxSize
    int IsFul(Stack S, int MaxSize); // 判断栈 S 是否以满
    void Push(Stack S, ElementType item); // 将元素 item 压入栈
    int IsEmpty(Stack S); // 判断栈 S 是否为空
    ElementType Pop(Stack S); // 删除并栈顶返回元素
*/
template <class T> 
class Stack {
public:
    T * array;// 数组实现的静态栈
    int maxSize;// 数组最大长度
    int top;// 栈指针
    T temp;// 暂存变量
    Stack(const int maxSize) {
        // 有参构造函数
        this->maxSize = maxSize;
        array = new T[maxSize];
        top = -1; //top 指针等于 -1. 表示为空栈
    }
    ~Stack() {delete[] array;
    }

    bool IsFull(){if (this->top == this->maxSize - 1)
            return true;
        return false;
    }
    bool IsEmpty(){if (this->top == -1)
            return true;
        return false;
    }
    bool Push(T data){if (IsFull() == true)
            return false;
        array[++top] = data;
        return true;
    }
    bool Pop() {if (IsEmpty() == true)
            return false;
        this->temp = array[top--];
        return true;
    }
    void clear()
    {
        cout << "top =" << this->top << endl;
        while(top != -1) {Pop();
            cout << temp << " ";
        }
        cout << "清理成功" << endl;
    }
};

两栈共享空间

有关两个栈共享空间的问题，最核心的想法就是：它们是在数组的两端，向中间靠拢，top1，top2 是栈 1 和栈 2 的栈顶指针。只要 top1 ! = top2 这两个栈就可以一直共享空间。

#define MAXSIZE 1000; 
#include <iostream>
using namespace std;
/*
    本程序仅仅是一个思路的提供，并不能单独执行。需要的函数还有很多，请自行补充。这里只有关键性的函数 
     
    有关栈参数的说明：主要是用来区分是哪个栈使用空间。*/
struct Node{int data[MAXSIZE];
    int top1,top2;
}; 

bool Push(Node * S, int data, bool stackNum){
    //stackNum 是两个栈参数
    if(S->top1 + 1 == S->top2)// 栈满
        return false;
    if(stackNum == true)// 栈 1 有元素进入
        S->data[++S->top1] = data;// 先 top1++ 在个元素赋值 
    else 
        s->data[--S->top2] = data; // 先 top2-- 在给元素赋值
    return true; 
}

bool Pop(Node * S, int temp,bool stackNum){// 用 temp 保存 
    if(stackNum == true){if(S->top1 == -1)    return false;
        temp = S->data[S->top--]; 
    }else{if(S->top2 == MAXSIZE)    return false;
        temp = S->data[S->top2++];
    }
    return true;
}

这样的情况通常是当两个栈的空间出现互补的情况时才是用。即一增加一减少。

【注意】共享空间是一个设计上的技巧，请不要滥用，不然后果自负。

栈的链式存储

压栈 Push

bool Push(const T data) {
        LinkStackNode<T> * temp = new LinkStackNode<T>;
        if (temp == NULL) {return false;// 内存申请失败}
        temp->data = data;
        temp->next = top;
        top = temp;
        return true;
    }

出栈 Pop

bool Pop() {if (top == NULL) {return false;}else{
            LinkStackNode<T> * temp = top;
            element = temp->data;
            top = top->next;
            delete temp;
            temp = NULL;
            return true;
        }
    }

完整代码

#pragma once
#include <iostream>
using namespace std;
//top 一定要在链表头
template <class T>
struct LinkStackNode {
    T data;
    LinkStackNode * next;

    LinkStackNode(T info, Link<T> * p = NULL) {
        data = info;
        next = p;
    }
    LinkStackNode() {}
};
template <class T>
class LinkStack
{
private:
    LinkStackNode<T> * top;
    T element;// 临时变量
public:
    LinkStack() {
        LinkStackNode<T>* top = new LinkStackNode<T>;
        top = NULL;
    }
    ~LinkStack() {while (top->next != NULL) {
            LinkStackNode<T> * temp = top;
            top = top->next;
            delete temp;
            temp = NULL;
        }
    }
    T GetElement() {return this->element;}
    bool IsEmpty() {return top == NULL ? true : false;}
    bool Push(const T data) {
        LinkStackNode<T> * temp = new LinkStackNode<T>;
        if (temp == NULL) {return false;// 内存申请失败}
        temp->data = data;
        temp->next = top;
        top = temp;
        return true;
    }
    bool Pop() {if (top == NULL) {return false;}else{
            LinkStackNode<T> * temp = top;
            element = temp->data;
            top = top->next;
            delete temp;
            temp = NULL;
            return true;
        }
    }
    bool GetPop() {
        // 获取当前的栈顶元素
        if (IsEmpty())
            return false;
        element = top->data;
        return true;
    }
};

栈的应用

单调栈

（https://blog.csdn.net/lucky52…）

顾名思义，单调栈就意味这栈内的数据是有序。但是 我们常常说的单调栈是指 出栈 的时候为增才能称之为单调增栈，反之亦然。

我们应该怎么理解这个单调栈呢？

举个例子：

现在有一组数 10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

• 10 入栈时，栈为空，直接入栈，栈内元素为 10。
• 3 入栈时，栈顶元素 10 比 3 大，则入栈，栈内元素为 10，3。
• 7 入栈时，栈顶元素 3 比 7 小，则栈顶元素出栈，此时栈顶元素为 10，比 7 大，则 7 入栈，栈内元素为 10，7。
• 4 入栈时，栈顶元素 7 比 4 大，则入栈，栈内元素为 10，7，4。
• 12 入栈时，栈顶元素 4 比 12 小，4 出栈，此时栈顶元素为 7，仍比 12 小，栈顶元素 7 继续出栈，此时栈顶元素为 10，仍比 12 小，10 出栈，此时栈为空，12 入栈，栈内元素为 12。

stack<int> st;
// 此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组){if (栈空 || 栈顶元素大于等于当前比较元素){入栈;}else{while (栈不为空 && 栈顶元素小于当前元素){
            栈顶元素出栈;
            更新结果;
        }
        当前数据入栈;
    }
}

单调栈的应用

视野总和

描叙：有 n 个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发型总和是多少。
输入：4 3 7 1
输出：2
解释：个子为 4 的可以看到个子为 3 的发型，个子为 7 可以看到个子为 1 的身高，所以 1 +1=2
思路：观察题之后，我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字，然后将每个          结果累计就是答案，但是这里时间复杂度为 O(N^2)，所以我们使用单调栈来解决这个问题。

1. 设置一个单调递增的栈（栈内 0~n 为单调递减）
2. 当遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值

int FieldSum(vector<int>& v)
{v.push_back(INT_MAX);/ 这里可以理解为需要一个无限高的人挡住栈中的人，不然栈中元素最后无法完全出栈
    stack<int> st;
    int sum = 0;
    for (int i = 0; i < (int)v.size(); i++)
    {if (st.empty() || v[st.top()] > v[i])// 小于栈顶元素入栈
        {st.push(i);
        }
        else
        {while (!st.empty() && v[st.top()] <= v[i])
            {int top = st.top();// 取出栈顶元素
                st.pop();
                sum += (i - top - 1);// 这里需要多减一个 1
            }
            st.push(i);
        }
    }
    return sum;
}

柱状图的最大矩形

84. 柱状图中最大的矩形

难度困难 769

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

思路：当前的数字可以向两边拓展，遇到比自己大的就接着拓展，小的就停止，然后用自己的高度乘以拓展的宽度，每次都         跟新最大面积，时间复杂度同样为 O(N^2)，所以我们接着借助单调栈.

1. 设置一个单调递减的栈（栈内 0~n 为单调递增）
2. 当遇到小于栈顶元素的值，我们开始更新数据，因为有可能最大面积就会出现在栈中的序列里
3. 牢记栈中数据永远是有序的，这个问题比较复杂，所以读者不妨对照着代码来理解问题

int largestRectangleArea(vector<int>& heights) {heights.push_back(-1);/ 同理，我们希望栈中所有数据出栈，所以给数组最后添加一个负数
    stack<int> st;
    int ret = 0, top;
    for (int i = 0; i < heights.size(); i++)
    {if (st.empty() || heights[st.top()] <= heights[i])
        {st.push(i);
        }
        else
        {while (!st.empty() && heights[st.top()] > heights[i])
            {top = st.top();
                st.pop();
                //i-top 指的是当前矩形的宽度，heights[top]就是当前的高度
                // 再次强调栈中现在为单调递增
                int tmp = (i - top)*heights[top];
                if (tmp > ret)
                    ret = tmp;
            }
            st.push(top);
            heights[top] = heights[i];
            // 如果这两句不清楚什么意思，请参考 https://blog.csdn.net/lucky52529/article/details/89155694
        }
    }
    return ret;
}

求最大区间

描述：给出一组数字，求一区间，使得区间元素和乘以区间最小值最大，结果要求给出这个最大值和区间的左右端点
输入：3 1 6 4 5 2
输出：60
       3 5
解释：将 3 到 5（6+4+5）这段区间相加，将和与区间内最小元素相乘获得最大数字 60
思路：使用暴力解法求出所有区间，再求出区间的最小值相乘跟新数据，并不是一种很好的算法，所以经过上面俩题的磨         炼，此时我们应该使用一个单调递减栈

1. 设置一个单调递减的栈（栈内 0~n 为单调递增）
2. 当遇到小于栈顶元素的值，我们开始更新数据，因为当前遇到的值一定是当前序列最小

int GetMaxSequence(vector<int>& v)
{
    stack<int> st;
    vector<int> vs(v.size()+1);
    vs[0] = 0;
    for (int i = 1; i < vs.size(); i++)
    {vs[i] = vs[i - 1] + v[i-1];
    }
    v.push_back(-1);
    int top, start, end, ret = 0;
    for (int i = 0; i < v.size(); i++)
    {if (st.empty() || v[st.top()] <= v[i])
        {st.push(i);
        }
        else
        {while (!st.empty() && v[st.top()] > v[i])
            {top = st.top();
                st.pop();
                int tmp = vs[i] - vs[top];
                tmp = tmp * v[top];
                if (tmp > ret)
                {
                    ret = tmp;
                    start = top+1;
                    end = i;
                }
            }
            st.push(top);
            v[top] = v[i];// 与第二题相同的道理，将当前数据的更改最左的 top 下标，防止出现比当前数据更小的数据
            // 这句在这道题里真的超级难理解，但是只要你有耐心相信你可以理解的
        }
    }
    return ret；}

递归（斐波那契数列实现）

$$
F(n)\left\{\begin{array}{ll}
0 & n=0 \\
1 & n=1 \\
F(n-2)+F(n-1) & n > 1
\end{array}\right.
$$

    public long recursive(int n) {if (n <= 0) return 0;
        if (n == 1) return 1;
        return recursive(n - 1) + recursive(n - 2);
    }

递归函数

所谓递归，即自己调用自己。

但是，请一定记住，递归一定要有要给出来的条件。上述斐波那契的函数我们看到返回两个自己想加。而系统会为这两个自己分配新的资源，这两个自己可能又会创建 4 个自己….. 直到最后到了你写的出来的条件为止。然后就要回退了，恢复之前的数据。你也许已经明白递归在编译器中使用栈做到。这其实对于机器一件非常麻烦的一件事，浪费大量资源的只为方便程序员自己的思考。所以我们编程的时候应该尽力避免这个递归写法。

递归和栈

既然编译器使用栈帮我们完成了递归。那我们能不能手动使用栈来代替递归的写法呢？

我们希望能降低我们递归的开销: 递归转换为非递归。（把递归变成迭代）

我们需要手动模拟堆栈的行为。（可以参考树的非递归遍历）

【补充】斐波那契的其他解法

数学公式法

$$
x=c_{1}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+c_{2}\left(\frac{1-\sqrt{5}}{2}\right)^{n}
$$

动态规划

利用动态规划的思想，利用递归分析问题，找到状态转移方程，然后从第一个状态开始迭代到最终状态。

这里的状态转移方程是：f(n) = f(n – 1) + f(n – 2)   (n > 2)
初始状态：f(0) = 0; f(1) = 1;

    public long addition(int n) {int[] result = {1, 2};
        if (n < 2) {return result[n];
        }
        long n1 = 0;
        long n2 = 1;
        long n3 = 0;
        for (int i = 2; i <= n; i++) {
            n3 = n1 + n2;
            n1 = n2;
            n2 = n3;
        }
        return n3;
    }

矩阵乘法

$$
\left(\begin{array}{c}
f(n) \\
f(n-1)
\end{array}\right)=\left(\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}\right)\left(\begin{array}{c}
f(n-1) \\
f(n-2)
\end{array}\right)=\cdots=\left(\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}\right)^{n-2}\left(\begin{array}{c}
f(2) \\
f(1)
\end{array}\right)
$$

let matrix22_mul = (x, y) = >{[x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1],
     x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]
}
let matrix22_pow = (x, n) =>{var r = [[1,0],[0,1]];
    var v = x;
    while (n) {if (n % 2 == 1) {r = matrix22_mul(r, v);
            n -= 1;
        }
        v = matrix22_mul(v, v);
        n = n / 2;
    }
    return r;
}
let fibnacci = n => n <= 0 ? 0 : 
                    matrix22_mul([[0,1],[0,0]], matrix22_pow([[0,1],[1,1]], n - 1))[0][1];

四则运算表达式求值

前缀中缀后缀

前缀（波兰表达式）

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

前缀表达的计算求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

中缀

中缀表达式就是常见的运算表达式，如(3+4)×5-6

后缀（逆波兰表达式）

后缀表达式计算机求值

与前缀表达式类似，只是顺序是从左至右：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

中缀转前缀

1. 初始化两个栈: 运算符栈 s1，储存中间结果的栈 s2
2. 从右至左扫描中缀表达式
3. 遇到操作数时，将其压入 s2

4. 遇到运算符时，比较其与 s1 栈顶运算符的优先级

   1. 如果 s1 为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入 s1
   3. 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 (4-1) 与 s1 中新的栈顶运算符相比较

5. 遇到括号时

   1. 如果是右括号“)”，则直接压入 s1
   2. 如果是左括号“(”，则依次弹出 S1 栈顶的运算符，并压入 S2，直到遇到右括号为止，此时将这一对括号丢弃
6. 重复步骤 2 至 5，直到表达式的最左边
7. 将 s1 中剩余的运算符依次弹出并压入 s2
8. 依次弹出 s2 中的元素并输出，结果即为中缀表达式对应的前缀表达式

中缀转后缀

1. 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压 s2；

4. 遇到运算符时，比较其与 s1 栈顶运算符的优先级：

   1. 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的高，也将运算符压入 s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
   3. 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 (4-1) 与 s1 中新的栈顶运算符相比较；

5. 遇到括号时：

   1. 如果是左括号“(”，则直接压入 s1；
   2. 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃；
6. 重复步骤 2 至 5，直到表达式的最右边；
7. 将 s1 中剩余的运算符依次弹出并压入 s2；
8. 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）

实现

思路

为了实现用栈计算算数表达式的值，需设置两个工作栈：用于存储运算符的栈 opter，以及用于存储操作数及中间结果的栈 opval。

算法基本思想如下：

（1）首先将操作数栈 opval 设为空栈，而将 ’#’ 作为运算符栈 opter 的栈底元素，这样的目的是判断表达式是否求值完毕。

（2）依次读入表达式的每个字符，表达式须以 ’#’ 结尾，若是操作数则入栈 opval，若是运算符, 则将此运算符 c 与 opter 的栈顶元素 top 比较优先级后执行相应的操作，（具体操作如下：(i)若 top 的优先级小于 c，即 top<c，则将 c 直接入栈 opter，并读入下一字符赋值给 c；(ii)若 top 的优先级等于 c，即 top=c，则弹出 opter 的栈顶元素，并读入下一字符赋值给 c，这一步目的是进行括号操作;（iii）若 top 优先级高于 c，即 top>c，则表明可以计算，此时弹出 opval 的栈顶两个元素，并且弹出 opter 栈顶的的运算符，计算后将结果放入占 opval 中。）直至 opter 的栈顶元素和当前读入的字符均为 ’#’, 此时求值结束。

算符间的优先关系如下表所示：

表中需要注意的是 θ1 为 opter 的栈顶元素，θ2 位从表达式中读取的操作符，此优先级表可以用二维数组实现，具体见代码（表来源：严蔚敏《数据结构》）。

程序

#include<iostream>     // 输入的表达式要以 '#' 结尾，如‘5+6*3/(3-1)#’#include<cstring>  
#include<cstdio>  
#include<cctype>  
#include<stack>  
using namespace std;  
  
stack<char> opter;    // 运算符栈  
stack<double> opval;  // 操作数栈  
  
int getIndex(char theta)   // 获取 theta 所对应的索引  
{  
    int index = 0;  
    switch (theta)  
    {  
    case '+':  
        index = 0;  
        break;  
    case '-':  
        index = 1;  
        break;  
    case '*':  
        index = 2;  
        break;  
    case '/':  
        index = 3;  
        break;  
    case '(':  
        index = 4;  
        break;  
    case ')':  
        index = 5;  
        break;  
    case '#':  
        index = 6;  
    default:break;  
    }  
    return index;  
}  
  
char getPriority(char theta1, char theta2)   // 获取 theta1 与 theta2 之间的优先级  
{const char priority[][7] =     // 算符间的优先级关系  
    {{ '>','>','<','<','<','>','>'},  
        {'>','>','<','<','<','>','>'},  
        {'>','>','>','>','<','>','>'},  
        {'>','>','>','>','<','>','>'},  
        {'<','<','<','<','<','=','0'},  
        {'>','>','>','>','0','>','>'},  
        {'<','<','<','<','<','0','='},  
    };  
  
    int index1 = getIndex(theta1);  
    int index2 = getIndex(theta2);  
    return priority[index1][index2];  
}  
  
double calculate(double b, char theta, double a)   // 计算 b theta a  
{switch (theta)  
    {  
    case '+':  
        return b + a;  
    case '-':  
        return b - a;  
    case '*':  
        return b * a;  
    case '/':  
        return b / a;  
    default:  
        break;  
    }  
}  
  
double getAnswer()   // 表达式求值  
{opter.push('#');      // 首先将 '#' 入栈 opter  
    int counter = 0;      // 添加变量 counter 表示有多少个数字相继入栈，实现多位数的四则运算  
    char c = getchar();  
    while (c != '#' || opter.top() != '#')   // 终止条件  
    {if (isdigit(c))   // 如果 c 在 '0'~'9' 之间  
        {if (counter == 1)   //counter== 1 表示上一字符也是数字，所以要合并，比如 12*12，要算 12，而不是单独的 1 和 2  
            {double t = opval.top();  
                opval.pop();  
                opval.push(t * 10 + (c - '0'));  
                counter = 1;  
            }  
            else  
            {opval.push(c - '0');     // 将 c 对应的数值入栈 opval  
                counter++;  
            }  
            c = getchar();}  
        else  
        {  
            counter = 0;   //counter 置零  
            switch (getPriority(opter.top(), c))   // 获取运算符栈 opter 栈顶元素与 c 之间的优先级，用 '>'，'<'，'=' 表示  
            {  
            case '<':               //< 则将 c 入栈 opter  
                opter.push(c);  
                c = getchar();  
                break;  
            case '=':               //= 将 opter 栈顶元素弹出，用于括号的处理  
                opter.pop();  
                c = getchar();  
                break;  
            case '>':               //> 则计算  
                char theta = opter.top();  
                opter.pop();  
                double a = opval.top();  
                opval.pop();  
                double b = opval.top();  
                opval.pop();  
                opval.push(calculate(b, theta, a));  
            }  
        }  
    }  
    return opval.top();   // 返回 opval 栈顶元素的值}  
  
int main()  
{//freopen("test.txt", "r", stdin);  
    int t;     // 需要计算的表达式的个数  
    cin >> t;  
    getchar();  
    while (t--)  
    {while (!opter.empty())opter.pop();  
        while (!opval.empty())opval.pop();  
        double ans = getAnswer();  
        cout << ans << endl<< endl;  
        getchar();}  
    return 0;  
}  

【注意】这里有一个会让人以疑惑的点：所谓 运算符比较优先级的问题。我们在中缀转后缀时才会用到比较运算符优先级。单纯的计算后缀表达式是只需要一个栈的。我们上述的实现中，使用了了两个栈其实是分别进行了这两步的操作——中缀变后缀，后缀计算。

深度优先初步（迷宫问题）

首先迷宫问题的需求很简单：判断是否有出口，如果有可以计算最短路径。

在这里要提出一个深度优先的思路：先盯着一条路走下去，发现死路一条再返回到交叉口，进行下一次选择。一条一条试。

这里有非常重要的一点就是：回溯

而回溯恰恰就是一个栈 Pop 的过程。

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
在本题中也用到的就是回溯，就是把走过的点坐标压栈，遇到无路可走的情况就开始回溯，也就是出栈！
总体思路就是：

现将入口点压栈，走过的地方标记为 2
每走一步就将坐标压栈，判断下一步可以走的地方，如果能走就压栈
当上下左右四个方向都不能走的时候就回溯
直到回溯到入口点还是没有其他方向可以走，那么循环结束，也就意味着没有出口！
使用一个方法判断坐标点是否合法的，注意数组越界的情况，首先不越界，其次坐标点值为 1 的时候才是合法的
对于多通路迷宫首先需要明白当右边出现两个入口点的时候只需要判断列 == N 即可认为是找到了出口
首先下一个点可以走的条件是：该点值为 1 或者该点值比上一个 + 1 还大
每走一步值就 +1，入口点值设置为 2

FROM：https://blog.csdn.net/m0_3803…

// 简单迷宫：int CheckAccess(Pos next)
{
    // 判断越界的情况
    if(next._col >= 0 &&next._row>=0
        && next._col<N && next._row<N)
    { 
        // 1 才是表示通路
        if (maze[next._row][next._col] == 1) 
        {return 1;}
    }
    //return 0 表示不可以通过
    return 0;
}
int MazeGetPath(Pos entry,Pos exit)
{
    Pos cur = entry;//cur 记录起始位置
    
    Stack path;
    StackInit(&path);
    StackPush(&path, entry);// 将起始坐标压栈
    while (StackEmpty(&path))
    {cur = StackTop(&path);
        if ((cur._row == exit._row) && (cur._col == exit._col))
            return 1;
        // 探测下一次可以去的地方
        maze[cur._row][cur._col] = 2;// 标记上一次走过的位置
        // 上
        Pos next = cur;
        next._row -= 1;
        if (CheckAccess(next)) 
        {StackPush(&path, next);
            continue;
        }
        // 下
        next = cur;
        next._row += 1;
        if (CheckAccess(next))
        {StackPush(&path, next);
            continue;
        }
        // 左
        next = cur;
        next._col -= 1;
        if (CheckAccess(next))
        {StackPush(&path, next);
            continue;
        }
        // 右
        next = cur;
        next._col += 1;
        if (CheckAccess(next))
        {StackPush(&path, next);
            continue;
        }

        // 回溯
        StackPop(&path);
    }
    return 0;
}

int CheckAccess(Pos next)
{
    // 判断越界的情况
    if(next._col >= 0 &&next._row>=0
        && next._col<N && next._row<N)
    { 
        // 1 才是表示通路
        if (maze[next._row][next._col] == 1) 
        {return 1;}
    }
    //return 0 表示不可以通过
    return 0;
}

int MazeCheckIsAccess(Pos cur, Pos next)
{
    // 判断越界的情况
    if ((next._col >= 0 && next._row >= 0 && next._col<N && next._row<N)
        &&(maze[next._row][next._col] == 1 || maze[next._row][next._col]>maze[cur._row][cur._col]+1))
    {return 1;}
    //return 0 表示不可以通过
    return 0;
}

int pathsize = 0;

int MazeGetPath(Pos entry,Pos exit)
{
    Pos cur = entry;//cur 记录起始位置
    
    Stack path;
    StackInit(&path);
    StackPush(&path, entry);// 将起始坐标压栈

    maze[entry._row][entry._col] = 2;
    while (StackEmpty(&path))
    {cur = StackTop(&path);
        maze[cur._row][cur._col] = 2;// 标记上一次走过的位置
        //if ((cur._row == exit._row) && (cur._col == exit._col))
        if (cur._col == 5) 
        {
            // 如果只找一条通路则返回
            //return 1;
            //StackDestory(&path);
            if (pathsize == 0||
                StackSize(&path) < pathsize)
            {pathsize = StackSize(&path);
            }
        }
        // 探测下一次可以去的地方
        // 上
        Pos next = cur;
        next._row -= 1;
        if (CheckAccess(next)) 
        {StackPush(&path, next);
            continue;
        }
        // 下
        next = cur;
        next._row += 1;
        if (CheckAccess(next))
        {StackPush(&path, next);
            continue;
        }
        // 左
        next = cur;
        next._col -= 1;
        if (CheckAccess(next))
        {StackPush(&path, next);
            continue;
        }
        // 右
        next = cur;
        next._col += 1;
        if (CheckAccess(next))
        {StackPush(&path, next);
            continue;
        }

        // 回溯
        StackPop(&path);
    }
    return 0;
}


int MazeGetShortPath(Pos entry, Pos exit)
{
    Pos cur = entry;//cur 记录起始位置

    Stack path;
    StackInit(&path);
    StackPush(&path, entry);// 将起始坐标压栈


    maze[entry._row][entry._col] = 2;
    while (StackEmpty(&path))
    {cur = StackTop(&path);
        if (cur._col == 5)
        {
            // 如果只找一条通路则返回
            //return 1;
            //StackDestory(&path);
            if (pathsize == 0 ||
                StackSize(&path) < pathsize)
            {pathsize = StackSize(&path);
            }
        }
        // 探测下一次可以去的地方
        // 上
        Pos next = cur;
        next._row -= 1;
        if (MazeCheckIsAccess(cur, next))
        {maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
            StackPush(&path, next);
            continue;
        }
        // 下
        next = cur;
        next._row += 1;
        if (MazeCheckIsAccess(cur, next))
        {maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
            StackPush(&path, next);
            continue;
        }
        // 左
        next = cur;
        next._col -= 1;
        if (MazeCheckIsAccess(cur, next))
        {maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
            StackPush(&path, next);
            continue;
        }
        // 右
        next = cur;
        next._col += 1;
        if (MazeCheckIsAccess(cur, next))
        {maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
            StackPush(&path, next);
            continue;
        }

        // 回溯
        StackPop(&path);
    }
    return 0;
}

以上的代码也仅仅是核心代码，并不能运行。可以使用 STL 的 Stack 来替换具体的操作。

队列

概念

和栈一样，队列也是一个被约束的线性结构，而我们给队列的规矩是：先进先出。见名知意，就像日常生活中排队一样，先到先得。不允许插队，这里的插队包括进来和出去。所以队列也是只有两个操作。进和出

顺序存储

对于顺序存储，我们会设置 rear 和 front 来指代队尾和队头。这个两个使用数字的下表来模拟指针的。所谓入队和出队其实就是 rear 和 front 的你追我赶。

入队 Push

每次入队 rear+1

出队 Pop

每次出队 front+1

缺陷——引出循环队列

这样会有一个问题，就是最终 rear 到顶不能再加了，front 也追上 rear 也不能再加了。但是我们知道这个队列还是有很多都可以用。

为了解决这个问题引出循环队列。

C++ 实现

//Queue.h
#define MAXSIZE 1000
#include "file.h"

template <class T>
class Queue{
private:
    T queue[MAXSIZE];
    int rear, front;
    T tempData;
public:
    Queue(){rear = front = 0;}
    ~Queue(){}
    int GetCurrent(){return (this->rear - this->front + MAXSIZE) % MAXSIZE;
    }
    T GetTemp(){return this->tempData;}
    bool Push(T data){if((rear+1)%MAXSIZE == front)   return false;
        queue[rear] = data;
        rear = (rear + 1) % MAXSIZE;
        return true;
    }
    bool Pop(){if(front == rear)   return false;
        this->tempData = queue[front];
        front = (front + 1) % MAXSIZE;
        return true;
    }
    bool Clear(){
        int i;
        cout<<endl;
        int length = GetCurrent();
        for(i = 0; i < length; i++){Pop();
            cout<<this->tempData<<" ";
        }
        cout<<endl;
        cout<<i<<endl;
        return true;
    }
};

链式存储

https://blog.csdn.net/weixin_…

入队

void enQueue(LiQueue *lqu,int x)
{
    QNode *p;
    p=(QNode*)malloc(sizeof(QNode));
    p->data=x;
    p->next=NULL;
    if(lqu->rear==NULL)
        lqu->front=lqu->rear=p;
    else
    {
        lqu->rear->next=p;
        lqu->rear=p;
    }
}

出队

int deQueue(LiQueue *lqu,int x)
{
    QNode *p;
    if(lqu->rear==NULL)
        return 0;
    else
        p=lqu->front;
    if(lqu->front==lqu->rear)
        lqu->front=lqu->rear=NULL;
    else
        lqu->front=lqu->front->next;
    x=p->data;
    free(p);
    return 1;
 
}

队列的应用

队列解决约瑟夫问题

额外给规定，满足的留下，不满足的出队。

// 队列实现约瑟夫问题
# include<stdio.h>
# include<queue>
using namespace std;

queue<int> Q;

int result(int n,int m)
{while(Q.empty()==false)// 清空队列
        Q.pop();

    int i,j;
    for(i=1;i<=n;i++)
        Q.push(i);

    j=m;
    
    while(n>1)
    {while(j>1)
        {int k=Q.front();
            Q.pop();
            Q.push(k);
            j--;
        }
        Q.pop();
        j=m;
        n--;
    }

    return Q.front();}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {if(n==0&&m==0)
            break;
        
        printf("%d\n",result(n,m));
    }
    return 0;
}

单调队列

https://blog.csdn.net/ljd2017…

单调队列的理解和单调栈 一样。

给出百科解释：不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小的元素。

用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值

举个例子：有 7 6 8 12 9 10 3 七个数字，现在让你找出范围（i-4，i）的最小值。

那我们就可以这样模拟一遍。

先初始化{0}（表示 i = 0 时的值）

i=1 ->{0}（表示 i =1, 时，在其范围内最小的值为 0）-> 7 进队 {7}；

i=2->{7}（表示 i =2, 时，在其范围内最小的值为 7）-> 6 比 7 小，7 出，6 进 {6}；

i=3-> {6}（表示 i =3, 时，在其范围内最小的值为 6）->8 比 6 大，8 进 {6, 8}；

i=4->{6, 8}（表示 i =4, 时，在其范围内最小的值为 6）-> 12 比 8 大，12 进 {6, 8 , 12};

i=5-> {6, 8 , 12}（表示 i =4, 时，在其范围内最小的值为 6）-> 9 比 12 小，12out，9 比 8 大，9 进 {6，8, 9}；

i=6-> {6，8, 9} 但是 单调队列中元素 6 的下标是 2，不在（2, 6], 中，故 6 out，这就是单调队列的精髓了。故单调队列为

{8,9}（表示 i =5, 时，在其范围内最小的值为 8）->10 比 9 大，10 进 最终 单调队列为{8，9, 10} ;

i=7->{8，9, 10}（表示 i =6, 时，在其范围内最小的值为 8）-> 3 比单调队列为{8，9, 10} 的任意值都小，故全 out，最终集合为 {3}；

相信大家看完这个例子了解得有些吧，再次重申一遍，单调队列的核心（我认为的哈）：得到当前的某个范围内的最小值或最大值。要不是这样的话，那还有必要这么麻烦找吗，直接找前面最小的就好了，可事实不是这样，题目是有限制的，规定在某个范围内找。

给出例题：
Description
一个长度为 n 的整数序列，从中找出一段不超过 m 的连续子序列，使得整个序列的和最大。

例如：1, -3, 5, 1, -2, 3

当 m = 4 时，sum = 5+1-2+3 = 7

当 m = 2 或 m = 3 时，sum = 5+1 = 6

Input
多测试用例，每个测试用例：

第一行是两个正数 n, m (n, m ≤ 300000)

第二行是 n 个整数

Output
每个测试用例输出一行：一个正整数，表示这 n 个数的最大子序和长度

Sample Input
6 4
1 -3 5 1 -2 3

Sample Output
7

使用单调队列：

思路：

我们先把序列的前 i 项和加起来并存到一个数组 sum[]上，那么任意连续的子序列和就为 sum [ i] – sum[j] (i>j && j>i-m)。

那么我们就可以跟上述例子一样，一直更新就好了，每次找出在（i-m，i）范围内的最小 sum[j]值

//code1:
#include<cstdio>
#include<algorithm>/// 单调队列，#include<cstring>
#include<list>
using namespace std;
typedef long long LL;
const int maxn=300010;
LL sum[maxn];
list <int > que;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))// 其功能是循环从输入流读取 m 和 n，直到遇到 EOF 为止，等同于 while (scanf("%d%d",&m,&n)!=EOF)。{que.clear(); /// 清除 
        sum[0]=0;
 
        for(int i=1;i<=n;i++)
        {scanf("%lld",&sum[i]);
            sum[i]=sum[i-1]+sum[i]; /// 求前 i 项和
        }
        
        /// 初始化
        LL maxs=sum[1];
 
        que.push_front(1);
 
        for(int i=2;i<=n;i++)
        {while(!que.empty()&&i-que.back()>m) /// 此步是判断是否在范围（i-m,i)内，不在就 pop
                que.pop_back();
 
            maxs=max(maxs,sum[i]-sum[que.back()]); 
                    /// 求最大值，sum[i]-sum[min]，表示前 i 个中找到最小的来减，sum[min]就是单调队列的尾部 sum[que.back()]
                    
            while(!que.empty()&&sum[i]<sum[que.front()])  /// 更新单调队列，比 sum[i]大的值都去掉
                que.pop_front();
 
            que.push_front(i); /// 最后将下标 i 入队
 
        }
        printf("%lld\n",maxs);
    }
    return 8;
}

//code2
#include<cstdio> /// 单调递增序列（但保证最可能小）#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=300010;
LL sum[maxn];
LL index1[maxn]; /// 存储下标
int main()
{
    LL n,m;
    while(~scanf("%lld%lld",&n,&m))
    {sum[0]=0;
        for(int i=1;i<=n;i++){scanf("%lld",&sum[i]);
            sum[i]+=sum[i-1]; /// 求前 i 项和
        }
        
        /// 初始化
        int left=1,right=1;
        index1[1]=1;
        LL tmax=sum[1];
 
        for(int i=2;i<=n;i++)
        {while(index1[left]<i-m) left++; /// 不在范围（i-m，i）内，左移就好了
 
            tmax=max(tmax,sum[i]-sum[index1[left]]); /// 减去范围（i-m，i）内最小的值
 
            while(right>=left&&sum[i]<sum[index1[right]]) /// 排除比值 sum[i]大的
                right--;
            right++;
            index1[right]=i; /// 将下标添加进去
        }
 
        printf("%lld\n",tmax);
    }
    return 0;
}

广度优先初步（迷宫问题）

所谓广度优先，以迷宫为例：如果有 5 条岔路口。则每个路口各走一格，第二轮也是每个路口在前进一格。

#include<stdio.h>
#define MaxSize 100
#define M 8
#define N 8
typedef struct
{int i,j;    // 方块在迷宫中的坐标位置(i,j)         
    int pre;    // 本路径中上一方块在队列中的下标   
} SqQueue; 
SqQueue Qu[MaxSize];  // 定义顺序非循环队列
int front=0,rear=0; 
int mg[M+2][N+2]=
{{1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};
void print(SqQueue Qu[],int front)
{   int k=0;
    for(int i=front;i>0;i=Qu[i].pre)
    {printf("(%d,%d)",Qu[i].i,Qu[i].j);
        k++;
        if(k%5==0)   // 每输出每 5 个方块后换一行
           printf("\n");
    }
}
bool mgpath1(int xi,int yi,int xe,int ye)    // 搜索路径为:(xi,yi)->(xe,ye)
{   int i, j, di, i1, j1;
    rear++;
    Qu[rear].i=xi; Qu[rear].j=yi; Qu[rear].pre=-1; //(xi,yi)进队
    mg[xi][yi]=-1;                // 将其赋值 -1, 以避免回过来重复搜索
    while(front!=rear)            // 队不空循环
    {   front++;
        i=Qu[front].i; j=Qu[front].j; // 出队
        if (i==xe && j==ye)        // 找到了出口, 输出路径
        {print(Qu, front);    // 调用 print 函数输出路径
            return true;        // 找到一条路径时返回真
        }
        for (di=0;di<4;di++)    // 循环扫描每个方位
        {switch(di)
          {
            case 0:i1=i-1;   j1=j; break;
            case 1:i1=i;  j1=j+1; break;
            case 2:i1=i+1;  j1=j; break;
            case 3:i1=i;   j1=j-1; break;
          }
          if (mg[i1][j1]==0)
          {   rear++;
              Qu[rear].i=i1; Qu[rear].j=j1; 
              Qu[rear].pre=front;    //(i1，j1)方块进队
              mg[i1][j1]=-1;    // 将其赋值 -1
          }
        }//for
    }//while
    return false;
}//mgpath1
 
int main()
{if (!mgpath1(M,N,1,1))
        printf("该迷宫问题没有解!");
    return 1;
}