当前位置 : 主页 > 编程语言 > 其它开发 >

栈(Stack)

来源:互联网 收集:自由互联 发布时间:2022-05-30
栈是一种遵从后进先出 LIFO(Last In First Out) 原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

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

生活中的案例
  • 堆成山的书

books

  • 堆成山的碗具

plates

这些案例中所有的特点都是添加的时候放在最顶端,移除的时候都是从顶端开始移除。

创建一个 Stack

接下来 我们用 JavaScript 这门语言来描述 这种数据解构。

class Stack {
  constructor() {
    this.items = {};
  }
}

我们使用了 JavaScript 的 对象 来 储存栈结构,接下来我们需要遵循(LIFO)原则,对元素的添加和删除做一些限制。

Stack 拥有的方法?
  • push(element):添加一个 或 几个新元素 到栈顶。
  • pop():移除栈顶的元素,并返回移除的元素。
  • peek(): 返回栈顶的元素,不做任何改变。
  • isEmpty():如果栈里没有任何元素就返回 true,反之返回false
  • clear():移除栈里所有的元素。
  • size(): 返回栈里的元素个数,和 数组的length属性相似。
  • toString(): 返回当前栈所有元素的内容。
class Stack {
  constructor() {
    this.items = {}; // 储存元素
    this.count = 0; // 记录栈元素的个数
  }
  // methods
  push(element) {
    this.items[this.count] = element;
    this.count++;
  }
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const current = this.items[this.count];
    delete this.items[this.count];
    return current;
  }
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  clear() {
    this.items = {};
    this.count = 0;
    // or
    // while (!this.isEmpty()) {
    //   this.pop()
    // }
  }

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

  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let str = `${this.items[0]}`;
    let index = 1;
    while (index < this.count) {
      str = `${str},${this.items[index]}`;
      index++;
    }
    return str;
  }
}
操作
const stack = new Stack();

stack.push(1); // 1
stack.push("a"); // 1,a
stack.peek(); // a
stack.pop(); // a
stack.toString(); // 1
问题

在 JavaScript 里,这个stack实例可以直接访问到items,count

const stack = new Stack();
stack.items = { 1: "a", 5: "c" };

我们希望保护内部的元素,只有我们暴露出的方法才能修改内部结构。不幸的是,我们在 Stack 类中声明的 items 和 count 属
性并没有得到保护,因为 JavaScript 的类就是这样工作的。

下划线命名约定

一部分开发者喜欢在 JavaScript 中使用下划线命名约定来标记一个属性为私有属性。

class Stack {
  constructor() {
    this._items = {};
    this._count = 0;
  }
}
用 ES2015 的限定作用域 Symbol 实现类
const _items = Symbol("stackItems");
class Stack {
  constructor() {
    this[_items] = {};
  }
}
  • 不过依然可以访问到这个属性
const _items = Symbol("stackItems");
class Stack {
  constructor() {
    this[_items] = {};
  }
}
const stack = new Stack();
const symbolKeys = Object.getOwnPropertySymbols(stack); // [Symbol(stackItems)]
stack[symbolKeys[0]] = { 1: "a", 4: "5" };
stack.toString(); // a,5
使用栈来解决的问题
  • JavaScript 执行栈

5 分钟理解 JS 调用栈

深入理解 JavaScript 中的执行堆栈

  • 十进制转换
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;
}

baseConverter(100, 8); // '144'
baseConverter(50, 2); // '110010'
上一篇:每日一题(2022-5-24):经典搜索算法
下一篇:没有了
网友评论