LeetCode - 栈与队列
PS：按照代码随想录的题单顺序刷题，记录一下。
1. 基本概念
2. 用栈实现队列
描述
LeetCode232 - 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 简单
实现 MyQueue 类：
void push(int x)将元素x推到队列的末尾。int pop()从队列的开头移除并返回元素。int peek()返回队列开头的元素。boolean empty()如果队列为空，返回true；否则，返回false。
说明：
- 你只能使用标准的栈操作，也就是只有
push to top，peek/pop from top，size和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用
list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例1：
txt
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false思路
用两个栈实现队列，一个栈专门入队，一个栈出队，出队时如果栈为空，将入队栈依次出栈并加入到出队栈，此时先出栈的元素就是先加入的元素。
232 - 用栈实现队列
javascript
var MyQueue = function() {
this.inStack = [];
this.outStack = [];
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.inStack.push(x);
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
if(!this.outStack.length) {
while(this.inStack.length) {
this.outStack.push(this.inStack.pop());
}
}
if(this.outStack.length) {
return this.outStack.pop();
}
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
if(this.outStack.length) {
return this.outStack[this.outStack.length - 1];
}
return this.inStack[0];
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return !(this.inStack.length + this.outStack.length);
};3. 用队列实现栈
描述
LeetCode225 - 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。简单
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的标准操作，也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。你可以使用
list（列表）或者deque（双端队列）来模拟一个队列, 只要是标准的队列操作即可。
示例1：
txt
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False思路
为了实现栈的后进先出，需要将后面添加的元素放到到队列的头部，可以使用一个辅助队列，每次添加时先添加到辅助队列，再将已有元素出队，添加到辅助队列，此时满足后面添加的元素排在队列前面，再将辅助队列与队列交换。
225 - 用队列实现栈
javascript
var Queue = function() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
Queue.prototype.push = function(x) {
this.items[this.count] = x;
this.count++;
}
Queue.prototype.pop = function() {
if(this.size() > 0) {
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
return undefined;
}
Queue.prototype.size = function() {
return this.count - this.lowestCount;
}
Queue.prototype.peek = function() {
return this.items[this.lowestCount];
}
var MyStack = function() {
this.queue = new Queue();
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
let count = this.queue.size();
this.queue.push(x);
while(count) {
this.queue.push(this.queue.pop());
count--;
}
return true;
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
return this.queue.pop();
};
/**
* @return {number}
*/
MyStack.prototype.top = function() {
return this.queue.peek();
};
/**
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return this.queue.size() === 0;
};4. 有效的括号
描述
LeetCode20 - 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。简单
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例1：
txt
输入：s = "()"
输出：true示例2：
txt
输入：s = "(]"
输出：false思路
当碰到左括号则入栈，右括号则出栈并比较是否是一对，不是则返回 false，当结束遍历后栈为空，返回 true。
20 - 有效的括号
javascript
var isValid = function (s) {
const stack = [];
for (const c of s) {
if (c === '(' || c === '[' || c === '{') {
stack.push(c);
} else {
let temp = stack.pop();
if ((c === ')' && temp !== '(') || c === ']' && temp !== '[' || c === '}' && temp !== '{') {
return false;
}
}
}
return stack.length === 0;
};5. 删除字符串中的所有相邻重复项
描述
LeetCode1047 - 给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。简单
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例1：
txt
输入："abbaca"
输出："ca"
解释：在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。思路
如果当前元素删除后，后面就需要比较上一个元素，应该要想到栈结构。如果与栈顶元素相同则出栈，否则入栈。
1047 - 删除字符串中的所有相邻重复项
javascript
var removeDuplicates = function(s) {
const stack = [];
for(let c of s) {
if(stack.length) {
if(stack[stack.length - 1] === c) {
stack.pop();
} else {
stack.push(c)
}
} else {
stack.push(c);
}
}
return stack.join('')
};6. 逆波兰表达式求值
描述
LeetCode150 - 给你一个字符串数组 tokens，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。中等
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是向零截断。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例1：
txt
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例2：
txt
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6思路
用栈进行存储，当出现运算符，将刚入栈的两个元素进行计算后入栈。逆波兰表达式是后缀表达式，还需要熟悉中缀表达式转后缀表达式。
150 - 逆波兰表达式求值
javascript
var evalRPN = function(tokens) {
const stack = [];
for(const c of tokens) {
switch(c) {
case '+':
stack.push(stack.pop() + stack.pop());
break;
case '-':
stack.push(-(stack.pop() - stack.pop()));
break;
case '*':
stack.push(stack.pop() * stack.pop());
break;
case '/':
const second = stack.pop();
const first = stack.pop();
// 小数点后截断:trunc
stack.push(Math.trunc(first / second));
break;
default:
stack.push(Number(c));
}
}
return stack.pop()
};7. 滑动窗口的最大值
描述
LeetCode239 - 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。困难
返回滑动窗口中的最大值。
示例1：
txt
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]示例2：
txt
输入：nums = [1], k = 1
输出：[1]思路
单调队列。每次要入队时，将队列内小于该值的元素从右边全部出队，因为当该入队元素在窗口内时，前面小于该值的元素均不会是最大值。这样保持队列单调递减，队列左边是窗口内最大值，当要出窗口的元素等于最大值时，将最大值从左边出队，窗口内第二大的值成为最大值。单调队列的优势在于当最大值出窗口后，马上能确定新窗口内的最大值。
239 - 滑动窗口的最大值
javascript
var Queue = function() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
Queue.prototype.enQueue = function(x) {
this.items[this.count++] = x;
}
Queue.prototype.deQueue = function() {
if(this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
Queue.prototype.deQueueEnd = function() {
if(this.isEmpty()) {
return undefined;
}
const result = this.items[this.count - 1];
delete this.items[this.count - 1];
this.count--;
return result;
}
Queue.prototype.isEmpty = function() {
return this.size() === 0;
}
Queue.prototype.peek = function() {
return this.items[this.lowestCount];
}
Queue.prototype.end = function() {
if(this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
Queue.prototype.size = function() {
return this.count - this.lowestCount;
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
const queue = new Queue();
let left = 0, right = 0;
const res = [];
while(right < nums.length) {
// 加入队列
if(queue.isEmpty()) {
queue.enQueue(nums[right]);
} else {
while(queue.end() < nums[right]) {
queue.deQueueEnd();
}
queue.enQueue(nums[right]);
}
if(right - left + 1 === k) {
res.push(queue.peek());
// 窗口左边元素等于窗口内最大值
if(nums[left] === queue.peek()) {
queue.deQueue();
}
left++;
}
right++;
}
return res;
};8. 前 K 个高频元素
描述
LeetCode347 - 给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。中等
示例1：
txt
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]示例2：
txt
输入：nums = [1], k = 1
输出：[1]思路
哈希表+快排：首先使用哈希表保存每个元素出现的次数，然后转为数组，使用快排后将频率最高的 k 种元素返回。不过这种方法时间复杂度是 O(nlogn)，进阶版可以使用堆排序，堆的大小为 k，时间复杂度是 O(nlogk)。
347 - 前 k 个高频元素
javascript
// 快排
var topKFrequent = function(nums, k) {
const map = new Map();
for(let i = 0; i < nums.length; i++) {
map.set(nums[i], (map.get(nums[i]) || 0) + 1);
}
const res = [];
const arr = Array.from(map.entries()).sort((a, b) => b[1] - a[1]);
for(let i = 0; i < k; i++) {
res.push(arr[i][0])
}
return res;
};