之前我写过一篇链表，当时是打算写一个系列的，但是后面没写一直让我内心不太舒服，主要是因为我觉得这些数据结构都比较简单，可能写了也没啥用～但最近我了解到还是很多前端人对于算法不了解，所以还是打算将这个系列写下去～

一、什么是栈？

对于这个问题，我想请你看一个《罗小黑战记》中羽毛球的名场面👇
May-20-2022 14-52-59.gif
上图中，这个容器就是栈（stack），而每一个羽毛球，就是一个存储单元，对于第一个进入的元素（也就是那个最酸爽的羽毛球🤣 ）我们称之为栈底元素，而最后进入栈中的就是栈顶元素了。
栈的存取规则就跟这个羽毛球筒一样，最先进入的，只能最后出来，也就是 first-in, last-out，并且只能观测到栈顶元素。
可能会有小可爱会说：前端里面没有栈呀！
image.png
的确，前端里面确实没有栈的概念，但我认为数据结构是不分语言的，这是一种思想，语言是死的，但思想是活的，学一样，可以通多样。
JavaScript 里面只有数组，没有栈，但它如果我们只用array.push()和array.pop()的话也是可以做为栈的，但这并不明确，万一被不知道此处代码逻辑的其他同事修改了逻辑，还是很麻烦的。最重要的是，刷题一定会用，面试可能会考。我一直认为懂数据结构与算法的程序员的眼界会更广阔，路走的更长远。
image.png
总结一下栈的操作规则：

  1. 查找：只能观测到栈顶元素。
  2. 入栈：元素入栈只能处于栈顶位置（最后一位）
  3. 出栈：元素出栈只能弹出栈顶元素（最后一位）

二、栈的实现

已知了栈的操作逻辑，接下来我们来实现一下栈。
这里我会使用两种基本的数据结构（数组和双向链表）的方式来实现栈的数据结构。

2.1 封装数组成栈

我们将数组封装一下，变成最基本的栈。

  1. class Stack<T> {
  2.     private data: T[] = [] // 定义一个仅内部访问的空数组
  4.   // 访问栈顶元素
  5.   peek(): T {
  6.         return this.data[this.size - 1]
  7.     }
  8.   // 添加元素到栈顶
  9.     push(value: T) {
  10.         this.data.push(value)
  11.     }
  12.   // 弹出栈顶元素
  13.     pop(): T {
  14.         return this.data.pop()
  15.     }
  16.   // 判断栈是否为空
  17.     empty() {
  18.         return this.data.length === 0
  19.     }
  20.   // 获取栈已有元素个数
  21.     get size() {
  22.         return this.data.length
  23.     }
  24. }

上面这种是最简单的栈的实现，代码很好读懂，我就不做过多解释了。下面我们来使用一下

// 这里的 <number> 就对应了定义 Stack<T> 中的 T，表示我接下来要放入栈中的元素是number类型
const stack = new Stack<number>() 
if (stack.empty()) {
  console.log('当前栈空空如也～')
}
stack.push(1)
stack.push(2)
if (stack.peek() === 2) {
  console.log('探查到栈顶元素是数字 2 没错啦～')
}
console.log('弹出的栈顶元素是:', stack.pop())

2.2 以链表为基础封装一个栈

以数组的方式形成一个栈总会让我觉得怪怪的，它明明是个数组，却只能干着栈的活儿（不是。
image.png
我个人认为数组作为栈是一种浪费，它创建时JS底层必然会给它附加上各种API，但是对于形成的栈而言，这些API不能被使用，着实是一种浪费，我们以链表的结构来封装一个栈。
先实现一个链表如下

class ListNode<T> {
    val: T
    next: ListNode<T> | null
    constructor(val: T, next?: ListNode<T> | null) {
        this.val = val
        this.next = next || null
    }
}

利用链表来实现栈

class Stack<T> {
    private list: ListNode<T> | null
    private top: ListNode<T> |null
    constructor() {
        this.list = null
    }
    push(val: T) {
        const node = new ListNode<T>(val) // 将元素构建成一个链表节点
        if (this.empty()) {
            // 栈为空时入栈直接将元素节点作为链表头元素（作为栈底元素存在）
            this.list = node
        } else {
            // 栈不为空时入栈，将元素添加到链表尾部（栈顶）
            this.top.next = node
        }
        // 更新最后一位
        this.top = node
    }
    pop(): T {
        // 栈内只有一个元素
        if (this.list === this.top) {
            const ans = this.list.val
            this.list = null
            this.top = null
            return ans
        }

        let temp = this.list
        while (temp.next !== this.top) {
            temp = temp.next
        }
        // 一直循环到找到最后一个元素为止
        const ans = temp.next.val
        // 将其断开链接
        temp.next = null
        this.top = temp
        return ans // 返回结果
    }
    peek(): T {
        return this.top ? this.top.val : null
    }
    empty() {
        return this.list === null
    }
}

这是我的第一想法，这种实现有很明显缺陷，就是在弹出操作时存在着O(n)级别的复杂度。

2.3 优化以链表构建的栈

我们来优化一下实现，这里有两个思路：

  1. 双向链表，这样我们就能在弹出操作时能轻易的找到栈顶之前的一位元素，从而将其作为新的栈顶元素

  2. 仍使用单链表，但将思路反转，以新入栈的元素作为链表头，这样就只需要维护这个链表头作为栈顶元素即可

    OK，这里我只做第二种方式来优化来，就不展示双向链表的实现了，有兴趣可以自己去实现，或实在有问题，可以给我留言。

    class Stack<T> {
 private list: ListNode<T> | null
 constructor() {
     this.list = null
 }
 push(val: T) {
     if (this.empty()) {
         // 当栈为空，直接将链表节点作为栈底（和栈顶元素存在）
         this.list = new ListNode(val)
     } else {
         // 当栈不为空，则将原栈中的列表作为栈下元素，新来的作为栈顶元素（链表头）
         this.list = new ListNode(val, this.list)
     }
 }
 pop(): T {
     if (this.empty()) return
     // 保存栈顶的值（链表头的值）
     const value = this.list.val
     // 将栈顶元素移除（移除链表头，将next作为新的链表头）
     this.list = this.list.next
     // 返回值
     return value
 }
 peek(): T {
     if (this.empty()) return
     return this.list.val
 }
 empty() {
     return this.list === null
 }
}

    我们可以很清晰的感受到这种实现方式的妙处了，仅仅只需要维护一个链表头，就可以轻松实现一个栈
    image.png

三、解题

我们已经理解了栈，接着我们尝试使用我们自己实现的栈来解决leetcode中的问题来加深对栈的理解
leetcode 20. 有效的括号
这题使用栈的思想来做（即便你用其他数据结构也可以使用栈思想，如数组），通过访问栈顶元素是否是来的元素的另一半（今天520，括号都有另一半，你呢？😅 😅 😅 ）来决定是否将其出栈，最后判断是否栈是否为空判断是否为有效括号即可（所有括号都找到了另一半🤪 🤪 🤪 ）


function isValid(s: string): boolean {
  const stack = new Stack<string>()
  for (let i = 0; i < s.length; i++) {
    // 判断观测元素是否是闭合的右括号，如果是闭合的右括号则看栈顶是否是对应的左括号
    if (
      s[i] === ')' && stack.peek() === '('
      || s[i] === ']' && stack.peek() === '['
      || s[i] === '}' && stack.peek() === '{'
    ) {
      // 如果是，则将对应的左括号从栈顶弹出
      stack.pop()
    } else {
      // 否则将其入栈
      stack.push(s[i])
    }
  }
  // 最后判断栈是否为空即可
  return stack.empty()
};

class Stack<T> {
    private list: MyListNode<T> | null
    constructor() {
        this.list = null
    }
    push(val: T) {
        if (this.empty()) {
            // 当栈为空，直接将链表节点作为栈底（和栈顶元素存在）
            this.list = new MyListNode(val)
        } else {
            // 当栈不为空，则将原栈中的列表作为栈下元素，新来的作为栈顶元素（链表头）
            this.list = new MyListNode(val, this.list)
        }
    }
    pop(): T {
        if (this.empty()) return
        // 保存栈顶的值（链表头的值）
        const value = this.list.val
        // 将栈顶元素移除（移除链表头，将next作为新的链表头）
        this.list = this.list.next
        // 返回值
        return value
    }
    peek(): T {
        if (this.empty()) return
        return this.list.val
    }
    empty() {
        return this.list === null
    }
}

// 之所以使用自己定义的链表是因为 leetcode 中链表元素是固定的 number 类型
class MyListNode<T> {
    val: T
    next: MyListNode<T> | null
    constructor(val: T, next?: MyListNode<T> | null) {
        this.val = val
        this.next = next || null
    }
}

希望看到这里的你能给我点个赞👍 谢谢您
image.png