队列和栈的使用

标签（空格分隔）： 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调用自己的情况，这就是函数的递归调用
• 所以函数的递归是通过栈这种数据结构来实现的，后面大多数的递归，都能通过使用栈的方式来实现。