初级算法-栈与队列

主要记录算法和数据结构学习笔记，新的一年更上一层楼！

• 栈先进后出，不提供走访功能和迭代器
• 递归、表达式求值、括号匹配、进制转换一般利用栈

---

• 队列先进先出
• 满队列：front==(rear+1)%m
• 循环队列出队操作 front = (front+1) % (m+1)
• 循环队列，f 队头，r 队尾，队列中的元素个数为 (r-f+MAX+1) % MAX
• 循环队列队空：rear==front；队满：front == (rear+1) % MAX
• 链接方式存储队列，进行插入运算时 常修改尾指针，插入前为空，头尾都需修改。
• 循环队列：尾指针-头指针+容量，front小于rear时N-front+rear

一、栈实现队列

1.题目：使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
示例

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
2.解题思路：

// 使用两个数组的栈方法（push, pop） 实现队列
/**
* Initialize your data structure here.
*/
var MyQueue = function() {this.stackIn = [];this.stackOut = [];
};/**
* Push element x to the back of queue. 
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {this.stackIn.push(x);
};/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {const size = this.stackOut.length;if(size) {return this.stackOut.pop();}while(this.stackIn.length) {this.stackOut.push(this.stackIn.pop());}return this.stackOut.pop();
};/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {const x = this.pop();this.stackOut.push(x);return x;
};/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {return !this.stackIn.length && !this.stackOut.length
};
// 运行时间：60ms
// 内存消耗：40.8MB

二、队列实现栈

1.题目：使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

2.解题思路：

// 使用两个队列实现
/*** Initialize your data structure here.*/
var MyStack = function() {this.queue1 = [];this.queue2 = [];
};/*** Push element x onto stack. * @param {number} x* @return {void}*/
MyStack.prototype.push = function(x) {this.queue1.push(x);
};/*** Removes the element on top of the stack and returns that element.* @return {number}*/
MyStack.prototype.pop = function() {// 减少两个队列交换的次数， 只有当queue1为空时，交换两个队列if(!this.queue1.length) {[this.queue1, this.queue2] = [this.queue2, this.queue1];}while(this.queue1.length > 1) {this.queue2.push(this.queue1.shift());}return this.queue1.shift();
};/*** Get the top element.* @return {number}*/
MyStack.prototype.top = function() {const x = this.pop();this.queue1.push(x);return x;
};/*** Returns whether the stack is empty.* @return {boolean}*/
MyStack.prototype.empty = function() {return !this.queue1.length && !this.queue2.length;
};// 运行时间：64ms
// 内存消耗：40.9MB

// 使用一个队列实现
/*** Initialize your data structure here.*/
var MyStack = function() {this.queue = [];
};/*** Push element x onto stack. * @param {number} x* @return {void}*/
MyStack.prototype.push = function(x) {this.queue.push(x);
};/*** Removes the element on top of the stack and returns that element.* @return {number}*/
MyStack.prototype.pop = function() {let size = this.queue.length;while(size-- > 1) {this.queue.push(this.queue.shift());}return this.queue.shift();
};/*** Get the top element.* @return {number}*/
MyStack.prototype.top = function() {const x = this.pop();this.queue.push(x);return x;
};/*** Returns whether the stack is empty.* @return {boolean}*/
MyStack.prototype.empty = function() {return !this.queue.length;
};// 运行时间：76ms
// 内存消耗：41.1MB

三、有效的括号

1.题目：
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

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

示例

示例 1:输入: "()"
输出: true
示例 2:输入: "()[]{}"
输出: true
示例 3:输入: "(]"
输出: false
示例 4:输入: "([)]"
输出: false
示例 5:输入: "{[]}"
输出: true

2.解题思路：

var isValid = function (s) {const stack = [];for (let i = 0; i < s.length; i++) {let c = s[i];switch (c) {case '(':stack.push(')');break;case '[':stack.push(']');break;case '{':stack.push('}');break;default:if (c !== stack.pop()) {return false;}}}return stack.length === 0;
};
// 简化版本
var isValid = function(s) {const stack = [], map = {"(":")","{":"}","[":"]"};for(const x of s) {if(x in map) {stack.push(x);continue;};if(map[stack.pop()] !== x) return false;}return !stack.length;
};
// 运行时间：52ms
// 内存消耗：41.6MB

四、删除字符串中的所有相邻重复项

1.题目：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例

输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。

2.解题思路：

// 使用栈
var removeDuplicates = function(s) {const stack = [];for(const x of s) {let c = null;if(stack.length && x === (c = stack.pop())) continue;c && stack.push(c);stack.push(x);}return stack.join("");
};
// 运行时间：76ms
// 内存消耗：51.1MB   

// 原地解法（双指针模拟栈）
var removeDuplicates = function(s) {s = [...s];let top = -1; // 指向栈顶元素的下标for(let i = 0; i < s.length; i++) {if(top === -1 || s[top] !== s[i]) { // top === -1 即空栈s[++top] = s[i]; // 入栈} else {top--; // 推出栈}}s.length = top + 1; // 栈顶元素下标 + 1 为栈的长度return s.join('');
};
// 运行时间：64ms
// 内存消耗：46.8MB   

五、逆波兰表达式求值

1.题目
根据 逆波兰表示法，求表达式的值。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例

示例 1：输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]输出: 22解释:该算式转化为常见的中缀算术表达式为：((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
= ((10 * (6 / (12 * -11))) + 17) + 5       
= ((10 * (6 / -132)) + 17) + 5     
= ((10 * 0) + 17) + 5     
= (0 + 17) + 5    
= 17 + 5    
= 22    
逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。逆波兰表达式主要有以下两个优点：-去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。-适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

2.解题思路：

var evalRPN = function (tokens) {const stack = [];for (const token of tokens) {if (isNaN(Number(token))) { // 非数字const n2 = stack.pop(); // 出栈两个数字const n1 = stack.pop();switch (token) { // 判断运算符类型，算出新数入栈case "+":stack.push(n1 + n2);break;case "-":stack.push(n1 - n2);break;case "*":stack.push(n1 * n2);break;case "/":stack.push(n1 / n2 | 0);break;}} else { // 数字stack.push(Number(token));}}return stack[0]; // 因没有遇到运算符而待在栈中的结果
};
// 运行时间：64ms
// 内存消耗：43.8MB

六、滑动窗口最大值

1.题目：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例

提示：
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

2.解题思路：

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
var maxSlidingWindow = function (nums, k) {class MonoQueue {queue;constructor() {this.queue = [];}enqueue(value) {let back = this.queue[this.queue.length - 1];while (back !== undefined && back < value) {this.queue.pop();back = this.queue[this.queue.length - 1];}this.queue.push(value);}dequeue(value) {let front = this.front();if (front === value) {this.queue.shift();}}front() {return this.queue[0];}}let helperQueue = new MonoQueue();let i = 0, j = 0;let resArr = [];while (j < k) {helperQueue.enqueue(nums[j++]);}resArr.push(helperQueue.front());while (j < nums.length) {helperQueue.enqueue(nums[j]);helperQueue.dequeue(nums[i]);resArr.push(helperQueue.front());i++, j++;}return resArr;
};
#运行时间：8528ms
#内存消耗：75.3MB

七、前K个高频元素

1.题目：
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例

示例 1:输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:输入: nums = [1], k = 1
输出: [1]

提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 $O(n\log n)$ , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

// js 没有堆 需要自己构造
class Heap {constructor(compareFn) {this.compareFn = compareFn;this.queue = [];}// 添加push(item) {// 推入元素this.queue.push(item);// 上浮let index = this.size() - 1; // 记录推入元素下标let parent = Math.floor((index - 1) / 2); // 记录父节点下标while (parent >= 0 && this.compare(parent, index) > 0) { // 注意compare参数顺序[this.queue[index], this.queue[parent]] = [this.queue[parent], this.queue[index]];// 更新下标index = parent;parent = Math.floor((index - 1) / 2);}}// 获取堆顶元素并移除pop() {// 堆顶元素const out = this.queue[0];// 移除堆顶元素 填入最后一个元素this.queue[0] = this.queue.pop();// 下沉let index = 0; // 记录下沉元素下标let left = 1; // left 是左子节点下标 left + 1 则是右子节点下标let searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left;while (searchChild !== undefined && this.compare(index, searchChild) > 0) { // 注意compare参数顺序[this.queue[index], this.queue[searchChild]] = [this.queue[searchChild], this.queue[index]];// 更新下标index = searchChild;left = 2 * index + 1;searchChild = this.compare(left, left + 1) > 0 ? left + 1 : left;}return out;}size() {return this.queue.length;}// 使用传入的 compareFn 比较两个位置的元素compare(index1, index2) {// 处理下标越界问题if (this.queue[index1] === undefined) return 1;if (this.queue[index2] === undefined) return -1;return this.compareFn(this.queue[index1], this.queue[index2]);}}const topKFrequent = function (nums, k) {const map = new Map();for (const num of nums) {map.set(num, (map.get(num) || 0) + 1);}// 创建小顶堆const heap= new Heap((a, b) => a[1] - b[1]);// entry 是一个长度为2的数组，0位置存储key，1位置存储valuefor (const entry of map.entries()) {heap.push(entry);if (heap.size() > k) {heap.pop();}}// return heap.queue.map(e => e[0]);const res = [];for (let i = heap.size() - 1; i >= 0; i--) {res[i] = heap.pop()[0];}return res;
};
#运行时间：88ms
#内存消耗：44.4MB

---