常见栈和队列算法

[Leo-lin214]

对栈和队列数据结构常见的算法进行总结，也为了更好滴应对后面深入学习算法。

包含 min 函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，要求时间复杂度为 O(1)。

答案

  const dataStack = [];
  const minStack = [];
  const push = data => {
    dataStack.push(data);
    if (minStack.length === 0 || data < min()) {
      minStack.push(data);
    } else {
      minStack.push(min());
    }
  }
  const pop = () => {
    minStack.pop();
    return dataStack.pop();
  }
  const min = () {
    return minStack.length && minStack[minStack.length - 1];
  }
  

滑动窗口的最大值（双端队列）

给定一个数组 nums，有一个大小为 K 的滑动窗口从数组的最左侧移动到数组的最右侧，你只可以看到在滑动窗口 K 内的数字。

滑动窗口每次只向右移动一位，返回滑动窗口的最大值。

答案

  const getWindowMin = (nums, k) => {
    const queue = [];
    const result = [];
    for (let i = 0; i < nums.length; i++) {
      if (queue.length && i - queue[0] > k - 1) {
        queue.shift();
      }
      let j = queue.length - 1;
      while (j >= 0 && nums[queue[j]] <= nums[i]) {
        queue.pop();
        j--;
      }
      queue.push(i);
      if (i >= k - 1) {
        result.push(nums[queue[0]]);
      }
    }
    return result;
  }
  

用两个栈实现队列

用两个栈来说实现一个队列，完成队列的 Push 和 Pop 操作。

队列中的元素为 int 类型。

答案

  const stack1 = [];
  const stack2 = [];
  const push = data => {
    stack1.push(data);
  }
  const pop = () => {
    if (!stack2.length) {
      while (stack1.length) {
        stack2.push(stack1.pop());
      } 
    }
    return stack2.pop() || null;
  }
  

用两个队列实现栈

用两个队列实现一个栈，完成栈的 Push 和 Pop 操作。

答案

  const queue1 = [];
  const queue2 = [];
  const push = data => {
    if (!queue1.length) {
      queue1.push(data);
      while (queue2.length) {
        queue1.push(queue2.shift());
      }
    } else if (!queue2.length) {
      queue2.push(data);
      while (queue1.length) {
        queue2.push(queue1.shift());
      }
    }
  }
  const pop = () => {
    if (queue1.length) {
      return queue1.shift();
    } else if (queue2.length) {
      return queue2.shift();
    }
  }
  

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等，如1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个弹出序列，而4，3，5，1，2就不可能是该压栈序列的弹出序列。

答案

  const isStack = (stack1, stack2) => {
    if (!stack1 || !stack2 || !stack1.length || !stack2.length) return false;
    let index = 0;
    const result = [];
    for (let i = 0; i < stack1.length; i++) {
      result.push(stack1[i]);
      while (result.length && result[result.length - 1] === stack2[index]) {
        result.pop();
        index++;
      }
    }
    return result.length === 0;
  }