数据结构之 栈与队列
栈
先进后出,即只能从一端入栈,出栈,可以把他想象成一个仅有一只开口的瓶子
队列
先进先出,一端只能进队.另一端只能出队.他是一个两端都开口的瓶子
解决问题
- 括号匹配问题
判断括号是否正确匹配,可以用栈的思想解决.括号一共有{[(,}])六种,从第一个字符开始,如果是左括号,就将他放入栈中,如果遇到右括号,就将它与栈尾的括号比对,若果匹配,就让队尾的括号出栈,不匹配则直接证明括号匹配不正确.然后继续前面的步骤,直至遍历到字符串结尾,到结尾处时栈为空则括号正确匹配,否则就错误. - 深度优先搜索 -栈
- 广度优先搜索 -队列
队列及栈的互相替换
- 两个栈来模仿队列
现在有数字 1.2.3,先入栈A 1-2-3(尾),要实现出队列(1-2-3),先将栈A的整体出栈放入栈B 3-2-1(尾),着时再将栈B中的数据出栈,顺序为1-2-3,便成功的用两个栈模拟了队列 - 两个队列来模拟栈
继续上边的模型,数字1.2.3入队列A 1-2-3(尾),要实现出栈(3-2-1),先将队列A整体出队列进入队列B()