数据结构与算法-栈与队列【五】

￡神魔★判官ぃ 2023-06-27 06:13 22阅读 0赞

标签：栈 队列 递归 尾递归 尾调用

--------------------

栈和队列都是特殊的线性表

普通的线性表，无论是以顺序存储结构表示的顺序表、链式存储结构表示的链表 可以在任意的位置【1~N+1】执行插入和删除操作。

而栈和队列，规定只能在表头和表尾部进行操作。

> **栈是先进后出、后进先出 只能在表尾（栈顶）进行插入（入栈）和删除（出栈）。通常用Stack来表示**

常见使用场景： 1，括号等匹配问题 2， 函数调用 3，递归调用 4， 表达式求值 5，八皇后问题

> **队列是先进先出，只能在表尾（队尾）插入（入队），在表头(队头)删除（出队）。通常用Queue来表示**

常见使用场景： 1，打印机打印排队 2，js里面的任务队列 其实涉及到先后顺序的很多都可以，排队上厕所，排队进地铁，都有着先进先出的特点。

栈和队列和普通线性表一样，可以使用顺序存储来表示也可以使用链式存储来表示。顺序栈，链栈/ 顺序队列，链队。 通常顺序栈【使用数组方式来表示】 和 循环队列【数组方式来表示，队尾指针到尽头之后移动到队头】更为常见。

在js里面，顺序栈，咱们可以用数组简单的模拟，`Array.protorype.push`作为入栈操作。`Array.protorype.pop`作为出栈操作。

#### \----Stack 案例 ####

1，将十进制数字转换为八进制

function getOctal(number) { 
            if (number === 0) return 0
            let stack = []
            let p = number
            while(p !== 0) { 
                let remain = p % 8
                stack.push(remain) // 入栈 
                p = Math.floor(p/8)
            }
            let res = ''
            while (stack.length != 0) { 
                res += stack.pop() // 出栈
            }
            return res
        }

2，括号的匹配校验，见[leetcode第20题][leetcode_20]

#### \----Queue案例 ####

二叉树的层次遍历（宽度优先遍历BFS），见[leetcode102题][leetcode102]

--------------------

> **栈和递归**

实际上函数嵌套调用和 递归函数都是通过栈来完成的。举一个例子：

function main() { 
            func1(1,2) // line 1
        }
        function func1(a, b) { 
            return func2(a, b, 1)
        }
        function func2(a, b, c) { 
            return a + b + c
        }
        main()

执行main函数，就会创建一个函数调用栈， func1 入栈，然后func2入栈，func2返回出栈，func1返回出栈，遵循先入后出，后入先出的原则。

递归函数是同理的，只不过是自己调用自己。

--------------------

> **一般性递归如果可以的话，可以往[尾递归][Link 1]方向优化，尾递归可以继续优化为循环。**

咱们以Fibonacci数列为例：

#### 一般性递归【函数调用栈空间呈指数级增长】 ####

重复运算，`f(5) = f(4) + f(3)，f(4) = f(3) + f(2)` 所以我们每一次存储前两个数字即可。

function fibonacci(n) { 
            if (n < 2) { 
                return n
            }
            return fibonacci(n - 1) + fibonacci(n - 2)
        }

#### 尾递归 ####

function fibonacci(n, ret1, ret2) { 
            if (n < 1) { 
                return 0
            }
            return fibonacci(n-1, ret1, ret1 + ret2)    
        }
        // ret1 ret2 初始值 为 0，1
        
        fibonacci(5, 0, 1)

#### 循环 ####

function fibonacci(n) { 
            if (n <= 2) return 1
            let n1 = 1, n2 = 2, sum = null
            for (let i = 0; i < n; i++) { 
                sum = n1 + n2
                n1 = n2
                n2 = sum
            }
            return sum
        }

资料：  
[尾调用维基百科][Link 1]  
[https://www.cnblogs.com/alantu2018/p/8465884.html][https_www.cnblogs.com_alantu2018_p_8465884.html]  
[ https://www.bilibili.com/video/av33876113][https_www.cnblogs.com_alantu2018_p_8465884.html]

[leetcode_20]: https://leetcode.com/problems/valid-parentheses/
[leetcode102]: https://leetcode.com/problems/binary-tree-level-order-traversal/
[Link 1]: https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8#%E4%BC%98%E5%8C%96%E5%B0%BE%E9%80%92%E5%BD%92%E7%9A%84%E5%88%86%E6%9E%90%E4%B8%8E%E7%A4%BA%E4%BE%8B
[https_www.cnblogs.com_alantu2018_p_8465884.html]: https://www.cnblogs.com/alantu2018/p/8465884.html