本文已参与「新人创作礼」活动，一起开启掘金创作之路。
关键词：操作受限的线性表 先进先出-队列 后进先出-栈
队列和栈不是全新的东西，只不过是多加了一些约束条件的数组或者链表而已。
队列和栈使用的场景都是在处理临时数据的时候，把数据按顺序处理，并在处理完成后销毁数据。
定义
相同点： 两个都是“操作受限”的线性表。
不同点:
栈：LIFO 后进先出，添加和删除的操作只能在一端进行。最典型的例子就是汉诺塔。
队列：FIFO 先入先出，添加和删除数据的操作分别是在两端进行的。拿号排队。
栈
队列
各个操作的复杂度
入栈、出栈、入队、出队，复杂度都是 O(1).
leetcode
【栈】20 有效的括号
function valid(s) { const ss = s.split(""); if (ss.length % 2 !== 0) return false; const diction = { '}': '{', ']': '[', ')': '(' } let cache = []; for (let i = 0; i < ss.length; i++) { if (i >= 1 && diction[ss[i]] === cache[cache.length - 1]) { cache.pop() } else { cache.push(ss[i]) } } return !cache.length }
【栈】71 简化路径
function simplifyPath(path) { const paths = path.split('/'); let r = []; for (let i = 0; i < paths.length; i++) { if (paths[i] === '..') { r.pop() } else if (paths[i] && paths[i] !== '.') { r.push(paths[i]) } } return '/' + r.join('/'); }
【队列】滑动窗口最大值
var maxSlidingWindow = function (nums, k) { const res = []; //分块与预处理 //左右分块 const n = nums.length; const left = new Array(n); const right = new Array(n); for (let i = 0; i < n; i++) { if (i % k === 0) { right[i] = nums[i]; } else { right[i] = Math.max(right[i - 1], nums[i]); } } for (let i = n - 1; i >= 0; i--) { if (i + 1 === n || (i + 1) % k === 0) { left[i] = nums[i]; } else { left[i] = Math.max(left[i + 1], nums[i]); } } for (let i = 0; i <= n - k; i++) { res.push(Math.max(left[i], right[i + k - 1])); } return res; }; // 双端队列 var maxSlidingWindow = function (nums, k) { const n = nums.length if (n < 2 || k === 1) return nums const ans = new Array(n - k + 1) const q = [] for (let i = 0; i < n; i++) { // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求 while (q.length && nums[q[q.length - 1]] <= nums[i]) { q.pop() } q.push(i) // 添加当前值对应的数组下标 if (q[0] <= i - k) { q.shift() } if (i + 1 >= k) { ans[i + 1 - k] = nums[q[0]] } } return ans };
