字数
1446 字
阅读时间
8 分钟
概述
栈是先进后出（FILO），队列是先进先出（FIFO）
对应操作：
Stack：push + pop + peek(top) + isEmpty
Queue：offer + poll + peek(top) + isEmpty
关于 Java 的部分集合接口及实现类参考：Java集合
用栈实现队列
主要思路：使用两个栈结构，一个作为队列的 push 对象，一个作为队列的 pop 对象
- 重点留意队列 pop 时需要先判断 入栈结构是否存在元素
Code JS
js
var MyQueue = function() {
this.stackIn = [];
this.stackOut = [];
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.stackIn.push(x);
};
/**
* @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();
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
const x = this.pop();
this.stackOut.push(x);
return x;
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return !this.stackIn.length && !this.stackOut.length;
};Code Java
java
lass MyQueue {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
/** Initialize your data structure here. */
public MyQueue() {
stackIn = new Stack<>(); // 负责进栈
stackOut = new Stack<>(); // 负责出栈
}
/** Push element x to the back of queue. */
public void push(int x) {
stackIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
dumpstackIn();
return stackOut.pop();
}
/** Get the front element. */
public int peek() {
dumpstackIn();
return stackOut.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
private void dumpstackIn(){
if (!stackOut.isEmpty()) return;
while (!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/用队列实现栈
思路：一个队列与栈保持一致，一个队列用来作为 push 对象的数据备份队列
Code JS
js
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;
};Code Java
java
class MyStack {
Queue<Integer> queue; // 与栈中元素保持一致的队列，队列的入口作为栈的出口
Queue<Integer> queueRecord; // 数据备份队列
public MyStack() {
queue = new LinkedList<>();
queueRecord = new LinkedList<>();
}
public void push(int x) {
queueRecord.offer(x);
while (!queue.isEmpty()) {
queueRecord.offer(queue.poll());
}
Queue<Integer> temp = queueRecord;
queueRecord = queue;
queue = temp;
}
public int pop() {
// 弹出队列的首部元素
return queue.poll();
}
public int top() {
// 返回队列的首部元素
return queue.peek();
}
public boolean empty() {
// 判断队列是否为空
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/逆波兰表达式
txt
逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。思路：理解了逆波兰表达式就会发现，栈的结构天然适配逆波兰表达式
Code JS
js
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
let stack = [];
for (let i = 0; i < tokens.length; i++) {
if (tokens[i] == "+") {
stack.push(stack.pop() * 1 + stack.pop() * 1);
} else if (tokens[i] == "-") {
stack.push(-stack.pop() + stack.pop());
} else if (tokens[i] == "*") {
stack.push(stack.pop() * stack.pop());
} else if (tokens[i] == "/") {
let temp1 = stack.pop();
let temp2 = stack.pop();
stack.push(temp2 / temp1 > 0 ? Math.floor(temp2 / temp1) : Math.ceil(temp2 / temp1));
} else {
stack.push(parseInt(tokens[i]));
}
}
return stack.pop();
};Code Java
java
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
for (int i = 0; i < tokens.length; ++i) {
if ("+".equals(tokens[i])) { // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
stack.push(stack.pop() + stack.pop()); // 注意 - 和/ 需要特殊处理
} else if ("-".equals(tokens[i])) {
stack.push(-stack.pop() + stack.pop());
} else if ("*".equals(tokens[i])) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(tokens[i])) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
} else {
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}滑动窗口最大值
思路：维护一个单调队列，队列的入口始终是最大值，队列的元素单调的
设计单调队列的时候，pop，和 push 操作要保持如下规则：
- pop(value)：如果窗口移除的元素 value 等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果 push 的元素 value 大于入口元素的数值，那么就将队列入口的元素弹出，直到 push 元素的数值小于等于队列入口元素的数值为止
Code JS
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
class MyQueue {
queue;
constructor() {
this.queue = [];
}
// 入列
enQueue(value) {
while (this.queue.length && value > this.queue[this.queue.length - 1]) {
this.queue.pop();
}
this.queue.push(value);
}
// 出列
deQueue(value) {
if (this.queue[0] == value) {
this.queue.shift();
}
}
// 返回队列首个元素
front() {
return this.queue[0];
}
}
let helperQueue = new MyQueue();
let res = [];
let num = 0, i = 0;
while (i < k) {
helperQueue.enQueue(nums[i++]);
}
res.push(helperQueue.front());
while (i < nums.length) {
helperQueue.enQueue(nums[i]);
helperQueue.deQueue(nums[num]);
res.push(helperQueue.front());
num++;
i++;
}
return res;
};前 k 个高频元素
TODO：
贡献者
jiechen