- 请用两个栈，实现一个队列
- 功能 add delete length
队列
- 先进先出
- API ： add delete length
逻辑结构 VS 物理结构
- 队列是逻辑结构，抽象模型
- 简单的，可以使用数组、链表实现
- 复杂的队列服务，需单独设计
思路
- 入队直接使用push填入栈1
- 出队：先将栈1的元素pop到栈2，然后栈2使用pop，最后栈2在pop到栈1
示例：入队===> ABCD === 【DCBA】
——
D
C
B
A
——此时A在栈底，但是队列是先进先出，要删除A，需要将A放到栈顶。
出队：1、栈1【DCBA】===pop===>栈2【ABCD】
——
A
B
C
D
——此时栈2中，A是在栈顶，可以删除A，满足队列先进先出的规则。
2、栈2【ABCD】===pop(A)===> 【BCD】
——
B
C
D
——此时已经删除完了A，但是后续继续增加新的元素E或F，应该在D的后面，
3、栈2【BCD】===pop===> 栈1【DCB】
——
D
C
B
——所以第三步D在栈顶，新增新的元素E或F，就在D的后面，满足的队列的先进先出规则。
代码实现
class MyQueue {
private stack1: number[] = []
private stack2:number[] = []
add(num:number) {
this.stack1.push(num)
}
delete():number | null {
let res;
const stack1 = this.stack1
const stack2 = this.stack2
// 将stck1 所有元素移动到stack2中
while(stack1.length){
const n:number = stack1.pop() as number
if (n != null){
stack2.push(n)
}
}
// stack2 pop
res = stack2.pop()
// 将 stack2 所有元素“还给”stack1
while(stack2.length){
const n = stack2.pop() as number
if (n != null) {
stack1.push(n)
}
}
return res || null
}
get length():number {
return this.stack1.length
}
}功能测试
const q = new MyQueue()
q.add(100)
q.add(200)
q.add(300)
console.log(q.length) // 3
console.log(q.delete()) // 100
console.log(q.length) // 2满足队列先进先出的规则
单元测试
describe('两个栈，一个队列',() => {
it('add and length', () => {
const q = new MyQueue()
q.add(100)
q.add(200)
q.add(300)
expect(q.length).toBe(3)
})
it('delete', () => {
const q = new MyQueue()
expect(q.delete()).toBeNull()
q.add(100)
q.add(200)
q.add(300)
expect(q.length).toBe(3)
expect(q.delete()).toBe(100)
expect(q.length).toBe(2)
expect(q.delete()).toBe(200)
expect(q.length).toBe(1)
expect(q.delete()).toBe(300)
expect(q.length).toBe(0)
})
})性能分析
- 时间复杂度：add==>O(1); delete ==> O(n)
- 空间复杂度，整体是O(n)
虽然在delete中有两次循环，但不是嵌套关系，所以它是时间和空间复杂度都是O(n);
