题目

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

队列

        用数组可以实现队列，数组和队列的区别是：队列是逻辑结构是一个抽象模型，简单地可以用数组、链表实现，所以数组和链表是一个物理结构，队列是一个逻辑结构。数组和链表可以实现队列，但是复杂的队列服务则需要单独设计。如常见的消息队列。

队列的特性：先进先出

API： add delete length

// 数组的队列形式
const queue = []queue.push(100) // 入队
queue.push(200)const n =  queue.shift() // 出队

实现思路

 如现有一个队列，入队顺序是 A B C，出队顺序也是 A B C，用两个栈 stack1、stack2 实现入队、出队。由于栈是先进后出，所以需要在A B C分别入栈 stack1 后，再将 stack1 每个元素pop 出栈且入栈 stack2 ，接着将 stack2 进行pop 操作，此时 A 出栈。最后将 stack2 内剩余元素压回到 stack1，方便后续stack1 的入栈操作。所以当队列里要入队一个元素时只需要一步，而要出队一个元素时则需要在两个 stack 之间进行腾挪。

 

/**
* 两个栈一个队列
*/
export class MyQueue {private stack1: number[] = []private stack2: number[] = []// 入队add(n: number) {this.stack1.push(n)}// 出队delete(n: number) {let resconst stack1 = this.stack1const stack2 = this.stack2// 将 stack1 所有元素移动到 stack2 中while(stack1.length) {const n = stack1.pop()if(n != null) {stack2.push(n)}}// stack2 popres = stack2.pop()// 将 stack2 中的元素还给 stack1while(stack2.length) {const n = stack2.pop()if(n != null) {stack1.push(n)}}return res || null}// 入队get length(): number {return this.stack1.length}
}

单元测试 

/**
* 两个栈，一个队列
*/
describe('两个栈，一个队列', () => {it('add and length', () => {const q = new MyQueue()expect(q.length).toBe(0)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.delete()).toBe(100)expect(q.length).toBe(2)expect(q.delete()).toBe(200)expect(q.length).toBe(1)})
})