栈（Stack）

1. 栈结构

栈是一种运算受限的线性表,后进先出(LIFO)

• LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘, 往往先把拿出去使用.
• 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
• 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
• 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈

先进后出 (LIFO)

2. 程序中栈结构的应用

• 函数调用栈

  当我们写代码时候, 程序报错, 报错信息里面一般都会带有抱错代码的栈信息

3. 栈常见的操作方法或属性

• push(element): 添加一个新元素到栈顶位置.

• pop()：移除栈顶的元素，同时返回被移除的元素。

• clear()：移除栈里的所有元素。

• peek：返回栈顶的元素，不对栈做任何修改。

• isEmpty：如果栈里没有任何元素就返回true，否则返回false。

• size：返回栈里的元素个数。这个属性和数组的 length 属性很类似。

4. 栈结构的封装

基于数组的封装

封装示例

/* ***********封装********** */
class Stack {
  constructor(stack = []) {
    this.source = stack;
  }

  // 返回栈里的元素个数。这个属性和数组的 length 属性很类似
  get size() {
    return this.source.length;
  }

  // 如果栈里没有任何元素就返回true，否则返回false。
  get isEmpty() {
    return this.source.length <= 0;
  }

  // 返回栈顶的元素，不对栈做任何修改。
  get peek() {
    if (this.isEmpty) return null;
    return this.source[this.size - 1];
  }

  // 添加一个新元素到栈顶位置.
  push(ele) {
    this.source.push(ele);
  }

  // 移除栈顶的元素，同时返回被移除的元素。
  pop() {
    return this.source.pop();
  }

  // 移除栈里的所有元素
  clear() {
    this.source = [];
  }
}

使用示例

/* ********使用********** */

let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push("absdh");

console.log(stack);
console.log(stack.size);
console.log(stack.isEmpty);
console.log(stack.peek);
console.log(stack.pop());

5. 栈相关的题目

题一

有 6 个元素 6,5,4,3,2,1 他们可以任意按照从大到小的顺序入栈，请问下列哪个选项是不合法的？

A. 5,4,3,6,1,2

B. 4,5,3,2,1,6

C. 3,4,6,5,2,1 （×）

D. 2,3,4,1,5,6

分析： A 答案: 65 进栈, 5 出栈, 4 进栈出栈, 3 进栈出栈, 6 出栈, 21 进栈,1 出栈, 2 出栈 B 答案: 654 进栈, 4 出栈, 5 出栈, 3 进栈出栈, 2 进栈出栈, 1 进栈出栈, 6 出栈 D 答案: 65432 进栈, 2 出栈, 3 出栈, 4 出栈, 1 进栈出栈, 5 出栈, 6 出栈

题二

十进制转二进制, 将十进制的 1000 转成二进制

分析: 将十进制不断除与二进制,直到结果<=0 为止,并且按照先后顺序,将余数倒置得到最后的二进制,

function dec2bin(num) {
  let stack = new Stack();
  while (num > 0) {
    stack.push(num % 2);
    num = Math.floor(num / 2);
  }
  let bin = [];
  while (!stack.isEmpty) {
    let n = stack.pop();
    bin.push(n);
  }
  return bin.join("");
}

dec2bin(100); // 1111101000
dec2bin(100); // 1100100
// 验证
console.log((1000).toString(2)); // 1111101000
console.log((100).toString(2)); // 1111101000