队列与栈的原理及特点（概括，详解在下面）
栈 Stack
1.先进后出
2.入栈（进栈）push
3.出栈（弹出）pop
4.栈的本质是一个特殊的线性数组（表）。特殊在只能在表尾进行插入和删除操作。
5.有顺序栈和链栈两种（这里自己去了解一下吧）
队列 queue
1.先进先出
2.表尾插入，表头删除
3.队列也是一种线性表
4.顺序队列和链对，以循环顺序队列更加常见
正题前的一个问题（答案在下文）
栈的浅谈
&emsp；栈提供push和pop接口，所以栈不提供迭代器（iterator），及不能遍历它。所以STL中栈往往不被归为容器，而被归类为容器适配器container adaapter。
&emsp；那就带来一个问题，STL中栈用什么实现呢？ 上图
可以看到栈可以用数组或者链表来实现，vector，deque，list。
用栈实现队列
push（x）----将一个元素放入队列的尾部
pop（）----- 从队列首部溢出元素
peek（）----- 返回队列首部的元素
empty（） ----- 返回队列是否为空
注意
&emsp；在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
&emsp；如果进栈和出栈都为空的话，说明模拟的队列为空了。
正题
&emsp；拿一道题来说吧。匹配括号，及字符串要有" ( " , " ) " , " [ " , " ] " , " { " , " } " 成对出现。常见于我们敲代码括号要匹配。
&emsp；三种情况：
1.第一种，字符串左方向括号多余不匹配。
2.第二种，括号没有多余，但类型不对。
3.第三种，字符串右方向括号多余不匹配。
&emsp；而我们需要的是运用栈的先进后出，或者叫后进的先出，依次遍历数组字符串，读到的左括号放进栈中，遇到匹配就出栈，此时就会有三种情况。
1.已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false。
2.遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false。
3.遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false。
当遍历完，栈时空的，那说明完全匹配。
bool IsValid(string s)
{
stack<int> st;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
st.push(')');
else if (s[i] == '{')
st.push('}');
else if (s[i] == '[')
st.push(']');
else if (st.empty() || st.top() != s[i])
return false;
else
st.pop(); // st.top() == s[i]
}
return st.empty();
}
*这里其实递归就是使用了栈，每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因*
由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误
网友评论