1. 栈是一种遵从 先进后出 原则的有序集合
    1. 栈顶：相当于数组的尾部
    2. 栈底：相当于数组的起始
    3. 入栈：相当于向数组末尾添加元素
    4. 出栈：相当于向数组末尾删除元素
  2. 栈的作用
    1. js 执行栈
    2. 变量的存储 - js中，变量存在栈结构中，复杂类型存在堆结构里面

数组模拟栈结构

  1. /**
  2.  * 1.push 在栈顶添加元素
  3.  * 2.pop 删除栈顶元素并返回
  4.  * 3.peek 获取栈顶元素
  5.  * 4.isEmpty 判断栈是否为空
  6.  * 5.clear 清空栈结构
  7.  * 6.size 返回栈元素数量
  8.  */
  9. class Stack {
  10.   constructor() {
  11.     this.items = [];
  12.   }
  13.   push(element) {
  14.     this.items.push(element);
  15.   }
  16.   pop() {
  17.     return this.items.pop();
  18.   }
  19.   peek() {
  20.     return this.items[this.items.length - 1];
  21.   }
  22.   isEmpty() {
  23.     return this.items.length === 0;
  24.   }
  25.   clear() {
  26.     this.items = [];
  27.   }
  28.   size() {
  29.     return this.items.length;
  30.   }
  31. }

对象模拟栈结构

  1. /**
  2.  * 需要使用一个变量表示栈元素的索引
  3.  * 1.push 添加栈顶元素
  4.  * 2.pop 删除栈顶元素并返回
  5.  * 3.peek 返回栈顶元素
  6.  * 4.isEmpty 判断是否为空
  7.  * 5.size 判断栈元素数量
  8.  * 6.clear 清空栈
  9.  */
  10. class Stack {
  11.   constructor() {
  12.     // count可以表示栈元素的数量
  13.     this.count = 0;
  14.     this.items = {};
  15.   }
  16.   push(element) {
  17.     this.items[this.count] = element;
  18.     this.count++;
  19.   }
  20.   pop() {
  21.     this.count--;
  22.     let res = this.items[this.count];
  23.     delete this.items[this.count];
  24.     return res;
  25.   }
  26.   peek() {
  27.     return this.items[this.count - 1];
  28.   }
  29.   isEmpty() {
  30.     return this.count === 0;
  31.   }
  32.   size() {
  33.     return this.count;
  34.   }
  35.   clear() {
  36.     this.count = 0;
  37.     this.items = {};
  38.   }
  39. }
  41. const stack = new Stack();
  42. stack.push(1);
  43. stack.push(2);
  44. stack.push(3);
  45. console.log(stack);
  46. stack.pop();
  47. console.log(stack);
  48. console.log(stack.isEmpty());
  49. console.log(stack.size());
  50. stack.clear();
  51. console.log(stack);

Snipaste_2022-05-08_13-15-18.png

栈解决进制转换问题

  1. function hexOct(number) {
  2.   const stack = new Stack();
  3.   // 余数
  4.   let rem;
  5.   let comNumber = number;
  6.   // 输出结果
  7.   let res = '';
  8.   // 将每个输出的结果压入栈中，最小位在栈底，最大位在栈顶
  9.   while (comNumber > 0) {
  10.     rem = comNumber % 2;
  11.     stack.push(rem);
  12.     comNumber = Math.floor(comNumber / 2);
  13.   }
  14.   // 将每一位取出，从栈顶开始，依次拼接字符串
  15.   while (!stack.isEmpty()) {
  16.     res += stack.pop();
  17.   }
  18.   return res;
  19. }