堆栈

描述

栈是属于一种后进先出的结构(LIFO), 而定义栈的规则就是只能从顶部添加或者压入, 从顶部获取, 不能直接操作栈底的元素, 如下图, 依次添加 9 6 3 1
结构概念: 入栈, 出栈, 栈顶(最后一个添加入栈), 栈底(最先添加入栈), 映射到理解的数组中时, 栈顶就是数组的末尾, 栈底就是第一个
操作:

• push(入栈): 向栈中添加一个元素
• pop(出栈): 移除栈顶的元素, 并返回该元素
• peek(检查栈顶元素): 仅仅只是返回栈顶的元素, 并不会删除
• isEmpty(是否为空): 检查栈是否为空
• clear(清空): 清空栈

• size(长度): 查看栈的长度

  实现

  ```javascript // es5 function Stack() { const items = [];

  this.push = function(ele) { items.push(ele); };

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

  this.peek = function() { return items[items.size() - 1]; };

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

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

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

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

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

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

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

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

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

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

<a name="ecff77a8"></a>
### 使用
<a name="121068bd"></a>
#### [十进制](https://zh.wikipedia.org/wiki/%E5%8D%81%E8%BF%9B%E5%88%B6)转[二进制](https://zh.wikipedia.org/wiki/%E4%BA%8C%E8%BF%9B%E5%88%B6)
十进制: 以10 为基础进位的数字, 由0,1,2,3,4,5,6,7,8,9 十个数字组成<br />二进制: 以2 为基础进位, 主要是计算机使用, 由 0 和 1 组成
```javascript
function divideBy2(number) {
    let $$num = number; // 备份, 不修改原参数
  const remStack = new Stack();
  let binaryString = '';
  let rem; // 余数
  while(num > 0) {
      rem = $$num % 2;
    remStack.push(rem);
    $$num = Math.floor($$num / 2);
  }
  // 此处为什么不能使用数组的 reduce 以及区别
  while(!remStack.isEmpty()) {
      binaryString += remStack.pop(); // 出栈拼接
  }
     /**
  使用数组进行拼接, 时间貌似是短了点
  binaryString = remStack.getItems().reverse().reduce((prev, next) => {
    prev += next;
    return prev;
  }, '');
  */
  return binaryString;
}
// 测试
console.log(divideBy2(10)); // 1010
console.log(divideBy2(8)); // 1000

当然不使用栈结构处理也是可以实现的, 但是我们需要学习的是一种结构或者是思想

// 非栈结构实现, 在拼接时也可以使用数组本身的pop 方法获取类似栈顶的数字
function divideBy2(decNumber) {
  const arr = [];
  let $$num = decNumber;
  let rem;

  while ($$num > 0) {
    rem = $$num % 2;
    arr.push(rem);
    $$num = Math.floor($$num / 2);
  }

  return arr.reverse().reduce((prev, next) => {
    return prev.concat(next);
  }, '');
}

疑问

• 为什么在 ES5中的实现中, 使用的是 定义内部变量而不是使用 this.items = []; 呢 ?

解: 根据函数内是一个单独的作用域, 外部访问不到, 所以从外部是无法修改内部定义的变量. 而使用了 this.items = [] 之后 在实例的属性上就会带有 items, 此时假设使用 stack.items = []就能将内部的状态修改掉, 等于破坏了原本设定的结构

• 在转换时为什么需要 Math.floor ?

解: 以 2 为被除数时, 出现有浮点数, 后续无法再次操作, 二进制为 0, 1

• 为什么是余数入栈 ? 为什么是栈底的数字放在二进制的最后 ?

其他

函数调用栈

视频