栈的特点是后入先出，根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索
队列一般常用于 BFS 广度搜索，类似一层一层的搜索。
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
思路：用两个栈实现，一个最小栈始终保证最小值在顶部
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.stack = []; // JS用数组表示栈
this.minStack = [Infinity];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
this.minStack.push(Math.min(this.minStack[this.minStack.length-1],x));
};
/**
* @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];
};var evalRPN = function (tokens) {
const stack = []
for (const item of tokens) {
if (!isNaN(+item)) {
stack.push(item)
} else {
let res = 0
const top = parseInt(stack.pop()) //在栈中的位置靠上（被除数）
const down = parseInt(stack.pop()) //靠下（除数）
switch (item) {
case '+':
res = top + down
break
case '-':
res = down - top
break
case '*':
res = top * down
break
case '/':
res = parseInt(down / top)
break
}
stack.push(res)
}
}
return stack[0]
};给定一个经过编码的字符串，返回它解码后的字符串。
输入：s = "3[a]2[bc]" 输出："aaabcbc"
var decodeString = function (s) {
const stack = []
for (let i = 0; i < s.length; i++) {
const char = s[i]
if (char !== ']') {
stack.push(char)
} else {
let str = ''
while (stack.length > 0) {
const temp = stack.pop()
if (temp !== '[') {
str = temp + str
} else {
let num = ''
while (stack.length > 0) {
const tempNum = stack.pop() // 处理类似100的数字，此时栈中['1','0','0']
if (!isNaN(tempNum)) {
num = tempNum + num
} else {
stack.push(tempNum)
break
}
}
str = str.repeat(+num)
break
}
}
stack.push(str)
}
}
return stack.join('')
}var inorderTraversal = function (root) { //递归
if (root === null) {
return []
}
const res = [];
(function inOrder(root) {
if (!root) {
return
}
inOrder(root.left)
res.push(root.val)
inOrder(root.right)
})(root);
return res
};var inorderTraversal = function (root) {
const stack = []
const res = []
let current = root
while (stack.length > 0 || current) {
while (current) {
stack.push(current)
current = current.left
}
current = stack.pop()
res.push(current.val)
current = current.right
}
return res
};给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
var cloneGraph = function (node) {
let visited = new Map();
return (function clone(node, visited) {
if (!node) {
return null
}
if (visited.has(node)) {
return visited.get(node)
}
const newNode = new Node(node.val)
visited.set(node, newNode)
for (let i = 0; i < node.neighbors.length; i++) {
newNode.neighbors[i] = clone(node.neighbors[i], visited)
}
return newNode
})(node, visited)
};给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
var numIslands = function (grid) {
const nr = grid.length
const nc = grid[0].length
let resNum = 0
for (let i = 0; i < nr; i++) {
for (let j = 0; j < nc; j++) {
if (grid[i][j] === '1') {
resNum++
dfs(grid, i, j)
}
}
}
return resNum
};
const dfs = (grid, row, col) => {
const gr = grid.length
const gc = grid[0].length
if (row < 0 || col < 0 || row >= gr || col >= gc || grid[row][col] === '0') {
return 0
}
grid[row][col] = '0'
dfs(grid, row + 1, col)
dfs(grid, row - 1, col)
dfs(grid, row, col + 1)
dfs(grid, row, col - 1)
}/**
* Initialize your data structure here.
*/
var MyQueue = function () {
this.stack1 = []
this.stack2 = []
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
this.stack1.push(x)
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
if (this.stack2.length > 0) {
return this.stack2.pop()
} else {
while (this.stack1.length > 0) {
this.stack2.push(this.stack1.pop())
}
return this.stack2.pop()
}
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function () {
if (this.stack2.length > 0) {
return this.stack2[this.stack2.length - 1]
} else {
while (this.stack1.length > 0) {
this.stack2.push(this.stack1.pop())
}
return this.stack2[this.stack2.length - 1]
}
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
if (this.stack1.length === 0 && this.stack2.length === 0) {
return true
}
return false
};var updateMatrix = function (matrix) {
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
const m = matrix.length, n = matrix[0].length
const dist = new Array(m).fill(new Array(n).fill(0))
const seen = new Array(m).fill(new Array(n).fill(false))
const queue = []
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
queue.push([i, j])
seen[i][j] = true
}
}
}
while (queue.length > 0) {
const [i, j] = queue.shift()
for (let d = 0; d < 4; d++) {
const ni = i + dirs[d][0]
const nj = j + dirs[d][1]
if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
dist[ni][nj] = dist[i][j] + 1
queue.push([ni, nj])
seen[ni][nj] = true
}
}
}
return dist
};- 熟悉栈的使用场景
- 后入先出，保存临时值
- 利用栈 DFS 深度搜索
- 熟悉队列的使用场景
- 利用队列 BFS 广度搜索