【堆栈】【堆】【栈】【队列】——算法学前—必学基础知识

上面这个是：什么是堆栈。我这儿就不再介绍。如果不懂的朋友，可以去看看。

小妖也不是太精，只能举例子来给大家说明。说得不好的，多多指点。

按键里面没有堆栈的概念。因为没有地址操作（个人理解，大概是那么回事）。

小妖只能模仿。利用数组做。

堆：

我这儿说的堆，差不多就是树了。

树_百度百科

比较懒，直接用网上的图了，这儿是满二叉树。当然，这个树可以不是二叉树，也可以不是满的。

我先做一个三层的二叉树。让大家明白树怎么做。

1. Dim 堆
2. 堆 = array("a", 1, 2) //这儿的1,2是没有意义的，只是用来占位而已。如果没有占位的话，下面的赋值不成功。这儿是根节点。
3. 堆(1) = array("b", 1, 2)//这儿是左子节点
4. 堆(2) = array("c", 1, 2)//这儿是右子节点
5. 堆(1)(1) = array("d")//这儿，因为已经没有子节点，所以数组只有这个元素。因为为了便利，我这儿还是用数组。
6. 堆(1)(2) = array("e")
7. 堆(2)(1) = array("f")
8. 堆(2)(2) = array("g")
9. TracePrint 遍历树(堆)
10. Function 遍历树(父节点)
11. Dim 返回值,i
12. For i = 0 To UBound(父节点)
13. If i = 0 Then //如果是0 那么返回当前节点值
14. 返回值=父节点(0)
15. Else //返回子节点值，用了递归
16. 返回值 = 返回值 & 遍历树(父节点(i))
17. End If
18. Next
19. 遍历树=返回值
20. End Function

复制代码

上面，我们定义了一个二叉树，根节点是a。并且实现遍历这个二叉树。

这个树，可以写成任意树。不仅仅是二叉树。

当然，定义树的时候，那样一个一个定义比较费力。建议用数组或者是什么来定义。

小妖这儿就不详细说了。有兴趣的同学可以回帖讨论。

当然了，后面小妖还会继续讲栈和队列（实际上上面的代码已经使用了栈，因为这儿使用了递归）。

[backcolor=rgb(247,247,247)]估计大家没意识到这个堆的用处。我们来举个例子，比如我们要在一个很大的学校找一个人。那么如果我们直接一个一个的找，估计找几天，大的学校估计几个月。如果我们用堆。

1. Dim 学校名称
2. 学校=array("XX大学",1,2,3,4,5,6,7)
3. For i = 1 To UBound(学校)
4. 学校(i) = array(i & "系", 1, 2, 3, 4, 5, 6, 7)
5. For j = 1 To UBound(学校(i))
6. 学校(i)(j) = array(i & "班", 1, 2, 3, 4, 5, 6, 7)
7. For z = 1 To UBound(学校(i)(j))
8. 学校(i)(j)(z) = (i-1) * 7 * 7 (j-1) * 7 z
9. Next
10. Next
11. Next
12. //如果我们想查找 XX大学，3系，1班是否有 10号
13. j="没有这个人"
14. For i = 1 To UBound(学校(3)(1))
15. If 学校(3)(1)(i) = 102 Then
16. j="有这个人"
17. Exit for
18. End If
19. Next
20. TracePrint j
21. //如果我们需要列出 XX大学，4系，2班 所有人员名单
22. For i = 1 To UBound(学校(3)(1))
23. TracePrint 学校(3)(1)(i)
24. Next

复制代码

甚至说，我们可以知道这个学校有几个系，每个系有哪些班级，每个班级有哪些人。

小妖这儿仅仅是抛砖引玉。更多的应用，估计其他语言在树这个运用上已经出神入化。小妖就不再细说。有想法的同学可以跟贴讨论。

栈：

栈就比较常用了。

栈就像一个楼梯，每次增加一个数的时候，你就得往上爬一格。每次减少的时候，你就往下走一格。

54321

像上面这个，从最下面开始装值，如果增加就往上，如果减少就往下。

例子：

我们做一个从1加到5.

1. TracePrint 累加(5)
2. Function 累加(累加值)
3. If 累加值 = 1 Then
4. 累加 = 1
5. Else
6. 累加=累加值 累加(累加值-1)
7. End If
8. End Function

复制代码

第一次运行的时候，参数累加值为5，累加值不等于1所以运行[backcolor=rgb(247,247,247)]累加=5 累加(5-1)。

所以，这时候最下面的那个栈已经装入值5了，如下：

[backcolor=rgb(247,247,247)]5 累加(5-1)

这儿其实还没运行完，因为这儿的累加(5-1)还需要再运行。

所以是运行累加(5-1),其实就是运行:累加(4)。

和上面一样，只是参数变成了4。

所以这儿的栈在之前的基础上，上移一格，进行入栈操作。

[backcolor=rgb(247,247,247)]4 累加(4-1)[backcolor=rgb(247,247,247)]5 累加(5-1)

这样。一直到瞒住参数=1。

这时候，就开始返回值了。

累加(1)=1[backcolor=rgb(247,247,247)]2 累加(2-1)[backcolor=rgb(247,247,247)]3 累加(3-1)[backcolor=rgb(247,247,247)]4 累加(4-1)[backcolor=rgb(247,247,247)]5 累加(5-1)

这样满足条件之后，开始返回值。

[backcolor=rgb(247,247,247)]累加 = 1

这是累加函数返回值，而且这个值是1。

所以，累加(2)=2 累加(1)=2 1=3

累加(3)=3 累加(2)=3 3=6

累加(4)=4 累加(3)=4 6=10

累加(5)=5 累加(4)=5 10=15

这样就把1加到5的值计算出来了。

如果是1加到100，只需要把参数改成100就可以了。

如果是5加到100，只需要判断参数等于5的时候，就累加=5这样。

实际上，上面就是递归。它使用了栈。所以说，递归实际上是耗费了内存的。如果过于庞大的数字，建议不要直接使用递归。

最后，我们来说队列。

其实，队列和栈是一样的。只是，队列是先进先出。

比如，我们这儿有一个队列。

1. Dim 列队
2. 列队 = array(1, 2, 3, 4, 5)
3. Call 出列()
4. TracePrint Join(列队)
5. Call 入列(10)
6. TracePrint Join(列队)
7. Sub 出列()
8. 列队(0)="0|"&列队(0)&"|"
9. t = 列队(0)
10. 列队 = Filter(列队,t ,0)
11. End sub
12. Sub 入列(值)
13. t=UBound(列队)
14. Redim Preserve 列队(t 1)
15. 列队(t 1) = 值
16. End Sub

复制代码

上面代码，写的是一个队列。出列是第一个出去，入列的是在后面入列。

当然了，你现在还不明白这有什么用。我们来举个例子。

1. dim 环 //没办法，必须要用全局函数来装数组，要不然无法从新定义
2. TracePrint 约瑟夫环(100,3) //显示函数运行结果
3. Function 约瑟夫环(N,k)
4. Dim i,t //定义变量
5. For i = 1 To N //给换赋初始值
6. 环=环&"|"&i
7. Next
8. 环 = Split(right(环,len(环)-1), "|")//因为多出一个 "|" 所以要用 right 去掉，然后用 split 转换为数组
9. Do //循环
10. For i = 1 To k - 1//当数到 k-1 的时候，出列、并且入列到后面
11. t = 出列
12. Call 入列(t)
13. Next
14. Call 出列 //当为K值时，剔除
15. Loop Until UBound(环)=0 //直到 换的最大下标为0结束
16. 约瑟夫环 = 环(0) //返回结果
17. End Function
18. Function 出列()// 出列函数
19. Dim t
20. 出列 = 环(0)
21. 环(0)="|"&环(0)&"|" //加 "|" 是为了区别出来是这个值，用 Filter 才不会出错
22. t = 环(0) // 用来做第二个参数， Filter不能调用自身做参数。
23. 环 = Filter(环, t, 0) //利用 Filter 去除第一个数组元素
24. End Function
25. Sub 入列(值)
26. Dim t
27. t=UBound(环)
28. Redim Preserve 环(t 1)
29. 环(t 1) = 值
30. End Sub

复制代码

上面是我利用入列出列写的约瑟夫环。主要思想为，数到的人就出列。如果数到并且不为K，那么就入列到后面去。如果是K，那么就退出环。一直到剩下最后一个人。代码都在上面了，我已经把出列和入列操作融合到代码里面了。仔细看下就明白。这样，小妖就把队列说完了。当然了，实际运用的时候，比如广度优先算法的核心就是这个队列。还有很多算法，他们都是基于以上3个方法。所有如果大家把这几个看懂了，很多很多算法，也就不在话下了。

最后，如果有看不懂的，或者什么意见建议，欢迎加群讨论！554127455