feat: 232 重写

lucifer · lucifer · commit c0029cff6a18 · 2021-03-05T11:18:12.000+08:00
diff --git a/problems/232.implement-queue-using-stacks.md b/problems/232.implement-queue-using-stacks.md
@@ -11,78 +11,66 @@ push(x) -- 将一个元素放入队列的尾部。
 pop() -- 从队列首部移除元素。
 peek() -- 返回队列首部的元素。
 empty() -- 返回队列是否为空。
- 
-
 示例:
 
 MyQueue queue = new MyQueue();
 
 queue.push(1);
 queue.push(2);
-queue.peek();  // 返回 1
-queue.pop();   // 返回 1
+queue.peek(); // 返回 1
+queue.pop(); // 返回 1
 queue.empty(); // 返回 false
- 
-
 说明:
 
-你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
+你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
-假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
-
+假设所有操作都是有效的、 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
 ```
 
 ## 前置知识
 
-- [栈](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md)
-
-## 公司
-
-- 阿里
-- 腾讯
-- 百度
-- 字节
-- bloomberg
-- microsoft
+- 栈
+- 队列
 
 ## 思路
 
-这道题目是让我们用栈来模拟实现队列。 我们知道栈和队列都是一种受限的数据结构。
-栈的特点是只能在一端进行所有操作，队列的特点是只能在一端入队，另一端出队。
+题目要求用栈的原生操作来实现队列，也就是说需要用到 pop 和 push
+但是我们知道 pop 和 push 都是在栈顶的操作，而队列的 enque 和 deque 则是在队列的两端的操作，这么一看一个 stack 好像不太能完成。
+
+我们来分析一下过程。
 
-在这里我们可以借助另外一个栈，也就是说用两个栈来实现队列的效果。这种做法的时间复杂度和空间复杂度都是 O(n)。
+假如向栈中分别 push 四个数字 `1, 2, 3, 4`，那么此时栈的情况应该是：
 
-由于栈只能操作一端，因此我们 peek 或者 pop 的时候也只去操作顶部元素，要达到目的
-我们需要在 push 的时候将队头的元素放到栈顶即可。
+![](https://pic.leetcode-cn.com/1614914197-xJWIpb-0081Kckwly1glwx3qnz9oj30760dyq39.jpg)
 
-因此我们只需要在 push 的时候，用一下辅助栈即可。
-具体做法是先将栈清空并依次放到另一个辅助栈中，辅助栈中的元素再次放回栈中，最后将新的元素 push 进去即可。
+如果此时按照题目要求 pop 或者 peek 的话， 应该是返回 1 才对，而 1 在栈底我们无法直接操作。如果想要返回 1，我们首先要将 2，3，4 分别出栈才行。
 
-比如我们现在栈中已经是 1，2，3，4 了。 我们现在要 push 一个 5.
+![](https://pic.leetcode-cn.com/1614914197-RzHCxu-0081Kckwly1glwx3yd0blj31yi0joq5p.jpg)
 
-push 之前是这样的：
+然而，如果我们这么做，1 虽然是正常返回了，但是 2，3，4 不就永远消失了么？ 一种简答方法就是，将 2，3，4 **存** 起来。而题目又说了，只能使用栈这种数据结构，那么我们考虑使用一个额外的栈来存放弹出的 2，3，4。
 
-![232.implement-queue-using-stacks.drawio](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu87p5vuj30c2067dg5.jpg)
+![](https://pic.leetcode-cn.com/1614914197-ifsUDV-0081Kckwly1glwx43ax3xj31jm0u042t.jpg)
+（pop 出来不扔掉，而是存起来）
 
-然后我们将栈中的元素转移到辅助栈：
+整个过程类似这样：
 
-![232.implement-queue-using-stacks.drawio](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu88r2h6j308p07c74k.jpg)
+![](https://pic.leetcode-cn.com/1614914197-mcKlvh-0081Kckwly1glwx4cnke3j30pg0j0dgx.jpg)
 
-最后将新的元素添加到栈顶。
+比如，这个时候，我们想 push 一个 5，那么大概就是这样的：
 
-![232.implement-queue-using-stacks.drawio](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu898h4rj309t07074l.jpg)
+![](https://pic.leetcode-cn.com/1614914197-CvfelO-007S8ZIlly1gfhu6exrzyj327g0u0gu9.jpg)
 
-整个过程是这样的：
+然而这一过程，我们也可以发生在 push 阶段。
 
-![232.implement-queue-using-stacks.drawio](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu89mjsjj30jg0czaba.jpg)
+总之，就是我们需要在 push 或者 pop 的时候，将数组在两个栈之间倒腾一次。
 
-## 关键点解析
+## 关键点
 
 - 在 push 的时候利用辅助栈(双栈)
 
 ## 代码
 
-- 语言支持：JS, Python, Java, Go
+- 语言支持：JS, Python, Java
 
 Javascript Code:
 
@@ -253,57 +241,10 @@ class MyQueue {
  */
 ```
 
-Go Code:
-
-```go
-type MyQueue struct {
-    StackPush []int
-    StackPop  []int
-}
-
-/** Initialize your data structure here. */
-func Constructor() MyQueue {
-    return MyQueue{}
-}
-
-/** Push element x to the back of queue. */
-func (this *MyQueue) Push(x int) {
-    this.StackPush = append(this.StackPush, x)
-}
-
-/** Removes the element from in front of queue and returns that element. */
-func (this *MyQueue) Pop() int {
-    this.Transfer()
-    var x int
-    x, this.StackPop = this.StackPop[0], this.StackPop[1:]
-    return x
-}
-
-/** Get the front element. */
-func (this *MyQueue) Peek() int {
-    this.Transfer()
-    return this.StackPop[0]
-}
-
-/** Returns whether the queue is empty. */
-func (this *MyQueue) Empty() bool {
-    return len(this.StackPop) == 0 && len(this.StackPush) == 0
-}
-
-// StackPush 不为空的时候, 转移到 StackPoP 中
-func (this *MyQueue) Transfer() {
-    var x int
-    for len(this.StackPush)>0 {
-        x, this.StackPush = this.StackPush[0], this.StackPush[1:] // pop
-        this.StackPop = append(this.StackPop, x) // push
-    }
-}
-```
-
 **复杂度分析**
 
-- 时间复杂度：$O(1)$
-- 空间复杂度：$O(1)$
+- 时间复杂度：<code>O(N)</code>，其中 N 为 栈中元素个数，因为每次我们都要倒腾一次。
+- 空间复杂度：<code>O(N)</code>，其中 N 为 栈中元素个数，多使用了一个辅助栈，这个辅助栈的大小和原栈的大小一样。
 
 ## 扩展
 
@@ -322,8 +263,6 @@ func (this *MyQueue) Transfer() {
 
 - [further reading](https://stackoverflow.com/questions/2050120/why-use-two-stacks-to-make-a-queue/2050402#2050402)
 
-更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
-
-关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。
 
-![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
+大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解
