两个栈实现一个队列

题目如下

• 请用两个栈实现一个队列

思路如下

1. 将数据A、B、C入栈到stackA中
2. 将stackA中的数据出栈（C-B-A），入栈到stackB中，此时stackB中的栈顶到栈底的数据依次为 A、B、C，此时可以通过stackB做出栈，即输出A，达到队列的效果
3. 在stackB出栈后，需要将stackB栈中剩余的数据重新入栈到stackA中，以保持数据原来的顺序不变

export class TwoStacksToQueue {
  private stack1: number[] = []
  private stack2: number[] = []
  // 入队列 时间复杂度 O(1)
  add(n:number) {
    this.stack1.push(n)
  }
  
  // 出队列 时间复杂度O(n)
  delete() :number | null {
    let res
    
    const stack1 = this.stack1
    const stack2 = this.stack2
    
    // 1.将stack1的所有元素移动到stack2中
    while(stack1.length){
      const n = stack1.pop()
      if(n != null){
        stack2.push(n)
      }
    }
    
    // 2.将stack2中的数据进行pop，也就是出队列
    res = stack2.pop()
    
    // 3.将stack2中的所有元素返还给stack1
    while(stack2.length){
      const n = stack2.pop()
      if(n !=null){
        stack1.push(n)
      }
    }
    
    return res || null
  }
  
  get length():number {
    return this.stack1.length
  }
}

单元测试

/**
 * @description 两个栈，一个队列 test
 * @author sola-grj
 */

import { TwoStacksToQueue } from './two-stacks-one-queue'

describe('两个栈，一个队列', () => {
    it('add and length', () => {
        const q = new TwoStacksToQueue()
        expect(q.length).toBe(0)

        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.length).toBe(3)
    })

    it('delete', () => {
        const q = new TwoStacksToQueue()
        expect(q.delete()).toBeNull()

        q.add(100)
        q.add(200)
        q.add(300)
        expect(q.delete()).toBe(100)
        expect(q.length).toBe(2)
        expect(q.delete()).toBe(200)
        expect(q.length).toBe(1)
    })
})