题目
- 用两个栈，实现一个队列
- 功能 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 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
}
// 入队
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)
})
})
