4、两个栈实现一个队列

两个栈实现一个队列

• 请用两个栈，实现一个队列
• 功能 add delete length

队列

• 先进先出
• API ： add delete length

逻辑结构 VS 物理结构

• 队列是逻辑结构，抽象模型
• 简单的，可以使用数组、链表实现
• 复杂的队列服务，需单独设计

思路

• 入队直接使用push填入栈1
• 出队：先将栈1的元素pop到栈2，然后栈2使用pop，最后栈2在pop到栈1

示例：入队===> ABCD === 【DCBA】

——
D
C
B
A
——
1
2
3
4
5
6

此时A在栈底，但是队列是先进先出，要删除A，需要将A放到栈顶。

出队：1、栈1【DCBA】=pop=>栈2【ABCD】

——
A
B
C
D
——
1
2
3
4
5
6

此时栈2中，A是在栈顶，可以删除A，满足队列先进先出的规则。

2、栈2【ABCD】=pop(A)=> 【BCD】

——
B
C
D
——
1
2
3
4
5

此时已经删除完了A，但是后续继续增加新的元素E或F，应该在D的后面，

3、栈2【BCD】=pop=> 栈1【DCB】

——
D
C
B
——
1
2
3
4
5

所以第三步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
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

功能测试

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
1
2
3
4
5
6
7
8

满足队列先进先出的规则

单元测试

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)
    })
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

性能分析

• 时间复杂度：add==>O(1); delete ==> O(n)
• 空间复杂度，整体是O(n)

虽然在delete中有两次循环，但不是嵌套关系，所以它是时间和空间复杂度都是O(n);