数据结构中的栈和队列在算法中的应用

大家好，我是王大傻，最近也换了一家工作。文章的事儿也耽搁了不少时间，这就来补上。这次呢，主要想对算法与数据结构的关系着重讲一下自己的心得。

相关知识点

1. 栈
   1. 什么是栈
   2. 用JS怎么实现栈
   3. 栈对应的算法题目思考
      1. 每日温度
2. 队列
   1. 什么是队列
   2. 用JS实现队列
   3. 队列对应的算法题目思考
      1. 滑动窗口的最大值

话不多说，咱们开卷！

栈

什么是栈

什么是栈呢？让我们先来看一张关于栈结构的图片描述

那么如图所示，对于栈来说，它是一种遵循后进先出原则的有序集合，而添加新元素的一端成为栈顶，另一端则叫做栈底，当我们需要操作栈的元素时候，我们只能在栈顶对栈的数据进行操作（添加、移除或者取值），简而言之，栈就相当于我们生活中的储物箱，你可以向里面放置一些物品，但是当你想拿取时候，则必须从储物箱的顶端进行拿取，默认他也只有这一个出口。那么，在JS中我们如何去实现一个栈呢？带着疑问我们往下看。

用JS实现栈

• 思考
• 首先我们要设计一个栈的数据结构 他有哪些操作
  • 1 入栈操作
  • 2 出栈操作
  • 3 清空栈
  • 4 获取当前栈顶值

那么基于这些思考，我们用代码来实现下栈的数据结构。因为在JS中和栈结构类似的就是我们的数组，那么我们就用数组来模拟一下栈的结构。

class Stack {
  constructor () {
    // 存储栈的数据
    this.data = []
    // 记录栈的数据个数（相当于数组的 length）
    this.count = 0
  }
  // push() 入栈方法
  push (item) {
    // 方式1：数组方法 push 添加
    // this.data.push(item)
    // 方式2：利用数组长度
    // this.data[this.data.length] = item
    // 方式3：计数方式
    this.data[this.count] = item
    // 入栈后，count 自增
    this.count++
  }
  // pop() 出栈方法
  pop () {
    // 出栈的前提是栈中存在元素，应先行检测
    if (this.isEmpty()) {
      console.log('栈为空！')
      return
    }
    // 移除栈顶数据
    // 方式1：数组方法 pop 移除
    // return this.data.pop()
    // 方式2：计数方式
    const temp = this.data[this.count - 1]
    delete this.data[--this.count]
    return temp
  }
  // isEmpty() 检测栈是否为空
  isEmpty () {
    return this.count === 0
  }
  // top() 用于获取栈顶值
  top () {
    if (this.isEmpty()) {
      console.log('栈为空！')
      return
    }
    return this.data[this.count - 1]
  }
  // size() 获取元素个数
  size () {
    return this.count
  }
  // clear() 清空栈
  clear () {
    this.data = []
    this.count = 0
  }
}

const s = new Stack()
s.push('a')
s.push('b')
s.push('c')

console.log(s) // Stack {data: {…}, count: 3}
复制代码

这样以来，我们就用js模拟实现了栈的数据结构，那么根据上述我们大概可以了解到，首先，栈这个数据结构的出入口在一个地方，那么对于我们来说，如果我们需要储存一些排序数据或者说我们需要对一些数据结果做存储，那么栈也是不二的选择，因为他只有一个出入口，那么我们可以保证每次出的结果都是历史存储的信息，每次入栈操作，就相当于我们进行比较后对数据进行的一些处理，当然，对于排序的说法，就是单调栈，维护一个栈，栈中的数据具有单调递减或者单调递增或者以某种特定的方式进行排列，这样一来，如果情况允许，我们每次都只需要拿当前数据和栈顶元素进行一个相比较就可以清楚当前数据是否需要入栈。那么话不多说，接下来，我们来看道算法题。

每日温度

先来读题

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。题目链接

先来读题，根据题目我们先来复述下我们能掌握的信息，首先我们会得到一个数组，而且根据实例我们最后需要返回的结果也是一个数组。对于返回数据，题目给我们做了这些约束

1. 首先返回数据是一个天数的集合
2. 这个天数代表的就是我们得到数组中某一项值在其后续数组顺序中首次出现比当前值大的数值下标与当前下标的差值。如 [1,2,4,3,1,5] 对 下标为0的数值1 来说 第一次出现的最大值就是2 其下标为1 1-0=1 所以天数为1，但是对于下标为2的4来说，第一次出现比他大的值是5 5的下标为5 所以 天数为 5-2=3

理清了题意，让我们来实现一下吧

/**
 * @param {number[]} T 每日温度数组 [73, 74, 75, 71, 69, 72, 76, 73]
 * @return {number[]} 等待天数列表 [1, 1, 4, 2, 1, 1, 0, 0]
 */
var dailyTemperatures = function(T) {
  // 创建单调栈用于记录（存储索引值，用于记录天数）
  const stack = [0]
  let count = 1

  // 创建结果数组（默认将结果数组使用 0 填充）
  const len = T.length
  const arr = new Array(len).fill(0)

  // 遍历 T
  for (let i = 1; i < len; i++) {
    let temp = T[i]
    // 使用 temp 比较栈顶值，如果栈顶值小，出栈（计算日期差，并存储），并重复操作
    //  - stack[count - 1] 代表栈顶值
    while (count && temp > T[stack[count - 1]]) {
      // 出栈
      let index = stack.pop()
      count--
      // 计算 index 与 i 的差，作为 index 位置的升温日期的天数使用 
      arr[index] = i - index
    }
    // 处理完毕，当前温度入栈（等待找到后续的更大温度）
    stack.push(i)
    count++
  }
  return arr
}
复制代码

那么对于这道题来说，我是怎样想到用栈的方法呢，这点，我们就需要结合一下栈的概念了，首先，我们刚才讲的有单调栈这个用法，那么对于这道题而言，我们只需要找到比数组中每个数据大的第一个值的下标，换句话说，一旦我们找到了这个下标，那么我们这个数据是不是就可以不去做比较了，也就是只用一次，这样来说，我们就可以用单调栈的方法 每次都先去对栈顶的元素进行对比，然后向栈里面推进一个元素（这样做我们是相当于维护了一个单调递减的栈，这样只要当前元素比栈顶小，那么他一定没我们栈内元素的值大）由此可以通过不断地出栈对比操作返回我们的目标结果，当我们比较完，栈内还有剩余怎么办，我们再看一下题意，如果没有那就返回0，这也是我们为什么初始时候将结果数组以0做填充的原因。讲到这里，相信大家对栈也有一定的认知和理解。那么接下来让我们看看队列是怎么回事吧！

队列

队列的概念

什么是队列呢？同样我们也来看一个图

如图可以知道，我们队列是遵循先进先出的有序集合。添加新元素的一端是队尾，另一端则是队首。对于队列来说，我们生活中就相当于去购票排队，我们总是在队尾进行排队（不包含插队情况哈），然后在排到队首时候进去购买并且出队。那么，同样我们来用JS去简单实现一个队列。

JS实现队列

首先我们拿数组来进行模拟

class Queue {
  constructor () {
    // 用于存储队列数据
    this.queue = []
    this.count = 0
  }
  // 入队方法
  enQueue (item) {
    this.queue[this.count++] = item
  }
  // 出队方法
  deQueue () {
    if (this.isEmpty()) {
      return
    }
    // 删除 queue 的第一个元素
    // delete this.queue[0] 这样是没办法正常的进行出队 因为数组delete后还会保留当前空间 以empty填充
    // 利用 shift() 移除数组的第一个元素
    this.count--
    return this.queue.shift()
  }
  isEmpty () {
    return this.count === 0
  }
  // 获取队首元素值
  top () {
    if (this.isEmpty()) {
      return
    }
    return this.queue[0]
  }
  size () {
    return this.count
  }
  clear () {
    // this.queue = []
    this.length = 0
    this.count = 0
  }
}

const q = new Queue()
复制代码

当我们使用数组进行模拟时候，我们出队操作时如果用delete方法对数组中的数据进行移除，则会发现，数组中数据被移除了，但是还会剩余一个空间，以empty进行填充，那么显然是不符合队列的概念的。所以我们再试试用对象的方法来模拟一下队列。

class Queue {
  constructor () {
    this.queue = {}
    this.count = 0
    // 用于记录队首的键
    this.head = 0
  }
  // 入队方法
  enQueue (item) {
    this.queue[this.count++] = item
  }
  // 出队方法
  deQueue () {
    if (this.isEmpty()) {
      return
    }
    const headData = this.queue[this.head]
    delete this.queue[this.head]
    this.head++
    return headData
  }
  length () {
    return this.count - this.head
  }
  isEmpty () {
    return this.length() === 0
  }
  clear () {
    this.queue = {}
    this.count = 0
    this.head = 0
  }
}

const q = new Queue()
复制代码

那么，在这里我们就完成了队列的实现。问题来了，既然栈里面有单调栈的概念，那么队列呢？答案是有，队列有一种特殊的队列就是双端队列，双端队列就是我们可以在队尾队首随意插入取出值，但是我们不能在中间进行赋值，这一点呢，有点像我们生活中做的火车高铁一样，火车高铁的首尾都可以当作行进方向，但是我们不能说从中间开始跑（不加新火车头，不倒车），这一点也同样和我们数组比较类似，那么我们如何应用队列呢？让我们带着问题一起来看道算法题目吧！

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

首先还是根据题意分析了，读题我们可以获得信息是，我们接收的是一个数组 还有一个k值 我们需要返回的是滑动窗口中最大的值，而这个最大值和k有关，带着疑问我们先看下实例，在此我们发现，k相当于一个约束，就像我们做轮播图时候，设定当前视图中显示几个一样，其他的我们是看不到的，对于本题而言，在k里面我们每次都需要取得最大值并且放到我们的最终结果中进行维护。那么为什么相当队列呢，我们可以看看k值包括的内容，每次我们都会在队尾新增一个内容，在队首也相应出去一个值，并没有对中间值进行操作。因此，我们开始根据题意写代码.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
if(nums.length<=1){// 判断如果数组长度小于等于1 我们就直接返回这个数据就行
    return nums
}
 let result = [] // 结果数组
 let dequeue = [] // 队列
 let i = 0// 这里的i后续会用到 提取出来了
 for(;i<k;i++){// 首先是对 0-k个元素中最大值的提取
     while(dequeue.length&&nums[i]>dequeue[dequeue.length-1]){// 我们需要比较当前队列是否有值 并且 当前元素是否比队尾元素大 如果大的话 我们将队尾元素弹出 这样我们的队列始终是一个递减队列
         dequeue.pop()
     }
     dequeue.push(nums[i])
 }
 result.push(dequeue[0])// 因为上一步保证了我们队首是最大值 所以此时我们将结果存入结果数组

 for(;i<nums.length;i++){// 和上述一样 我们每次移动都将队尾元素进行更替
        while(dequeue.length&&nums[i]>dequeue[dequeue.length-1]){
         dequeue.pop()
     }
     dequeue.push(nums[i])
     if(dequeue[0] === nums[i-k]){// 这里我们需要考虑一个特殊情况 如 [1,3,-1,-3,2]
     /*
     [1,3,-1],-3,2  3
     1,[3,-1,-3],2  3
     1,3,[-1,-3,2]  2 
     i-k-1 i-k  i-k+1····· i-1 i
    此时由于我们遍历已经右移了一次 但是 我们栈中的元素 3 还是比当前最大值2 大 那么我们就需要进行比较
    i-k i为当前的窗口  那么 i-k 就是窗口左侧的元素 如果相等 就将我们队首元素弹出
      */
         dequeue.shift()
     }
     result.push(dequeue[0]) // 最后依然是放进我们队首元素
 }
 return result
};
复制代码

相信至此，聪明的你已经对队列以及栈有了一个初步的认识，那么相信经过不断的沉淀积累，也一定可以在我们的日常工作中大放光芒。期待屏幕前的你可以在实际应用后给个反馈。大傻在此感谢你的关注和点赞，有什么疑问也可以放在评论区，大家一起探讨下！