第88题 实现队列功能
请用两个栈，实现一个队列功能
功能
add/delete/length
- 数组实现队列，队列特点：先进先出
- 队列是逻辑结构，抽象模型，简单的可以用数组、链表来实现
/**
* @description 两个栈实现 - 一个队列功能
*/
class MyQueue {
stack1 = []
stack2 = []
/**
* 入队
* @param n n
*/
add(n) {
this.stack1.push(n)
}
/**
* 出队
*/
delete() {
let res
const stack1 = this.stack1
const stack2 = this.stack2
// 第一步：将 stack1 所有元素移动到 stack2 中
while(stack1.length) {
const n = stack1.pop()
if (n != null) {
stack2.push(n)
}
}
// 第二步：stack2 pop 出栈
res = stack2.pop()
// 第三步：将 stack2 所有元素“还给”stack1
while(stack2.length) {
const n = stack2.pop()
if (n != null) {
stack1.push(n)
}
}
return res || null
}
// 通过属性.length方式调用
get length() {
return this.stack1.length
}
}
// 功能测试
const q = new MyQueue()
q.add(100)
q.add(200)
q.add(300)
console.info(q.length)
console.info(q.delete())
console.info(q.length)
console.info(q.delete())
console.info(q.length)
性能分析：时间复杂度：
add O(1)、delate O(n)空间复杂度整体是O(n)
使用链表实现队列
可能追问：链表和数组，哪个实现队列更快？
- 数组是连续存储，
push很快，shift很慢 - 链表：查询慢（把链表全部遍历一遍查询）时间复杂度：
O(n)，新增和删除快（修改指针指向）时间复杂度：O(1) - 数组：查询快（根据下标）时间复杂度：
O(1)，新增和删除慢（移动元素）时间复杂度：O(n) - 结论：
链表实现队列更快
思路分析
- 使用单项链表，但要同时记录
head和tail - 要从
tail入队，从head出队，否则出队时tail不好定位 length要实时记录单独存储，不可遍历链表获取length（否则遍历时间复杂度是O(n)）
// 用链表实现队列
// 节点数据结构
interface IListNode {
value: number
next: IListNode | null
}
class MyQueue {
head = null // 头节点，从head出队
tail = null // 尾节点，从tail入队
len = 0 // 链表长度
/**
* 入队，在 tail 位置入队
* @param n number
*/
add(n) {
const newNode = {
value: n,
next: null,
}
// 处理 head，当前队列还是空的
if (this.head == null) {
this.head = newNode
}
// 处理 tail，把tail指向新的节点
const tailNode = this.tail // 当前最后一个节点
if (tailNode) {
tailNode.next = newNode // 当前最后一个节点的next指向新的节点
}
// 
// 把当前最后一个节点断开，指向新的节点
this.tail = newNode
// 记录长度
this.len++
}
/**
* 出队，在 head 位置出队
*/
delete() {
const headNode = this.head
if (headNode == null) return null
if (this.len <= 0) return null
// 取值
const value = headNode.value
// 处理 head指向下一个节点
// 
this.head = headNode.next
// 记录长度
this.len--
return value
}
get length() {
// length 要单独存储，不能遍历链表来获取（否则时间复杂度太高 O(n)）
return this.len
}
}
// 功能测试
const q = new MyQueue()
q.add(100)
q.add(200)
q.add(300)
console.info('length1', q.length)
console.log(q.delete())
console.info('length2', q.length)
console.log(q.delete())
console.info('length3', q.length)
console.log(q.delete())
console.info('length4', q.length)
console.log(q.delete())
console.info('length5', q.length)
// 性能测试
var q1 = new MyQueue()
console.time('queue with list')
for (let i = 0; i < 10 * 10000; i++) {
q1.add(i)
}
for (let i = 0; i < 10 * 10000; i++) {
q1.delete()
}
console.timeEnd('queue with list') // 12ms
// 数组模拟入队出队
var q2 = []
console.time('queue with array')
for (let i = 0; i < 10 * 10000; i++) {
q2.push(i) // 入队
}
for (let i = 0; i < 10 * 10000; i++) {
q2.shift() // 出队
}
console.timeEnd('queue with array') // 425ms
// 结论：同样的计算量，用数组和链表实现相差很多，数据量越大相差越多