【数据结构与算法】前端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)

本人其他平台账号：