【数据结构与算法】前端JS实现栈

前言

Hello,大家好,这里是GIS宇宙,今天我们来聊一下栈。栈它是一种遵从后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。栈也被用在编程语言的编译器和内存中保存变量、方法调用等,也被用于浏览器历史记录(浏览器的返回按钮)。所以说学习算法的乐趣在哪?就是可以自己实现一些很骚的操作,而不是做一个调包侠(狗头)

创建栈

栈就像下面的书籍堆一样,你要想拿书得从堆的最后一本(栈顶)开始拿,你要想放一本书,也得放最后一本(栈顶)。因此栈越旧的元素越靠近栈底,越新的元素越靠近栈顶

栈的话,js是没有的,所以我们要基于上一篇文章介绍的数组,自己写一个属于自己的算法库,万事开头难,让我们先创建一个栈的类:

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

我们用数组来保存我们的元素,由于栈遵从LIFO原则,所以我们需要对数组进行约束来完成我们的栈类,它还应该有以下方法:

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

添加元素

push(element){
    this.items.push(element)
}

移除元素

栈删除元素都是删栈顶的元素,也就是数组最后一个元素,因此我们只需要用数组的pop方法,删除尾部元素即可:

pop(){
    return this.items.pop()
}

查看栈顶元素

如果我们想知道我们最后添加的元素是什么,只需要查看一下栈顶元素即可(数组最后一个元素)

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

检查栈是否为空

如果栈为空返回返回true,否则返回false,只需判断一下数组是否为空即可

isEmpty(){
    return this.items.length === 0
}

此外,我们还需要完成栈长度size的获取方法,类似数组的length

size(){
    return this.items.length;
}

清空栈元素

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

至此,栈的基本功能就完成了,我们来调用一下。

使用stack类

const stack = new Stack();
console.log(stack.isEmpty()); // 输出为true
stack.push(5)
stack.push(8)
console.log(stack.peak()) // 输出8
stack.push(11)
console.log(stack.size()) // 输出3
console.log(stack.isEmpty) // 输出false
stack.push(15)

下图描绘我们的操作:

然后我们调用两次pop方法,移除两个元素

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

栈改良

创建一个Stack类最简单的方式是使用一个数组来存储其元素。在处理大量数据的时候,我们需要评估如何操作数据是最高效的。在使用数组时,大部分方法的时间复杂度是 O(n)。O(n)的意思是,我们需要迭代整个数组直到找到要找的那个元素,在最坏的情况下需要迭代数组的所有位置,其中的 n 代表数组的长度。如果数组有更多元素的话,所需的时间会更长。另外,数组是元素的一个有序集合,为了保证元素排列有序,它会占用更多的内存空间,因此我们需要对我们的Stack类进一步改良,让其获取元素的时候占用更小,且按需排序。

class Stack{
    constructor(){
        this.count = 0;
        this.items = {};
    }
    // 方法
}

添加元素

push(elemengt){
    this.items[this.count] = element;
    this.count++;
}

在Js中,对象是一系列键值对的集合,采用键值对可以快速访问某一变量。我们使用count变量作键名,插入的元素作为它的值,然后递增count。

const stack = new Stack();
stack.push(5)
stack.push(8)
/////结果///////
items = { 
  0: 5, 
  1: 8 
}; 
count = 2;

验证是否为空

size(){
    return this.count;
}
isEmpty(){
    return this.count === 0
}

从栈中删除元素

由于我们没用数组存储元素,需要手动实现移除元素的逻辑。

pop(){
    if(this.isEmpty()){
        return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
}

首先,我们需要检查栈是否为空,如果为空返回undefined。如果栈不为空的话,则count-1,保存栈顶的值以便返回,并在对象中删除该元素。

查看栈顶值并清空栈

clear(){
    this.items = {};
    this.count =0;
}
// 也可用LIFO原则移除
while(!this.isEmpty()){
    this.pop();
}

toString方法

toString(){
    if(this.isEmpty()){
        return '';
    }
    let objString = `${this.item[0]}`;
    for (let i = 1;i<this.count;i++){
        objString = `${objString},${this.item[i]}`;
    }
    return objString;
}

如果栈是空的则返回空字符串,不为空则使用模板字符串合并多个值。

以上的方法除了toString,复杂度都为O(1)

保护内部元素

然而我们创建的数据结构还不完善,我们希望别人在使用的时候,只能用我们创建的方法来修改元素。试下执行下述代码:

const stack = new Stack(); 
console.log(Object.getOwnPropertyNames(stack)); // {1} 
console.log(Object.keys(stack)); // {2} 
console.log(stack.items); // {3}

行{1}和行{2}的输出结果是[“count”, “items”]。这表示count和items属性是公开的,我们可以像行{3}那样直接访问它们。根据这种行为,我们可以对这两个属性赋新的值,然而这不是我们希望看到的。

本章使用的语法是ES2015(ES6)创建了Stack类,ES6的类是基于原型,原型创建的类在内存空间和扩展方面由于函数创建的类,但这种方式不能声明私有属性(变量)或方法,下面介绍实现私有属性的方法。

下划线区分

部分JS库我们可以看到会有下划线来命名标记这个属性为私有,但是只是标记方便自己区分,没有真正实现私有

class Stack { 
  constructor() { 
    this._count = 0; 
    this._items = {}; 
  } 
}

ES2015限定作用于Symbol实现类

ES2015 新增了一种叫作Symbol的基本类型,它是不可变的,可以用作对象的属性。

const _items = Symbol('stackItems'); // {1} 
class Stack { 
  constructor () { 
    this[_items] = []; // {2} 
  } 
  // 栈的方法 
}

在上面的代码中,我们声明了Symbol类型的变量_items(行{1}),在类的constructor函数中初始化它的值(行{2})。要访问_items,只需要把所有的this.items都换成this[_items]。

这种方法创建了一个假的私有属性,因为ES2015新增的Object.getOwnProperty-Symbols方法能够取到类里面声明的所有Symbol属性,看下面这个例子:

const stack = new Stack(); 
stack.push(5); 
stack.push(8); 
let objectSymbols = Object.getOwnPropertySymbols(stack); 
console.log(objectSymbols.length); // 输出 1 
console.log(objectSymbols); // [Symbol()] 
console.log(objectSymbols[0]); // Symbol() 
stack[objectSymbols[0]].push(1); 
stack.print(); // 输出 5, 8, 1

可以看到我们通过获取到的Symbol,依旧可以修改元素,别急还有第三种方法。

ES2015的WeekMap实现类

这种方法可以确保属性是私有的,这就是WeekMap。Map数据结构后面会专门再写一篇,这里简单介绍一下,WeekMap可以存储键值对,键是对象,值可以是任意类型,来看看新版本:

const items = new WeakMap(); // {1} 
 
class Stack { 
  constructor () { 
    items.set(this, []); // {2} 
  } 
  push(element){ 
    const s = items.get(this); // {3} 
    s.push(element); 
  } 
  pop(){ 
    const s = items.get(this); 
    const r = s.pop(); 
    return r; 
  } 
  // 其他方法 
}

行{1},声明一个WeakMap类型的变量items。
行{2},在constructor中,以this(Stack类自己的引用)为键,把代表栈的数组存入items。
行{3},从WeakMap中取出值,即以this为键(行{2}设置的)从items中取值。 现在我们知道了,items在Stack类里是真正的私有属性。采用这种方法,代码的可读性不强,而且在扩展该类时无法继承私有属性。鱼和熊掌不可兼得!

其他提案

TypeScript 提供了一个给类属性和方法使用的private修饰符。然而,该修饰符只在编译时有用(包括我们在前几章讨论的 TypeScript 类型和错误检测)。

class Stack { 
   private items:number[] = [1,2,3]
}

事实上,我们不能像在其他编程语言中一样声明私有属性和方法。虽然有很多种方法都可以达到相同的效果,但无论是在语法还是性能层面,这些方法都有各自的优点和缺点。

应用

十进制转二进制

要把十进制转化成二进制,我们可以将该十进制数除以 2 并对商取整,直到结果是 0 为止。

function decimalToBinary(decNumber) { 
  const remStack = new Stack(); 
  let number = decNumber; 
  let rem; 
  let binaryString = ''; 
 
  while (number > 0) { // {1} 
    rem = Math.floor(number % 2); // {2} 余数
    remStack.push(rem); // {3} 
    number = Math.floor(number / 2); // {4} 商
  } 
 
  while (!remStack.isEmpty()) { // {5} 
    binaryString += remStack.pop().toString(); 
  } 
 
  return binaryString; 
}
console.log(decimalToBinary(233)); // 11101001 
console.log(decimalToBinary(10)); // 1010 
console.log(decimalToBinary(1000)); // 1111101000

在这段代码里,当除法的结果不为 0 时(行{1}),我们会获得一个余数,并放到栈里(行{2}、行{3})。然后让结果继续除以 2(行{4})。另外请注意:JavaScript 有数值类型,但是它不会区分整数和浮点数。因此,要使用Math.floor函数仅返回除法运算结果的整数部分。最后,用pop方法把栈中的元素都移除,把出栈的元素连接成字符串(行{5})。

进制转换算法

我们可以修改之前的算法,使之能把十进制转换成基数为 2~36 的任意进制。除了把十进制数除以 2 转成二进制数,还可以传入其他任意进制的基数为参数,就像下面的算法这样。

function baseConverter(decNumber, base) { 
  const remStack = new Stack(); 
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; // {6} 
  let number = decNumber; 
  let rem; 
  let baseString = ''; 
 
  if (!(base >= 2 && base <= 36)) { 
    return ''; 
  } 
 
  while (number > 0) { 
    rem = Math.floor(number % base); 
    remStack.push(rem); 
    number = Math.floor(number / base); 
  }
  while (!remStack.isEmpty()) { 
    baseString += digits[remStack.pop()]; // {7} 
  } 
 
  return baseString; 
}
console.log(baseConverter(100345, 2)); // 11000011111111001 
console.log(baseConverter(100345, 8)); // 303771 
console.log(baseConverter(100345, 16)); // 187F9 
console.log(baseConverter(100345, 35)); // 2BW0

我们只需要改变一个地方。在将十进制转成二进制时,余数是 0 或 1;在将十进制转成八进制时,余数是 0~7;但是将十进制转成十六进制时,余数是 0~9 加上 A、B、C、D、E 和 F(对应 10、11、12、13、14 和15)。因此,我们需要对栈中的数字做个转化才可以(行{6}和行{7})。因此,从十一进制开始,字母表中的每个字母将表示相应的基数。字母 A 代表基数 11,B 代表基数 12,以此类推。

小结

在本文中主要介绍了一下什么是栈,如何用JS写一个栈,并优化性能,从普通的数组到对象再到Map数据结构等,下一篇文章介绍队列,期待和你一起学习算法,上周偷懒了,所以这周会多更一篇文章。这里是GIS宇宙,带你了解代码的乐趣

参考文献:

Array – JavaScript | MDN (mozilla.org)

学习JavaScript数据结构与算法第三版 Learning JavaScript Data Structures and Algorithms 3rd Edition ([巴西]格罗纳(LoianeGroner), 孙晓博, 邓钢, 吴双, 陈迪, 袁源) (z-lib.org)

本人其他平台账号:

  • 微信公众号:GIS宇宙
  • CSDN:GIS_宇宙
  • 知乎:GIS宇宙
  • 掘金:GIS宇宙
© 版权声明
THE END
喜欢就支持一下吧
点赞9 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容