JavaScript数据结构与算法之栈详解

目录

• 1.认识栈
• 2.面向过程方法源码编写栈
• 2.1思考
• 2.2需要实现的方法
• 2.3源码实现，并调用类
• 3.用面向对象的方法来源码书写
• 3.1思考
• 3.2需要实现的方法
• 3.3源码及使用类
• 4.总结

1.认识栈

栈：（stack）又名堆栈，它是一种运算受限的线性表。遵循后进先出（LIFO）

栈顶：限定仅在表尾进行插入和删除操作的线性表，

栈底：限定仅在表头进行插入和删除操作的线性表。

进栈：向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；

出栈：从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

2.面向过程方法源码编写栈

2.1思考

面向过程是什么：

面向过程就是将解决问题的步骤分析出来，

然后用函数实现，

只要一步一步的执行调用他就可以了。

2.2需要实现的方法

• push（element）添加一个或多个元素到栈顶
• pop（）删除钱顶的元素，并返回移除的元素
• peek（）返回栈顶的元素
• isEmpty（）用于判断栈是否为空，空则为空
• clear（）用于清空栈的元素
• size（）用于返回栈中元素的个数

在实现之前我们思考一下我们怎么实现

首先我们借用数组的方法来实现，所以我们需要创建

一个空数组来模拟栈

2.3源码实现，并调用类

构建一个类，用数组来模拟，

在类中书写各种方法

部分调用数组的方法。

总的来说就是用类来包装

数组的方法来实现栈的模拟

class Stack {
   constructor() {
       this.item = []
         }
   push(element) {
        this.item.push(element)
               }
   pop() {
      return this.item.pop()
          }
   peek() {
       return this.item[this.item.length - 1]
            }
   isEmpty() {
       return this.item.length === 0
            }
   clear() {
         this.item = []
   size() {
          return this.item.length
            }
        }
//实例化Stack类
const stack = new Stack()
stack.push(4)
stack.push(6)
console.log( stack.pop())
console.log(stack.peek())
console.log(stack.isEmpty())
console.log(stack.size())

运行结果：

3.用面向对象的方法来源码书写

3.1思考

面向对象：

就是将构建问题的事物，分解成若干个对象，

建立对象不是为了完成某个步骤，而是为了

描述某个事物在解决问题过程的行为

3.2需要实现的方法

• push（element）添加一个或多个元素到栈顶
• pop（）删除钱顶的元素，并返回移除的元素
• peek（）返回栈顶的元素
• isEmpty（）用于判断栈是否为空，空则为空
• clear（）用于清空栈的元素
• size（）用于返回栈中元素的个数
• toString()用于将栈以字符串的形式打印

那么在实现这个类，我们用对象来模拟栈

3.3源码及使用类

class Stack {
   constructor() {
      this.count=0
      this.items = {}
            }
   push(element) {
      this.items[this.count]=element
      this.count++
            }
    pop() {
       if(this.isEmpty()){
           return undefined
          }
       this.count--
       const result=this.items[this.count]
       delete this.items[this.count]
       return result
            }
    peek() {
          if(this.isEmpty()){
               return undefined
               }
         return this.items[this.count-1]
            }
    isEmpty() {
         return this.count===0
            }
    clear() {
        this.items={}
        this.count=0
          }
    size() {
       return this.count
           }
    toString(){
       if(this.isEmpty()){
        return undefined
               }
         let objectString=`${this.items[0]}`
          for(let i=1;i<this.count;i++){
               objectString=`${objectString},${this.items[i]}`
               }
         return objectString
            }
        }
 
  const stack = new Stack()
  stack.push(23)
  stack.push(34)
  stack.push(80)
  console.log( stack.pop())
  console.log(stack.peek())
  console.log(stack.isEmpty())
  console.log(stack.size())
  console.log(stack.toString())

在使用对象来模拟栈时，采用了键：值的方式 

来存储数据，比如this.items[this.count]=element

在这个结构中用this.count来记录栈的大小，

当我们向里面插入一个数字时，就分配count为键

插入的值为值。这个时候就需要将this.count++.

关于pop（）与peek（），toString()方法都需要

先判断栈是否为空，如果为空则返回undefined。

4.总结

• 了解了面向对象与面向过程
• 掌握了两种方式用什么来模拟栈
• 对栈模拟进行源码设计