Javascript数据结构之栈处理

作者: tww844475003 分类: 前端开发 发布时间: 2022-01-15 13:57

栈数据结构

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

栈在编辑语言的编译器和内存中保存变量、方法调用等,也被用于浏览器历史记录

基于数组的栈

  • push(element(s)):插入一个(或几个)新元素到栈项
  • pop():移除栈顶的元素,同时返回被移除的元素
  • peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶元素,仅仅返回它)
  • isEmpty():如果栈里没有任何元素就返回 true,否则返回 false
  • clear():移除栈里所有元素
  • size():返回栈里的元素个数,该方法和数组的 length 属性很类似
class Stack {
  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;
  }
  // 返回栈长度
  size() {
    return this.items.length;
  }
  // 清空栈元素
  clear() {
    this.items = [];
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8
stack.push(11);
console.log(stack.items); // [ 5, 8, 11 ]
console.log(stack.size()); // 3
stack.pop();
console.log(stack.items); // [ 5, 8 ]

基于对象的栈

  • push(element(s)):插入一个新元素到栈项
  • pop():移除栈顶的元素,同时返回被移除的元素
  • peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶元素,仅仅返回它)
  • isEmpty():如果栈里没有任何元素就返回 true,否则返回 false
  • clear():移除栈里所有元素
  • size():返回栈里的元素个数,该方法和数组的 length 属性很类似
  • toString():返回栈里所有元素
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;
  }
  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }
  // 检查栈是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 返回栈长度
  size() {
    return this.count;
  }
  // 清空栈元素
  clear() {
    this.count = 0;
    this.items = {};
  }
  // toString
  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;
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8
stack.push(11);
console.log(stack.toString()); // 5,8,11
console.log(stack.size()); // 3
stack.pop();
console.log(stack.toString()); // 5,8

保护数据结构内部元素

上面基于数组或对象的栈,我们希望保护内部元素,只有我们暴露出的方法才能修改内部结构。对于 Stack 类来说,要确保元素只会被添加到栈顶,而不是栈底或其他任意位置。不幸的是,在 Stack 类中声明的 items 和 count 属性并没有得到保护。

console.log(Object.getOwnPropertyNames(stack)) // [ 'count', 'items' ]
console.log(Object.keys(stack)) // [ 'count', 'items' ]
console.log(stack.items) // { '0': 5, '1': 8 }
  • 下划线命名约定
class Stack {
  constructor() {
    this._count = 0;
    this._items = {};
  }
}

下划线命名约定就是在属性名称之前加上一个下划线(_)。不过这种方式只是一种约定,并不能保护数据,而且只能依赖于使用我们代码的开发者具备的常识。

  • 用 ES2015 的限定作用域 Symbol 实现类

ES2015新增了一种叫作 Symbol 的基本类型,它是不可变的,可以用作对象的属性。看看怎么用它在 Stack 类中的声明 items 属性

const _items = Symbol('stackItems');
class Stack {
  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;
  }
  // 返回栈长度
  size() {
    return this[_items].length;
  }
  // 清空栈元素
  clear() {
    this[_items] = [];
  }
}

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

这种方法创建了一个假的私有属性,因为 ES2015 新增的 Object.getOwnPropertySymbols 方法能够取到类里声明的所有 Symbols 属性。上面的破坏 Stack 类的例子,可以看到访问 stack[objectSymbols[0]] 是可以得到 _items 的。_items 属性是一个数组,可以进行任意的数组操作。

  • 用 ES2015 的 WeakMap 实现类

WeakMap 数据类型可以确保属性是私有的,这种数据结构,只需要知道 WeakMap 可以存储键值对,其中键是对象,值可以是任意数据类型。

const items = new WeakMap();

class Stack {
  constructor() {
    items.set(this, [])
  }
  // 向栈插入元素
  push(element) {
    const s = items.get(this);
    s.push(element);
  }
  // 从栈弹出元素
  pop() {
    const s = items.get(this);
    const r = s.pop();
    return r;
  }
  // 查看栈顶元素
  peek() {
    const s = items.get(this);
    return s[s.length - 1];
  }
  // 检查栈是否为空
  isEmpty() {
    const s = items.get(this);
    return s.length === 0;
  }
  // 返回栈长度
  size() {
    const s = items.get(this);
    return s.length;
  }
  // 清空栈元素
  clear() {
    items.set(this, [])
  }
  getItems() {
    const s = items.get(this);
    return s;
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8
stack.push(11);
console.log(stack.getItems()); // [ 5, 8, 11 ]
console.log(stack.size()); // 3
stack.pop();
console.log(stack.getItems()); // [ 5, 8 ]
stack.clear()
console.log(stack.size()); // 0
  • ECMAScript 类属性提案

Typescript 提供了一个给类属性和方法使用的 private 修饰符。该修饰符只在编译时有用,在代码被编译完成后,属性同样是公开的

class Stack {
  #count = 0;
  #items = [];
}

栈的运用要

栈的实际运用非常广泛。在回溯问题中,它可以存储访问过的任务或路径、撤销的操作。也可以用它来解决一些计算机科学问题。任意进制转换的算法。判断回文数。

  • 十进制转二进制

十进制转化成二进制,我们可以将十进制数除以2并对商取整直到结果是0为止。把十进制数取余的数存入栈中,利用栈中后进先出的原则,依次弹出余数,即为该下进制数的二进制表示。

function decimalToBinary(decNumber) {
  const remStack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = '';
  while(number > 0) {
    rem = Math.floor(number % 2);
    remStack.push(rem);
    number = Math.floor(number / 2);
  }
  while(!remStack.isEmpty()) {
    binaryString += remStack.pop().toString();
  }
  return binaryString;
}
console.log(decimalToBinary(42)) // 101010
console.log(decimalToBinary(10)) // 1010
console.log(decimalToBinary(1000)) // 1111101000
  • 进制转换算法

在将十进制转成二进制时,余数是0或1;在将十进制转成8进制时,余数是0~7;将十进制转成16进制数据时,余数是1~9 、A 、B 、C 、D 、E ,从十一制开始,字母表中的每个字母将表示相应的基数。字母A代表基数11,B代表基数12。

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()];
  }
  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
  • 回文数

根据栈后进先出(LIFO)原则 ,该数据结构特点,组成字符器与原始值相等即为回文数。

function isPalindrome(value) {
  const stack2 = new Stack();
  for (let i = 0; i < value.length; i++) {
    stack2.push(value[i]);
  }
  let value2 = '';
  while(stack2.size() > 0) {
    value2 += stack2.pop();
  }
  if (value === value2) {
    return true;
  } else {
    return false;
  }
}
console.log(isPalindrome('10001')) // true
console.log(isPalindrome('level')) // true
console.log(isPalindrome('leveel')) // false
前端开发那点事
微信公众号搜索“前端开发那点事”

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表回复

您的电子邮箱地址不会被公开。