栈

一、概念

数组和栈

1. 数组是一种线性结构，可以在 任意位置 插入和删除数据
2. 栈和队列 是 ==受限制的线性结构==

栈结构

1. 是一种受限的线性表，==先进后出== LIFO（last in first out）， 后进先出。
2. 仅允许在表的一端进行插入和删除，这一端成为==栈顶==。相对地，另一端为栈底。
3. 向一个栈插入新元素又称 ==进栈==、入栈或压栈)、出栈(退栈)
4. 向一个栈删除元素又称作 ==出栈==、退栈

程序中的栈实现

1. 函数调用栈
   1. A调用B，B中又调用了C，C中又调用D；
   2. 执行过程中，先将A压入栈，A没有执行完，不会退出栈
   3. 依次将B/C/D压入到栈中，D压入到栈顶。当前栈顺序是 栈底A->B->C->D栈顶
   4. D执行完，弹出栈。C/B/A 依次出栈
   5. 函数调用栈的称呼，就来自于其内部的实现机制（通过栈来实现的）。
2. 递归（容易引发栈溢出）

栈结构的实现

1. 基于数组实现
2. 基于链表实现（链表：也是一种数据结构，JavaScript中没有自带的链表结构）

二、属性和方法

栈的方法（6个）：

• push(element): 添加一个新元素到栈顶位置
• pop(): 移出栈顶位置，同时返回被移出的元素
• peek(): 返回栈顶的元素，不对栈做任何修改
• isEmpty(): 如果栈里没有任何元素就返回true，否则返回false
• size(): 返回栈元素的个数
• toString(): 将栈结构的内容以字符形式返回

具体代码实现

// 基于数组的实现
function Stack() {
  // 栈的属性
  this.items = [];

  // push(element): 添加一个新元素到栈顶位置
  Stack.prototype.push = function (element) {
    this.items.push(element);
  }

  // pop(): 移出栈顶位置，同时返回被移出的元素
  Stack.prototype.pop = function () {
    return this.items.pop();
  }

  // peek(): 返回栈顶的元素，不对栈做任何修改
  Stack.prototype.peek = function () {
    return this.items[this.items.length - 1];
  }

  // isEmpty(): 如果栈里没有任何元素就返回true，否则返回false
  Stack.prototype.isEmpty = function () {
    return this.items.length === 0;
  }

  // size(): 返回栈元素的个数
  Stack.prototype.size = function () {
    return this.items.length;
  }

  // toString(): 将栈结构的内容以字符形式返回
  Stack.prototype.toString = function () {
    return this.items.toString();
  }
}

// 栈的使用
const stack = new Stack();
stack.push(1)
stack.push(2)
stack.push(3)
stack.items = [1,2,3]
console.log(stack.items)
console.log(stack.peek())

三、算法实例

/***************  十进制转二进制 ***********/
// 方法：除以2，直到商为0，倒着取全部的余数

function dec2bin(decNumber) {
  // 1.定义栈对象，用于保存余数
  let stack = new Stack();

  // 2.循环取余数
  while(decNumber > 0) {
    // 2.1 获取余数，放入到栈中
    stack.push(decNumber % 2);

    // 2.2 获取整除后的结果，作为下一次循环的数字
    decNumber = Math.floor(decNumber / 2);

  }

  // 3.从栈中取出余数
  let binaryString = '';
  while(!stack.isEmpty()) {
    binaryString += stack.pop();
  }

  return binaryString;
}