手把手5分钟掌握JavaScript栈数据结构(一)【JavaScript数据结构与算法系列】_js栈的数据结构

一、JavaScript栈数据结构

JavaScript中本无“栈”的这种类型，但是我们有时候又需要用到这类的数据结构，还记得上一篇文章提到的数组吗？JavaScript中的栈数据结构就是基于Array类型来进行封装的。让我们拭目以待吧！

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

在现实生活中也能发现很多栈的例子。例如，一摞书或者餐厅里叠放的盘子。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录(浏览器的返回按钮）。

二、一个基于数组的栈

①创建一个基于数组的栈

我们将创建一个类来表示栈。简单地从创建一个stack-arrayjs文件并声明 stack 类开始。

class Stack {
	constructor(){
		this.items =[];	//{1}
	}
}
1
2
3
4
5

我们需要一种数据结构来保存栈里的元素。可以选择数组(行{1})。

数组允许我们在任何位置添加或删除元素。

由于栈遵循LIFO原则，需要对元素的插人和删除功能进行限制。

接下来，要为栈声明一些方法。

• push(element(s))：添加一个(或几个)新元素到栈顶。
• pop()：移除栈顶的元素，同时返回被移除的元素。
• peek()：返回栈顶的元素，不对栈做任何修改(该方法不会移除栈顶的元素，仅仅返回它)。
• isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
• clear()：移除栈里的所有元素。
• size()：返回栈里的元素个数。该方法和数组的length属性很类似。

②向栈添加元素

我们要实现的第一个方法是push。该方法负责往栈里添加新元素，有一点很重要：该方法只添加元素到栈顶，也就是栈的末尾。push方法可以如下这样写。

push(element){
	this.items.push(element);
}
1
2
3

因为我们使用了数组来保存栈里的元素，所以可以用上一章学到的数组的push方法来实现。

③从栈移除元素

接着，我们来实现pop方法。该方法主要用来移除栈里的元素。栈遵从LIFO原则，因此移出的是最后添加进去的元素。

因此，我们可以用上一章讲数组时介绍的pop方法。

栈的pop方法可以这样写：

pop(){
	this.items.pop();
}
1
2
3

只能用push和pop方法添加和删除栈中元素，这样一来，我们的栈自然就遵从了LIFO原则。

④查看栈顶元素

现在，为我们的类实现一些额外的辅助方法。

如果想知道栈里最后添加的元素是什么，可以用peek方法。

该方法将返回栈顶的元素。

peek(){
	return this.items[this.items.length -1];
}
1
2
3

因为类内部是用数组保存元素的，所以访问数组的最后一个元素可以用 length - 1。

在上图中，有一个包含三个元素的栈，因此内部数组的长度就是3。数组中最后一项的位置是2，而 length - 1 (3 - 1) 正好是2。

⑤检查栈是否为空

下一个要实现的方法是isEmpty，如果栈为空的话将返回true，否则就返回false。

isEmpty(){
	return this.items.length === 0;
}
1
2
3

使用isEmpty方法，我们能简单地判断内部数组的长度是否为0。

类似于数组的 length属性，我们也能实现栈的length。对于集合，最好用 size代替length。因为栈的内部使用数组保存元素，所以能简单地返回栈的长度。

size(){
	return this.items.length;
}
1
2
3

⑥清空栈元素

最后，我们来实现clear方法。clear方法用来移除栈里所有的元素，把栈清空。

实现该方法最简单的方式如下。

clear(){
	this.items = [];
}
1
2
3

也可以多次调用pop方法，把数组中的元素全部移除。

到这一步呢，就完成了！栈已经实现。

三、使用Stack类

在深入了解栈的应用前，我们先来学习如何使用stack类。首先需要初始化Stack类，然后验证一下栈是否为空(输出是true，因为还没有往栈里添加元素)。

const stack = new Stack();
console.log(stack.isEmpty());	//输出为true

1
2
3
4

接下来，往栈里添加一些元素（这里我们添加数字5和9，你可以添加任意类型的元素）。

stack.push(5);
stack.push(9);

1
2
3
4

如果调用peek方法，将输出9，因为它是往栈里添加的最后一个元素。

console.log(stack.peek());	//输出为9

1
2
3

再添加一个元素。

stack.push(12);
console.log(stack.size());	//输出为3
console.log(stack.isEmpty());	//输出为false

1
2
3
4
5

我们往栈里添加了12。如果调用size方法，输出为3，因为栈里有三个元素(5、9和12如果我们调用isEmpty方法，会看到输出了false(因为栈里有三个元素，不是空栈)。

最后，我们再添加一个元素。

stack.push(15)

1
2
3

下图描绘了目前为止我们对栈的操作，以及栈的当前状态。

然后，调用两次pop方法从栈里移除两个元素。

stack.pop();
stack.pop();
console.log(stack.size());	//输出为2

1
2
3
4
5

在两次调用pop方法前，我们的栈里有四个元素。调用两次后，现在栈里仅剩下5和9了下图描绘了这个执行过程。

四、本章小结

本系列文章主要讲述JavaScript栈数据结构（Stack）的类封装，但是本文作为栈类第一篇，主要是是先讲述基础，重点需要熟练掌握栈的基本结构及基础方法的使用，在后面的栈数据结构文章中才能一帆风顺。数据栈类的文章共三篇本文是第一篇。

工欲善其事，必先利其器。

五、写在后面

这作为一个JavaScript栈数据结构的第一篇文章，主要目的是让学习JavaScript栈数据结构的朋友可以快速掌握其基本结构和基础方法，本系列也会持续进行更新的。

有问题请留言或者@博主,谢谢支持o(￣︶￣)o~

感谢您的阅读,如果此文章或项目对您有帮助，若可以的话请给个一键三连吧！

GitHub有开源项目,需要的小伙伴可以顺手star一下！

GitHub: https://github.com/langyuxiansheng