3.JavaScript 数据结构与算法（三）栈

[webVueBlog]

什么是栈

• LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。

栈的特点：先进后出，后进先出。

程序中的栈结构

• 函数调用栈：A(B(C(D())))：
  即 A 函数中调用 B，B 调用 C，C 调用 D；在 A 执行的过程中会将 A 压入栈，随后 B 执行时 B 也被压入栈，函数 C 和 D 执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数 D 执行完之后，会弹出栈被释放，弹出栈的顺序为 D->C->B->A;

• 递归：
  为什么没有停止条件的递归会造成栈溢出？比如函数 A 为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数 A 压入栈，最后造成栈溢出（Queue Overfloat）。

栈结构实现

栈常见的操作

• push() 添加一个新元素到栈顶位置。
• pop() 移除栈顶的元素，同时返回被移除的元素。
• peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。
• isEmpty() 如果栈里没有任何元素就返回 true，否则返回 false。
• size() 返回栈里的元素个数。这个方法和数组的 length 属性类似。
• toString() 将栈结构的内容以字符串的形式返回。

function dec2bin(dec) {
 // new 一个 Stack，保存余数
 const stack = new Stack()
 // 当不确定循环次数时，使用while
 while (dec > 0) {
  stack.push(dec % 2)
  dec = Math.floor(dec/2)
 }
 let binaryStriing = '';
 while(!stack.isEmpty()) {
  binaryString += stack.pop();
 }
 return binaryString
}

JavaScript 代码实现栈结构

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

 // push(item) 压栈操作，往栈里面添加元素
 push(item) {
  this.items.push(item);
 } 
 
 // 出栈
 pop() {
  return this.items.pop();
 }

 peek() {
  return this.items[this.items.length - 1]
 }
 
 isEmpty() {
  return this.items.length === 0
 }
 
 size() {
  return this.items.length
 }

 // toString() 返回以字符串形式的栈内元素数据
 toString() {
  let result = ''
  for (let item of this.items) {
   result += item + ' '
  }
  return result
 }
}