Android程序员的数据结构算法回顾（一）-栈，队列

前言

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，这两种基本的数据结构在实现各种算法中起到了重要的作用。比如需要用递归来解决的问题就得利用栈结构，队列在数据缓存，搜索中起到了关键作用。

1.栈

栈是一种后进先出的线性数据结构，就好像你在洗盘子，洗好的盘子一个一个叠起来，而被拿去乘菜时需要从最顶端开始取。

这种数据结构的实现比较容易，java中已经提供了Stack类，而往往我们不需要直接使用这种数据结构来解决某个问题，在我的记忆里我唯一用到过的就是在计算几何里面一个凸包算法。用处最大的其实还是好好理解这种结构的作用。

比如斐波那契数列 f(n) = f(n-1)+f(n-2)

1 1 2 3 5 8 13 ......

也就是问题的求解需要子问题的答案来求解。这里我们只知道f(1) = 1 ,f(2) = 1;假如我们现在要求 f(5)。那么如何利用栈结构来求解呢？其实程序的每一次方法调用都是一个压栈的过程，而栈结构会保存我们每一次调用方法的参数以及返回结果。

需要知道f(5)，那先帮我求出f(4)跟f(3)吧，需要知道f(4),那先帮我求出f(3)跟f(2)吧.....以此类推直到发现已经求出了f(1)跟f(2)，此时压栈过程结束,开始出栈。依次把答案返回给等待结果的栈。所以在递归的时候一定要写出口，不然一直递归下去，栈就满了，程序就要抛StackOverFlow异常了。这种调用栈其实就是Java虚拟机栈，虚拟机给他分配的空间是有限的。当你的程序需要深层次调用时，利用递归肯定是不行的。递归的代码很简单，主要是理解它的工作过程。

再举个稍微复杂点的例子吧，比如数组求最大值？

比如现在数组元素有10个，如何来分解这个问题？那就把数组分半呗，分别求出第1-第5个的最大值，第6-第10个的最大值，然后取最大值不就是整个数组的最大值么？依次类推，1-5的最大值不就是 1-3,4-5两个区间取最大值么。最后当你的数组划分成只剩下一个元素的时候，他本身就是最大值了，然后再慢慢的出栈，把之前遗留的求区间最大值问题一个个返回得到最终答案。为了简单，下面画出6个元素的时候方法栈调用情况：

一步一步压栈直到数组长度为1，最后一步步出栈得到各个子区间的最大值，最终合并答案得到结果。

所以对于利用子问题答案来求解的问题，基本上都可以利用栈结构来解决。还记得大学学过的归并排序？快速排序么？其实都是通过分解子区间来提升效率的方式。只要理解了栈结构，这些都可以好好掌握。

2.队列

队列是一种先进先出的线性数据结构，当然这是对于最基本的队列单向队列而言。队列就好像你在食堂排队一样，你总是要排在队尾，打饭的一头在队首。队列也一样，插入元素的一端叫做队尾，取元素的一端就做队首。当然在实现的时候为了能充分利用内存空间，把队列设计成一种环形结构（循环队列），本文主要讨论如何利用队列来解决实际问题，对于其他衍生的队列等不作讨论。

队列比较简单，其实就是对数组的一系列操作，java没有直接提供相关的Queue类，而是提供了一个Queue接口，声明了实现类必须实现的offer(添加元素到队尾) peek(取出队首元素并删除) ,poll(返回队首元素不删除)等方法。LinkedList实现 了Queue接口，直接拿来当队列用就行了。

对于队列的运用，二叉树的广度优先遍历是最经典的一个

比如上面那棵二叉树，广度优先遍历就是从上到下，从左到右遍历一遍。然而对于程序而言，这样一棵树状结构的数据结构存在内存当中，计算机只知道每一个节点的相邻节点是哪一个。那如何按照这种顺序来遍历呢？队列就能起到很好的作用。

1.A先入队列，然后从队首取出元素A，找到相邻的节点B C分别入队列,A出队列

队列内： B C 已遍历 :A B C

2.然后取出队首元素B，找到B相邻的节点 D，加入队列。B出队列。

队列内： C D 已遍历 :A B C D

3.然后取出队首元素C，找到C相邻节点E F分别入队列，C出队列

队列内： D E F 已遍历 :A B C D E F

4.D E F分别出队列发现都没有了相邻节点，二叉树广度优先遍历完毕。

普通队列比较简单，这里就不贴代码分析了。队列涉及的数据结构还有很多，比如优先队列，单调队列，双端队列等等。以后有机会也会一一讲解。

二叉树的深度优先遍历就是利用递归的方式，利用上面栈结构就能写出代码了，自己练习吧。