栈
后进先出，数据结构类似于蜂窝煤，js中可以用数组push() pop() 来模拟栈
应用场景
- 十进制转二进制
- 有效的括号（Leetcode20）
- 函数执行栈中
var isValid = function(s) { let stack=[]; for(let i=0;i<s.length;i++){ if(s[i]==="("||s[i]==="["||s[i]==="{"){ stack.push(s[i]) }else{ if(stack[stack.length-1]==="("&&s[i]===")"|| stack[stack.length-1]==="{"&&s[i]==="}"|| stack[stack.length-1]==="["&&s[i]==="]"){ stack.pop() }else{ return false; } } } return stack.length===0 }
队列
后进先出，数据结构类似于排队，js中可以用数组push() shift() 来模拟队列
应用场景
- 食堂排队
- js异步中的任务队列
- 计算最近请求次数leetcode993
链表
多个元素组成的链表，元素存储不连续，用next指针连在一起，js中可以用对象来模拟链表
应用场景
- leetcode237删除链表
- leetcode206反转链表
- leetcode2两数相加
- leetcode83删除排序链表中的重复元素
- leetcode141环形链表
const a={val:"a"}
const b={val:"b"}
const c={val:"c"}
const d={val:"d"}
a.next=b
b.next=c
c,next=d
//遍历
let p=a;
while(p){
console.log(a.val)
p=p.next
}
//插入
let e={val:"e"}
b.next=e
e.next=c
//删除
b.next=c