栈满足先进后出，队列满足先进先出。

用栈实现队列 (opens new window)

class MyQueue {
  private queue: number[] = [];

  push(value: number): void {
    this.queue.push(value);
  }

  pop(): number | undefined {
    return this.queue.shift();
  }

  peek(): number | undefined {
    return this.queue[0];
  }

  empty(): boolean {
    return !this.queue.length;
  }
}

用队列实现栈 (opens new window)

class MyStack {
  private stack: number[] = [];

  push(value: number): void {
    this.stack.push(value);
  }

  pop(): number | undefined {
    return this.stack.shift();
  }

  top(): number {
    const n = this.stack.length;
    return this.stack[n - 1];
  }

  empty(): boolean {
    return !this.stack.length;
  }
}

滑动窗口的最小值 (opens new window)

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里面的最大值。

function maxSlidingWindow(nums: number[], k: number): number[] {
  const { length } = nums;
  if (!k || !length) return [];
  const deque: number[] = [];
  for (let i = 0; i < k; i++) {
    cleanDeque(deque, nums, i, k);
    deque.push(i);
  }

  const res: number[] = [];
  res.push(nums[deque[0]]);
  for (let i = k; i < length; ++i) {
    cleanDeque(deque, nums, i, k);
    deque.push(i);
    res.push(nums[deque[0]]);
  }
  return res;
}

/**
 * 刷新双端队列
 * @param queue
 * @param nums
 * @param index
 * @param k
 */
function cleanDeque(
  queue: number[],
  nums: number[],
  index: number,
  k: number
): void {
  // 如果双向队列中包含不是滑动窗口的数，直接出队
  if (queue.length && index >= k + queue[0]) {
    queue.shift();
  }
  while (queue.length && nums[index] > nums[queue[queue.length - 1]]) {
    queue.pop();
  }
}

有效的括号 (opens new window)

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

有效字符串需满足：

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

function isValid(s: string): boolean {
  const n = s.length
  if (n % 2) return false

  const stack: string[] = []
  let index = 0
  while (index < n) {
    const letter = s[index]
    if (letter === '(' || letter === '{' || letter === '[') stack.push(letter)
    else {
      switch (letter) {
        case ')': {
          if (stack.pop() !== '(') return false
          break
        }
        case '}': {
          if (stack.pop() !== '{') return false
          break
        }
        case ']': {
          if (stack.pop() !== '[') return false
          break
        }
      }
    }
    index++
  }
  return !stack.length
}

字符串解码 (opens new window)

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

function decodeString(s: string): string {
  const stack: string[] = []
  for (const char of s) {
    if (char !== ']') {
      stack.push(char)
      continue
    }
    // 每当遇到 ']' 的时候，就可以把栈里面的数据取出来，然后计算出之前的字母的数量
    let cur = stack.pop()
    let str = '' // 括号内的字母
    while (cur !== '[') {
      str = cur + str
      cur = stack.pop()
    }
    cur = stack.pop()
    let num = '' // 括号前的数字
    while (!isNaN(+cur!)) {
      num = cur + num
      cur = stack.pop()
    }
    cur && stack.push(cur) // 把上一次的字母加回去
    stack.push(str.repeat(+num))
  }
  return stack.join('')
}

根据身高建队列 (opens new window)

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意： 总人数少于1100人。

function reconstructQueue(people: number[][]): number[][] {
  const n = people.length
  if (!n) return []
  // 按身高进行降序排列，然后按照前面的人数进行升序排列
  people.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]))
  const res: number[][] = []

  for (let i = 0; i < n; i++) {
    res.splice(people[i][1], 0, people[i])
  }

  return res
}

数组中的第 k 个最大元素 (opens new window)

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

function findKthLargest(nums: number[], k: number): number {
  nums.sort((a, b) => b - a)
  return nums[k - 1]
}