队列和栈的使用
标签（空格分隔）： algorithm
队列和栈的应用
1.队列的应用
- 队列是一种常见的数据结构，主要的特性先进来的元素会先出去，也就是First In First Out:FIFO ，所以适合具有这个特性的算法来使用，比如图的广度优先搜索、二叉树的层次遍历等。
- 所以队列和生活中的排队非常相似，先来的先服务，后来的后服务。
2.栈的应用
- 栈和队列的特性不一样，队列的特性是先进先出，栈是先进后出
- 栈的出口和入口只有一个，都是从一个地方进入或者出去，所以进去的时候，就不能出来，而且出来的时候，只有最后进入的能够出来
- 比较适合于先进来等着，等到满足某种条件的时候，才按照后来的先处理
- 想起了进电梯的场景，一般都是先进电梯的最后出来(考虑到同一楼层的)
5.栈使用举例
- 这里有个题目说的是如何判断一个括号字符串包含的括号对：'{','}','[',']','(',')' 是否合理
- 假设有个字符串"{}{}(){}[]{]["，其实括号的匹配是有一定的规律的，']',')','}' 只要出现右括号的地方，那么它前面必须要有一个其对应的左括号才行，如果不是对应的左括号，那么就是不合理的括号串。类似消消乐，只是条件是最近的括号匹配可以消除
- 具体的就是，再扫描字符串的过程中，首先把左括号存起来，遇到右括号的时候，看看离这个右括号最近的左括号（栈顶的左括号）是否合理，把合理的括号对匹配上，不合理的直接返回整个括号字符串不合理。
- 最后如果是完全匹配，那么栈为空，只要栈非空，那么说明不是完全匹配
- 从上面的描述中能看出来，后扫描到的左括号要存起来，但是有需要在遇到右括号的时候，匹配最近的左括号，有后进先出的特性吧，这就是一个很典型的栈的应用。
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(int i= 0; i < s.length(); ++i){
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') { // 左括号放入栈中，等待匹配
stack.push(c);
}else { // 右括号，进行匹配
/**1.栈为空，无法匹配false
* 2.匹配上则把左括号匹配出栈
* 3.没有匹配上那么false
* */
if(stack.empty())
return false;
char ch = stack.peek();
if(c - ch == '}' - '{' || c - ch == ']' - '[' || c - ch == ')' - '(')
stack.pop();//把匹配的左括号出栈
else
return false;
}
}
/**如果栈为空，那么完全匹配*/
return stack.empty();
}
- 值得提的是，栈的应用非常广泛，例如：函数调用函数调用，从CPU角度来看，CPU首先会保存调用者A的现场内容(变量等情况)，这个时候会把这个现场情景进栈(也就是数据信息)，保存在栈中。然后去执行A调用的函数B，如果这个时候B还调用了函数C，那么在CPU转去执行C的时候，还是会类似的把B的现场进栈，一直到C函数执行完，再从栈中把B现场出栈，继续执行B，然后B执行完，把A的现场出栈，执行A，直到所有的程序执行结束。
/**main ->
* A ->
* B ->
* C 执行完
* <-C
* <- B
* A <-
* 执行A ->调用 B ->调用C c返回->执行B B返回->执行A
* | | | | | | | | | |
* | | | | | | | | | |
* | | | | | B | | | | |
* | | | A | | A | | A | | |
* |main| |main| |main| |main| |main|
*
*
* **/
- 从上面的调用可以看出来，函数的调用也是有成本的，如果函数嵌套调用的越多所消耗的资源，栈数据也就越大
- 如果上面的函数B,C都是A函数的话，那么就会出现A调用自己的情况，这就是函数的递归调用
- 所以函数的递归是通过栈这种数据结构来实现的，后面大多数的递归，都能通过使用栈的方式来实现。
