前言
栈作为一种数据结构,它可以应用在很多地方,当你需要经常获取刚存放进去的数据时,那么栈这种数据结构将是你的首选。
栈的实现方式一般有两种:数组实现和对象实现,这两种实现方式最终实现的功能都是一样的,但是在性能上却有着很大的差别。
本文将详细讲解这两种实现方式的差异并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文。
数组实现栈
本文讲解的是栈用代码的实现,如果对栈这种数据结构还不是很了解的话,可以移步我的另一篇文章:栈与队列
实现思路
栈的核心思想为后进先出(LIFO),那么我们可以用数组来描述栈。
接下来,我们来看下,一个栈都需要具备哪些功能:
入栈,添加一个新元素至栈顶(数组的末尾)。 出栈,将栈顶的元素移除并返回被移除的元素。 获取栈顶元素,获取当前栈顶元素返回。 判断栈是否为空,判断栈(数组)内是否有数据。 清空栈,移除栈内所有的元素。 获取栈大小,返回栈里的元素个数。 输出栈内数据,将栈中的所有元素以字符串的形式返回。
❝我们分析完栈都需要具备哪些功能后,发现数组中提供了很多现成的API可以实现上述功能,接下来,跟大家分享下上述功能的实现思路。
入栈(push),可以使用数组的push方法直接往数组的末尾添加元素。 出栈(pop),可以使用数组的pop方法直接移除栈中的元素,该方法会返回当前被移除的元素。 栈顶元素(peek),可以通过数组的长度-1获取到数组中的最后一个元素。 栈是否为空(isEmpty),可以通过判断数组的长度是否为0来实现。 清空栈(clear),可以将数组直接赋值为空或者调用出栈方法直至栈中的数据为空。 栈大小(size),可以返回数组的长度。 输出栈内数据,可以调用数组的toString方法将数组转换为字符串。
实现代码
有了实现思路后,我们就可以将上述实现思路转换为代码了。
新建一个Stack.ts文件 定义栈并规定其类型
private items: any[];
在构造器中初始化栈
constructor() {
this.items = [];
}
根据实现思路实现栈中的函数
// 入栈
push(item:any) {
this.items.push(item);
}
// 出栈
pop() {
return this.items.pop();
}
// 返回栈顶元素
peek() {
return this.items[this.items.length - 1];
}
// 判断栈是否为空
isEmpty() {
return this.items.length === 0;
}
// 清空栈栈内元素
clear() {
this.items = [];
}
// 获取栈内元素数量
size():number{
return this.items.length;
}
// 将栈内元素转为字符串
toString(){
return this.items.toString();
}
完整代码请移步:Stack.ts
编写测试代码
上述代码我们实现了一个栈,接下来我们往栈中添加几条数据,测试栈内的方法是否正确执行。
新建一个StackTest.js文件 实例化一个栈
const stack = new Stack();
测试栈内方法是否正确执行
// 入栈
stack.push("第一条数据");
stack.push("第二条数据");
// 出栈
stack.pop();
// 返回栈顶元素
console.log(stack.peek());
// 查看栈大小
console.log(stack.size());
// 判断栈是否为空
console.log(stack.isEmpty());
// 返回栈内所有元素
console.log(stack.toString())
// 清空栈
stack.clear()
完整代码请移步:StackTest.js
执行结果如下
对象实现栈
实现一个栈最简单的方式是通过数组存储每一个元素。在处理大量数据时,我们需要评估如何操作数据是最高效的。
在使用数组时,大部分方法的时间复杂度都为O(n),我们需要迭代整个数组直至找到目标元素,在最坏的情况下我们需要迭代数组的每一个位置。数组是元素的一个有序集合,为了保证元素排列有序,它会占用更多的内存空间。
如果我们可以直接获取元素,占用更少的内存空间,并且仍然保证所有元素都按照我们的需要进行排列,就属于最优解决方案了。
实现代码
我们可以使用一个对象来存储所有的栈元素,保证它们的顺序并且遵循LIFO原则。接下来我们来看看如何使用对象来实现栈。
新建一个ObjStack.ts文件 定义栈对象结构
interface StackObj {
[propName: number] : any;
}
定义栈并规定其类型,count用于记录栈的大小。
private items: StackObj;
private count: number;
在构造器中初始化栈相关变量
this.items = {};
this.count = 0;
入栈,当前栈的大小为新元素的key。
push(item: any) {
this.items[this.count] = item;
this.count++;
}
出栈,当前栈大小-1,取出栈顶元素,删除栈顶元素,返回取出的栈顶元素
pop() {
if(this.isEmpty()){
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
console.log(this.items);
return result;
}
返回栈顶元素,以当前栈大小-1为key获取其对应的value值。
peek() {
if(this.isEmpty()){
return undefined;
}
return this.items[this.count - 1];
}
判断栈是否为空,清空栈内元素,获取栈内元素数量
// 判断栈是否为空
isEmpty() {
return this.count === 0;
}
// 清空栈内元素
clear() {
this.items = [];
this.count = 0;
}
// 获取栈内元素数量
size():number{
return this.count;
}
将栈内元素转为字符串,遍历当前栈对象中的数据,将栈中的数据用逗号拼接并返回。
toString(){
if (this.isEmpty()){
return "";
}
let objString = `${this.items[0]}`;
for (let i = 1; i < this.count; i++){
objString = `${objString},${this.items[i]}`
}
return objString;
}
完整代码请移步:ObjStack.ts
编写测试代码
上述代码我们用对象实现了一个栈,接下来我们往栈中添加几条数据,测试栈内的方法是否正确执行。
新建一个StackObjTest.js文件 实例化一个栈
const stack = new ObjStack();
测试栈内方法是否正确执行
// 入栈
stack.push("第一条数据");
stack.push("第二条数据");
// 出栈
stack.pop();
// 返回栈顶元素
console.log(stack.peek());
// 查看栈大小
console.log(stack.size());
// 判断栈是否为空
console.log(stack.isEmpty());
// 返回栈内所有元素
console.log(stack.toString())
// 清空栈
stack.clear()
完整代码请移步:StackObjTest.js
执行结果如下
二者的区别
数组大部分方法的时间复杂度都为O(n),数组中的元素是一个有序集合,为了保证元素排列有序,它会占用更多的内存空间。
对象可以通过key直接访问到目标元素时间复杂度为O(1),我们可以直接目标元素进行操作,速度明显比数组快了很多倍。
接下来,我们通过一个实例来看看这两者在执行速度上的差异。
十进制转二进制
把十进制转为二进制,需要将该十进制除以2并对商取整,直到结果是0为止。
声明一个函数参数为一个十进制数
const decimalToBinaryStack = function (decNumber) {
}
函数内部声明一个变量,用于接收当前传进来的参数进行除法运算后得到的值。
// 传进来的十进制数
let number = decNumber;
函数内部实例化一个栈,用于保存模运算后得出的值。 函数内部声明两个变量,用户保存当前模运算的值和最终生成的二进制字符串
// 余数
let rem;
// 二进制结果
let binaryString = "";
while循环,判断当前参数进行除法运算后得到的值是否为0,如果不为0就对当前结果进行模运算,将模运算得到的值入栈,对当前结果进行除法运算,直至当前结果为0。
while (number > 0) {
// 模运算
rem = Math.floor(number % 2);
// 将余数入栈
stack.push(rem);
// 当前十进制结果除以二
number = Math.floor(number / 2);
}
while循环,将栈中的数据取出拼接到二进制结果字符串中去
while (!stack.isEmpty()) {
binaryString += stack.pop().toString();
}
返回二进制结果字符串
return binaryString;
完整代码请移步:Examples.js
❝实现代码如上所述,唯一不同的就是一个使用的是对象栈一个使用的数组栈,接下来我们来看下不同栈的运行时间差距。
写在最后
文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊 本文首发于掘金,未经许可禁止转载💌
评论区