JavaScript —— 算法思想之栈数据结构

《工欲善其事，必先利其器》

大家好，我是 vk 。关于《算法》，我们前面两章分别学习了《指针思想》和《递归思想》，然后今天，我们就来学习一个新的处理复杂数据的编程方式 —— 《栈数据结构》。

一、如何理解栈？

数据结构栈，我们可以把其理解为一个羽毛球筒，它的进出口永远只有一个。然而，最先进去的羽毛球（工作栈），则是在最底下，也就是栈底。以此类推，最后一个进去的，永远都是在其他羽毛球的上面，也就是栈顶。

但是，如果你要拿一个羽毛球出来，你能拿到的，永远都是最上面那一个羽毛球，也就是栈顶的。以此类推，当羽毛球用完了剩下最后一个，它也就是最开始第一个进入羽毛球筒的。因此，这就是著名的后入先出原则，简称 LIFO。

我们看一张图片，可以很清晰的把上面的过程展示出来：

关于《执行上下文和临时性死区》的概念，大家有兴趣也可以去看一下我的另一篇文章。

二、算法应该怎么利用栈数据结构？

算法，肯定离不开计算和数据结构。我们通过一个例子切入，带大家应用栈数据结构：

• 试编写 “智能重复” smartRepeat 函数，实现：
• 将 3[abc] 字符串变为 abcabcabc；
• 将 3[2[a]2[b]] 字符串变为 aabbaabbaabb；
• 将 2[1[a]3[b]2[3[c]4[d]]] 字符串变为 abbbcccddddcccddddabbbcccddddcccdddd；
• 不用考虑输入字符串是否非法的情况。

因为前两天我们学习了指针和递归，所以给大家看一下我自己的分析过程：

• 首先，它是一个字符串，但是结果的结构变了，那么势必要用到指针的思想；
• 其次，字符串有配对，且，有嵌套的格式，那么相比递归，我会更加倾向与栈；
• 因为处理这种字符串模板编译的难题，栈往往都是要比递归来的更优一点的；
• 指针方面我选择用 while 而不是 for，因为 while 可以更加灵活的操控指针。

决定了算法的使用之后，就可以开始解题了：

let str = "2[1[a]3[b]2[3[c]4[d]]]";

function smartRepeat(templateStr) {
	// 指针
	let index = 0;
	// 栈1，存放临时字符串
	let charSections = [];
	// 栈2，存放字符串次数
	let timeSections = [];
	// 截取指针的剩余字符串
	let rest = templateStr;

	while(index < templateStr.length - 1) {
		// 截取剩余部分字符串
		rest = templateStr.substring(index);
		// 若当前字符是以数字和 [ 开头
		if (/^(\d+)\[/.test(rest)) {
			// 得到这个字符串次数
			let times = Number(rest.match(/^(\d+)\[/)[1]);
			// 字符串栈先填充字符串
			charSections.push("");
			// 字符串次数入栈
			timeSections.push(times);
			// 让指针后移，times这个数字是多少位就后移多少位加1([)位
			index += times.toString().length + 1;
		} else if (/^(\w+)\]/.test(rest)) {
			// 若当前字符是字母，那么此时就把字符串栈的栈顶这一项修改为当前字符
			// 获取这段字符并修改字符串栈
			let word = rest.match(/^(\w+)\]/)[1];
			charSections[charSections.length - 1] = word;
			// 让指针后移，word这个词是多少位就后移多少位
            index += word.length;
		} else if(rest[0] == "]") {
            // 若当前字符是 ]，那么字符串栈弹栈，字符串次数栈也弹栈
            let char = charSections.pop();
            let time = timeSections.pop();
            // 把字符串的新栈顶的元素重复刚刚弹出的哪个字符串指定次数拼接到新栈顶上
            charSections[charSections.length - 1] += char.repeat(time);
            // 指针自增，继续计算
            index++;
        }
	}
	// while 结束之后， 肯定还剩余一项，此时最后拼接一次，就会得到完整的字符串
    return charSections[0].repeat(timeSections[0]);
}

let resultStr = smartRepeat(str);
console.log(resultStr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

我们先看一下结果如何：

可见上图，结果与我们题目的要求符合。那么这道题，我们也就可以划上一个句号了。但是回过头来回想一下，如果我们使用递归或者其他算法呢？能否解答出来？

答案是肯定可以的。只不过没有栈这种数据结构来的方便，就目前来讲，可能使用栈数据结构来处理这道题，应该是效率最高的一种做法了。。。

三、总结

结合前几天学习的算法知识，我本人自己也在这里做一个小总结，希望大家如果有不同的看法也可以为我指出，大家一起进步：

1. 什么时候该应用指针思想？

不管是对象还是字符，只要我们有需要对每一个对象或字符进行判断和操作的这种需求，那么就势必需要应用指针。其核心是：遍历、判断；

2. 什么时候该用递归？

不管是对象还是字符，只要出现 规则复现 这种现象，那么优先考虑递归算法。其核心是：指针从左往右顺序不变，同时含有 规则复现 现象；

3. 什么时候该使用 栈数据结构？

同样，不管是对象还是字符，只要出现 规则复现 这种现象，且其指针顺序不是有序的，而是有可能从右往左，由内往外的时候，那么优先考虑使用 栈数据结构。

最后，感谢你的阅读，希望我的文章对你有所帮助。