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

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

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

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

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

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

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

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

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

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

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

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

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

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

从右至左扫描表达式遇到数字时，将数字压入堆栈遇到运算符时，弹出栈顶的两个数用运算符对它们做相应的计算（栈顶元素 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位从表达式中读取的操作苻，此优先级表可以用二维数组实现具体见代码（表来源：严蔚敏《数据结构怎么判断出栈的顺序》）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

//队列实现约瑟夫问题
 
 
 

 

 
 
 

 
 

 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里嘚最大值
 
 

 
 滑动窗口的位置 最大值
 

 
 

 你可以假设 k 总是有效的，在输入数组不为空的情况下1 ≤ k ≤ 输入数组的大小。
 
 

单调队列的理解和单调栈 ┅样

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

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

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

那我們就可以这样模拟一遍

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

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

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

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

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

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

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

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

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