栈和队列的定义
栈
和
队列
都是一种基本的数据结构，可以用来存放数据，
栈
的顺序是先入后出，而
队列
的顺序是先入先出，我们可以通过它们实现不同很多特定的功能
比如在安卓中，遍历一个布局文件里所有子view，并打印它们。
首先我们先思考一下这个问题，在Android的布局文件的结构，我们可以把它类比做数据结构中的多叉树。
上图就是一个常见的
RootView
的结构，我们可以通过
getChildAt(int)
这个方法，来遍历这个
RootView
并获取它的所有子View。
方法一：递归
当我们想要遍历一个ViewGroup所有子View的时候，我们通常想到的就是通过递归，而递归也是最容易写出来的。
直接上代码：
fun printAllChildren(rootView : View){
print(rootView)
if(rootView is ViewGroup){
for(index in 0 until rootView.childCount) {
val view = rootView.getChildAt(index)
printAllChildren(view)
}
}
}
递归的优点很明显，代码清晰，浅显易懂，但是缺点也同样明显，就是当RootView的层级较深的时候，可能会引起栈溢出，而程序会抛出
StackOverflowError
这个错误。这是因为在JVM中，每当启动一个新的线程，JVM都会为为其分配一个java栈，而每调用一个方法，都会被封装成一个栈帧，进行
压栈
的操作；当方法执行完毕，就会进行
弹栈
的操作。
而
StackOverflowError
这个错误又是怎么产生的呢，这是因为在每个栈帧中，都会保存该方法中的一些局部变量、返回地址等数据，这些都是会占用内存，而递归每调用一次方法，就会
压栈
产生一个新的栈帧并消耗内存，但是一直到最后不会再调用新方法，才会执行
弹栈
的操作，所以有可能在执行的过程当中超过了内存的限制，就报出
StackOverflowError
所以我们需要考虑通过其他的方法来遍历ViewGroup。
方法二：栈和队列
之前我们说过，安卓的布局结构其实就是一个多叉树，而在数据结构中遍历多叉树有两种方式，
广度优先
和
深度优先
。如下图：
2.1 广度优先
广度优先其实就是对多叉树的每一层节点依次访问，当一层访问完毕，再进入下一层。就是遵循
树的层数
，一层一层地遍历。
广度优先算法，是非常适合先入先出的队列来实现的，每层子View依次进入队列，然后取出队头的子View并处理，如果该子View是ViewGroup，那么再取出它所有的子View放入队尾。
所以上图如果通过广度优先来遍历，那么最后的结果就是：
A -> B -> C -> D -> E -> F
，通过图来看一下：
java中，可以使用
LinkedList
来完成队列的功能，因为它实现了
Deque
双端队列接口，代码实现：
fun printAllChildren(rootView : View){
val viewDeque = LinkedList<View>()
var view = root
viewDeque.addLast(view)
while(viewDeque.isNotEmpty()){
view = viewDeque.poll() //取出队列第一个元素
print(view)
if(view is ViewGroup){
for(index in 0 until view.childCount){
val childView = view.getChildAt(index)
viewDeque.addLast(childView)
}
}
}
|
2.2 深度优先
深度优先则是对每个分支的路径，深入访问到叶子节点之后，才会访问其他的节点。
深度优先算法，是非常适合先入后出的栈来实现，对一个子View先做压栈操作，再弹栈，输出该View，然后遍历得到该子View所有的子View并做压栈操作，再弹栈输出栈顶的子View，重复上述的操作。
所以如果通过深度优先算法来遍历，那么最后得到的结果就是
A -> C -> F -> B -> E -> D
， 通过图来看一下：
我们还是用
LinkedList
来实现栈，因为LinkedList有
push()
和
pop()
方法来模仿
压栈
和
弹栈
的操作，代码如下：
fun getAllChildren(rootView: View){
val viewStack = LinkedList()
var view = rootView
viewStack.push(view)
while(viewStack.isNotEmpty()){
view = viewStack.pop() //弹出栈顶的元素
print(view)
if(view is ViewGroup){
for(index in 0 until view.getChildCount()){
val childView = view.getChildAt(index)
viewStack.push(childView)
}
}
}
}
总结
我们通过三种方法来实现了ViewGroup的遍历，明白了ViewGroup其实就是一种多叉树的数据结构，也明白了栈和队列在安卓中的运用，当然上面的场景也可以变换，比如统计一个
ViewGroup所有子View的数量
、
自己实现一个方法查找指定id的子View
等等。
转载请注明出处