基本概念

栈（Stack）是一种后进先出的结构，LIFO（Last In First Out）
QQ截图20210222113313.png

实现栈方法

Stack class

  1. class Stack {
  2.   constructor() {
  3.     this.stack = []
  4.     this.top = 0
  5.   }
  6. }

push()

栈尾部推入一个元素，top指针自增

  1. push(element) {
  2.   this.stack.push(element);
  3.   this.top++;
  4. }

pop()

top指针自减，移除元素并返回移除元素

  1. pop() {
  2.   if (this.top !== 0) {
  3.     this.top--;
  4.     return this.stack.pop();
  5.   }
  6.   return 'Stack is empty';
  7. }

peek()

返回顶部元素的值

  1. peek() {
  2.   if (this.top !== 0) {
  3.     return this.stack[this.top - 1];
  4.   }
  5.   return null;
  6. }

size()

返回当前栈的大小

  1. size() {
  2.   return this.top;
  3. }

isEmpty()

返回当前栈是否为空

  1. isEmpty() {
  2.   return this.top === 0;
  3. }

clear()

清空栈

  1. clear() {
  2.   while (this.top > 0) {
  3.     this.pop();
  4.   }
  5. }

封装栈结构

  1. class Stack {
  2.   constructor() {
  3.     this.stack = []
  4.     this.top = 0
  5.   }
  7.   // Add element to the end of the stack
  8.   push(element) {
  9.     this.stack.push(element);
  10.     this.top++;
  11.   }
  13.   // Return and remove the last element of the stack
  14.   pop() {
  15.     if (this.top !== 0) {
  16.       this.top--;
  17.       return this.stack.pop();
  18.     }
  19.     return 'Stack is empty';
  20.   }
  22.   // Return the last element of the stack without removing 
  23.   peek() {
  24.     if (this.top !== 0) {
  25.       return this.stack[this.top - 1];
  26.     }
  27.     return null;
  28.   }
  30.   // Return true if stack is empty, flase otherwise
  31.   isEmpty() {
  32.     return this.top === 0;
  33.   }
  35.   // Return the number of elements in the stack
  36.   size() {
  37.     return this.top;
  38.   }
  40.   // Clear stack elements 
  41.   clear() {
  42.     // this.item = [];
  43.     while (this.top > 0) {
  44.       this.pop();
  45.     }
  46.   }
  47. }

场景应用

  • 十进制转二进制