跟着卡哥学算法Day 10：栈与队列理论 & 常见题目

JavaScript 没有独立的数据结构，但可通过数组模拟，或自行封装类。

栈 LIFO#

后进先出：最后添加的元素最先被移除

操作#

push：元素入栈（添加到栈顶）
pop：元素出栈（移除栈顶元素）
peek：查看栈顶元素（不移除）

实现方式#

使用数组实现

1
const stack = []
2
stack.push(1) // 入栈 [1]
3
stack.push(2) // 入栈 [1, 2]
4
const top = stack.pop() // 出栈 2，栈变为 [1]

定义 Stack 类

1
class Stack {
2
  constructor() {
3
    this.items = []
4
  }
5
  push(item) {
6
    this.items.push(item)
7
  }
8
  pop() {
9
    return this.items.pop()
10
  }
11
  peek() {
12
    return this.items[this.items.length - 1]
13
  }
14
  isEmpty() {
15
    return this.items.length === 0
16
  }
17
}
18

19
const s = new Stack()
20
s.push(10)
21
s.push(20)
22
s.pop() // 返回 20

队列 FIFO#

先进先出：最先添加的元素最先被移除

操作#

enqueue：元素入队（添加到队尾）
dequeue：元素出队（移除队首元素）
front：查看队首元素（不移除）

实现方式#

使用数组实现

1
const queue = []
2
queue.push(1) // 入队 [1]
3
queue.push(2) // 入队 [1, 2]
4
const front = queue.shift() // 出队 1，队列变为 [2]

性能较差，因为shift()操作会导致所有元素前移，时间复杂度是 O(n)，频繁操作可能影响性能

定义 Queue 类

1
class Queue {
2
  constructor() {
3
    this.items = {}
4
    this.frontIndex = 0 // 队首指针
5
    this.rearIndex = 0 // 队尾指针
6
  }
7
  enqueue(item) {
8
    this.items[this.rearIndex] = item
9
    this.rearIndex++
10
  }
11
  dequeue() {
12
    if (this.isEmpty()) return null
13
    const item = this.items[this.frontIndex]
14
    delete this.items[this.frontIndex]
15
    this.frontIndex++
16
    return item
17
  }
18
  front() {
19
    return this.items[this.frontIndex]
20
  }
21
  isEmpty() {
22
    return this.rearIndex === this.frontIndex
23
  }
24
}
25

26
const q = new Queue()
27
q.enqueue(10)
28
q.enqueue(20)
29
q.dequeue() // 返回 10

通过指针追踪队首和队尾，性能更优

接下来都通过 🌟 来代表题目难度：

简单：🌟
中等：🌟🌟
困难：🌟🌟🌟

经典题目#

232.用栈实现队列 🌟#

力扣链接

题目描述#

使用栈实现队列的下列操作：

push(x) — 将一个元素放入队列的尾部。
pop() — 从队列首部移除元素。
peek() — 返回队列首部的元素。
empty() — 返回队列是否为空。

示例：

1
MyQueue queue = new MyQueue();
2
queue.push(1);
3
queue.push(2);
4
queue.peek();  // 返回 1
5
queue.pop();   // 返回 1
6
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

解题思路#

队列先进先出，如 1 -> 2 -> 3，3 先进队列，同样也是先出队列

如果想用栈来模拟队列，需要两个栈来实现

进栈：将元素压入输入栈
出栈：如果输出栈不为空，则直接从栈顶弹出；为空时，需要将输入栈所有元素压入输出栈，再从输出栈弹出数据
如果两个栈都为空，则模拟队列为空

代码#

1
var MyQueue = function () {
2
  this.stackIn = []
3
  this.stackOut = []
4
}
5

6
/**
7
 * @param {number} x
8
 * @return {void}
9
 */
10
MyQueue.prototype.push = function (x) {
11
  this.stackIn.push(x)
12
}
13

14
/**
15
 * @return {number}
16
 */
17
MyQueue.prototype.pop = function () {
18
  if (this.stackOut.length) {
19
    return this.stackOut.pop()
20
  }
21
  while (this.stackIn.length) {
22
    this.stackOut.push(this.stackIn.pop())
23
  }
24
  return this.stackOut.pop()
25
}
26

27
/**
28
 * @return {number}
29
 */
30
MyQueue.prototype.peek = function () {
31
  const x = this.pop()
32
  this.stackOut.push(x)
33
  return x
34
}
35

36
/**
37
 * @return {boolean}
38
 */
39
MyQueue.prototype.empty = function () {
40
  return !this.stackIn.length && !this.stackOut.length
41
}

225. 用队列实现栈 🌟#

力扣链接 🌟

题目描述#

使用队列实现栈的下列操作：

push(x) — 元素 x 入栈
pop() — 移除栈顶元素
top() — 获取栈顶元素
empty() — 返回栈是否为空

注意:

你只能使用队列的基本操作— 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解题思路#

类比用栈实现队列，使用两个栈来实现，那么此处也可以用两个队列来实现栈

如何用一个队列实现栈？

入队列：添加元素进队列
出队列：获取队列长度，将对首元素重新入队列，直到只剩最后一个元素
如果队列为空，则模拟栈为空

代码#

1
// 使用set解决
2
var intersection = function (nums1, nums2) {
3
  const set1 = new Set(nums1)
4
  const result = new Set()
5

6
  for (let i of nums2) {
7
    if (set1.has(i)) {
8
      result.add(i)
9
    }
10
  }
11
  return [...result]
12
}
13
// 使用数组解决
14
var intersection = function (nums1, nums2) {
15
  const record = new Array(1000).fill(0)
16
  const result = new Set()
17
  for (let i of nums1) {
18
    record[i] = 1
19
  }
20
  for (let i of nums2) {
21
    if (record[i] === 1) result.add(i)
22
  }
23

24
  return [...result]
25
}

用 set 作为哈希表时，每次 insert 值时都需要对这个值做哈希运算，转变为另一个内部存储的值，同时需要开辟新的空间存储，相对来说需要花费时间更多。
用数组作为哈希表效率高，用下标做哈希映射，速度是最快的

20. 有效的括号 🌟#

力扣链接 🌟

题目描述#

给定一个只包括 ’(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

1
输入: "()"
2
输出: true
3

4
输入: "()[]{}"
5
输出: true
6

7
输入: "([)]"
8
输出: false

解题思路#

栈结构非常适合做匹配类的题目

遇到左括号，则入栈
遇到右括号，则判断栈顶元素是否匹配，匹配则出栈，否则返回 false
循环结束后，栈为空，则返回 true

代码#

1
var isValid = function (s) {
2
  const map = new Map()
3
  map.set('(', ')')
4
  map.set('[', ']')
5
  map.set('{', '}')
6

7
  const arr = Array.from(s)
8
  let result = []
9
  for (let i of arr) {
10
    const right = map.get(i)
11
    if (right) {
12
      result.unshift(i)
13
      continue
14
    }
15
    if (map.get(result.shift()) !== i) {
16
      return false
17
    }
18
  }
19
  return !result.length
20
}

1047. 删除字符串中的所有相邻重复项 🌟#

力扣链接 🌟

题目描述#

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

1
输入："abbaca"
2
输出："ca"
3
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

解题思路#

遍历字符串数组，如果当前字符等于栈顶元素，出栈，否则入栈

代码#

1
var removeDuplicates = function (s) {
2
  const arr = Array.from(s)
3

4
  const result = []
5
  for (let i of arr) {
6
    if (result[result.length - 1] !== i) {
7
      result.push(i)
8
    } else {
9
      result.pop()
10
    }
11
  }
12
  return result.join('')
13
}

音乐

音乐

栈 LIFO#

操作#

实现方式#

队列 FIFO#

操作#

实现方式#

经典题目#

232.用栈实现队列 🌟#

题目描述#

解题思路#

代码#

225. 用队列实现栈 🌟#

题目描述#

解题思路#

代码#

20. 有效的括号 🌟#

题目描述#

解题思路#

代码#

1047. 删除字符串中的所有相邻重复项 🌟#

题目描述#

解题思路#

代码#

音乐

文章目录