/栈(Stack)，先进后出。Fast In - Last Out、FILO。添加、删除都是 O(1)、查询为 O(n)，元素是无序的。

    队列(Queue)，先进先出。Fast In - First Out、FIFO。 添加、删除都是 O(1)、查询为 O(n)，元素是无序的。

    双端队列(Deque、Double-End Queue)，queue 和 stack 的结合体。插入和删除都是 O(1) 操作。

    Java 的 Stack 源码

    Java 的 Queue 源码

    Python 的 heapq

    高性能的 container 库

    优先队列(Priority Queue)。
    插入操作 O(1)，取出操作 O(log n)，可以按照元素的优先级取出。
    底层具体实现的数据结构较为多样和复杂，可以由 heap、bst、avl 等实现。

    Java 的 PriorityQueue 文档

    structure_operations.png

    https://www.bigocheatsheet.com/

    有效的括号（亚马逊、JPMorgan 在半年内面试常考）
    最小栈（亚马逊在半年内面试常考）
    柱状图中最大的矩形（亚马逊、微软、字节跳动在半年内面试中考过）
    滑动窗口最大值（亚马逊在半年内面试常考）

    设计循环双端队列（Facebook 在 1 年内面试中考过）
    接雨水（亚马逊、字节跳动、高盛集团、Facebook 在半年内面试常考）

    1. // 有效的括号
    2. // 如果一个题目具有最近相关性，它就可以用栈来解决。
    4. // 思路1：暴力求解，不断 replace 匹配括号，O(n^2)
    5. // 思路2：Stack
    7. /**
    8.  * @param {string} s
    9.  * @return {boolean}
    10.  */
    11. var isValid = function(s) {
    12.   if (s.length % 2 === 1) return false;
    14.   const map = new Map([
    15.     ['{', '}'],
    16.     ['[', ']'],
    17.     ['(', ')']
    18.   ]);
    20.   const stack = [];
    22.   let c;
    24.   for (let i = 0; i < s.length; i++) {
    25.     c = s[i];
    27.     if (map.get(c)) {
    28.       stack.push(map.get(c));
    29.     } else {
    30.       if (stack.pop() !== c) {
    31.         return false;
    32.       }
    33.     }
    34.   }
    36.   return stack.length === 0;
    37. };
    // 最小栈

// 思路：使用辅助栈
// 后续如果遇到用栈来实现队列，都可以考虑使用两个栈来解决

var MinStack = function() {
  this.stack = [];
  this.minStack = [Infinity];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
  this.stack.push(val);
  this.minStack.push(
    Math.min(this.minStack[this.minStack.length - 1], val)
  );
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  this.stack.pop();
  this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.minStack[this.minStack.length - 1]
};

    // 柱状图中最大的矩形（★★★）

// 思路1：暴力求解 O(n^3)
// 思路2：暴力求解，枚举柱子高度，寻找左右边界 
// 思路3：stack，单调递增栈

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  let maxArea = 0;

  const stack = [];

  heights = [0, ...heights, 0];

  for (let i = 0; i < heights.length; i++) {
    while (heights[i] < heights[stack[stack.length - 1]]) {
      maxArea = Math.max(
        maxArea,
        heights[stack.pop()] * (i - stack[stack.length - 1] - 1)
      );
    }

    stack.push(i);
  }

  return maxArea;
};

    // 滑动窗口最大值（★★★）
// 所有的滑动窗口的题目，都可以考虑使用队列解决

// 思路1：暴力求解 O(n*k)
// 思路2：单调队列 O(n+k) -> O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const queue = [], result = [];

  for (let i = 0; i < nums.length; i++) {
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop();
    }

    queue.push(i);

    while (queue[0] <= i - k) {
      queue.shift();
    }

    if (i >= k - 1) result.push(nums[queue[0]]);
  }

  return result;
};

    // 设计循环双端队列（★★☆）

// 思路：数组实现双端队列，数组其实就是一个双端队列，只不过不存在限制

/**
 * @param {number} k
 */
var MyCircularDeque = function(k) {
  this.queue = [];
  this.maxSize = k;
};

MyCircularDeque.prototype.size = function () {
  return this.queue.length;
}

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function(value) {
  if (this.size() < this.maxSize) {
    this.queue.unshift(value);
    return true;
  }
  return false;
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function(value) {
  if (this.size() < this.maxSize) {
    this.queue.push(value);
    return true;
  }
  return false;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function() {
  if (this.size()) {
    this.queue.shift();
    return true;
  }
  return false;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function() {
  if (this.size()) {
    this.queue.pop();
    return true;
  }
  return false;
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function() {
  if (this.size()) {
    return this.queue[0];
  }
  return -1;
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function() {
  if (this.size()) {
    return this.queue[this.size() - 1];
  }
  return -1;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function() {
  return this.size() == 0;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function() {
  return this.size() === this.maxSize;
};

    // 接雨水（★★★）

// 思路1：单调栈
// 思路2：双指针解法

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  const stack = [];

  let maxArea = 0;

  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop();

      if (!stack.length) break;

      const left = stack[stack.length - 1];
      const currWidth = i - left - 1;
      const currHeight = Math.min(height[left], height[i]) - height[top];

      maxArea += currWidth * currHeight;
    }

    stack.push(i);
  }

  return maxArea;
};


/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let maxArea = 0;

  let left = 0,
      right = height.length - 1;

  let leftMax = 0,
      rightMax = 0;

  while (left < right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);

    if (leftMax < rightMax) {
      maxArea += leftMax - height[left++];
    } else {
      maxArea += rightMax - height[right--];
    }
  }

  return maxArea;
};