Javascript数据结构与算法（三）栈

kohoh_ 发布于2019-08-26 14:01 / 1324人阅读

摘要：保护数据结构内部元素下划线命名约定这只是一种约定，只能依赖于开发人员具备的常识用的限定作用于实现类实现了假的私有属性，虽然基本类型不可变，但由于新增的方法仍然能取到所有属性，而且是数组的形式，但我们操作的是栈，不应该出现这种行为。

栈是一种遵循后进先出（ILFO）原则的有序集合，新添加或待删除的元素都保存在栈的同一段，称为栈顶，另一端就叫栈底。现实中很多例子采用了这种数据结构，比如一摞书，叠放的盘子。栈通常用来保存变量、方法调用，当然也可以用于浏览器历史记录。

基于数组的栈 创建类

class StackArray {
  constructor() {
    this.items = [];
  }

向栈顶添加元素

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

从栈顶移除元素

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

查看栈顶元素

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

检查栈是否为空

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

清空栈元素

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

转化为数组

toArray() {
    return this.items;
  }

转化为字符串

toString() {
    return this.items.toString();
  }

基于Javascript对象的stack类 创建stack类

class Stack {
  constructor() {
    this.count = 0;//记录栈的大小，帮助我们进行添加和删除操作
    this.items = {};
  }

添加元素

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

删除元素

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

验证一个栈是否为空和它的大小

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

  size() {
    return this.count;
  }

查看栈顶的值并将栈清空

peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  };
clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    this.items = {};
    this.count = 0;
  };

转为字符串

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;
  }
}

总结

除了toString方法，我们创建的其他方法的时间复杂度均是O(1),代表我们可以直接扎到目标元素并对其进行操作。

注意

目前为止我们使用的是ES6语法类，由于JavaScript语言的特点，类并不能跟其他语言一样具有私有属性，也就是在外部可以引用私有属性，对其进行赋值等操作。看以下的代码了解一下：

const stack = new Stack();
console.log(Object.getOwnPropertyNames(stack));//["count","items"]
console.log(Object.keys(stack));//["count","items"]
console.log(stack.items);//直接访问私有属性

那么问题来了，我们只想让用户使用我们暴露出来的属性或者方法，我们该怎么实现私有属性呢。笔者看了前辈总结的，直接把它写上来。

保护数据结构内部元素 下划线命名约定

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

这只是一种约定，只能依赖于开发人员具备的常识

用E2015的限定作用于Symbol实现类

const _items = Symbol("stackItems");
class Stack{
    constructor(){
        this[_items] = [];
    }
};

实现了假的私有属性，虽然Symbol基本类型不可变，但由于ES2015新增的Object.getOwnPropertySymbols方法仍然能取到所有Symbol属性，而且是数组的形式，但我们操作的是栈，不应该出现这种行为。别急，还有第三个方案

用ES2015的WeakMap实现类

const items = new WeakMap();
class Stack{
    constructor(){
        items.set(this,[]);
    },
    push(element){
        const s = items.get(this);
        s.push(element);
    }
}

这样我们就实现了一个实现了一个完全的私有属性，但是代码可读性对于笔者真的太难受了，不知道你们怎么觉得呢。

栈的实践 进制转换算法

function baseConverter(decNumber, base) {
  const remStack = new Stack();
  const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  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()];
  }

平衡圆括号算法

function parenthesesChecker(symbols) {
  
const stack = new Stack();
  const opens = "([{";
  const closers = ")]}";
  let balanced = true;
  let index = 0;
  let symbol;
  let top;

  while (index < symbols.length && balanced) {
    symbol = symbols[index];
    if (opens.indexOf(symbol) >= 0) {
      stack.push(symbol);
    } else if (stack.isEmpty()) {
      balanced = false;
    } else {
      top = stack.pop();
      if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
        balanced = false;
      }
    }
    index++;
  }
  return balanced && stack.isEmpty();
}

云服务器 GPU云服务器 javascript全栈视频 javascript全栈教程 javascript全栈开发 javascript快速全栈开发

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/109973.html

学习JavaScript数据结构与算法（一）：栈与队列

摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

Flink_China 2019-08-19 17:23 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

Jonathan Shieber 2019-08-29 12:33 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

SHERlocked93 2019-08-22 11:04 评论0 收藏0
JavaScript 数据结构与算法之美 - 栈内存与堆内存、浅拷贝与深拷贝

摘要：栈内存与堆内存浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。栈内存与堆内存中的变量分为基本类型和引用类型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言想写好前端，先练好内功。栈内存与堆内存、浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。笔者写的 JavaScrip...

dailybird 2019-08-23 18:26 评论0 收藏0
[ JavaScript ] 数据结构与算法 —— 栈

摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。前言 JavaScript是当下最流行的编程语言之一，它可以做很多事情：数据可视化（D3.js，Three.js，Chart.js）; 移动端应用(React Native,Weex,AppCan,Fl...

everfight 2019-08-26 13:31 评论0 收藏0