用两个栈实现一个队列

题目

请用两个栈，来实现队列的功能，实现功能 add delete length 。

队列 Queue

栈，先进后出

队列，先进先出，API 包括

• add
• delete
• length

常见的“消息队列”就是队列的一种应用场景

• A 系统向 B 系统持续发送海量的消息
• A 系统先把一条一条消息放在一个 queue
• B 系统再从 queue 中逐条消费（按顺序，先进先出）

逻辑结构和物理结构

队列和栈一样，是一种逻辑结构。它可以用数组、链表等实现。
思考：用数组实现队列，性能会怎样 —— add 怎样？delete 怎样？

复杂场景下（如海量数据，内存不够用）需要单独设计。

题目分析

可画图分析

• 队列 add
  • 往 stack1 push 元素
• 队列 delete
  • 将 stack1 所有元素 pop 出来，push 到 stack2
  • 将 stack2 执行一次 pop
  • 再将 stack2 所有元素 pop 出来，push 进 stack1

答案

参考 two-stacks-one-queue.ts

划重点

• 队列
• 画图，帮助梳理解题思路