添加 用栈实现队列 和 用队列实现栈 c++版本代码

ziggy7 · labuladong · commit ed93c697c2fd · 2020-06-24T13:12:09.000+08:00
解法思路与原作者相同
diff --git a/数据结构系列/队列实现栈栈实现队列.md b/数据结构系列/队列实现栈栈实现队列.md
@@ -203,8 +203,104 @@ public boolean empty() {
 ![labuladong](../pictures/labuladong.jpg)
 
 
+[Xingsheng Qi](https://github.com/ziggy7) 提供 用栈实现队列 C++解法代码：
+
+```CPP
+class MyQueue {
+private:
+    stack<int> s1; 
+    stack<int> s2;  
+    
+public:
+    MyQueue() {
+    }
+    
+    /** 添加元素到队尾 */
+    void push(int x) {
+        s1.push(x);
+    }
+    
+    /** 删除队头的元素并返回 */
+    int pop() {
+        // 先调用 peek 保证 s2 非空
+        peek();
+        //保存 s2 的栈顶元素用于返回
+        int tmp = s2.top();
+        s2.pop();
+        return tmp;
+    }
+    
+    /** 返回队头元素 */
+    int peek() {
+        if (s2.empty())
+        // 把 s1 元素压入 s2
+            while (!s1.empty()){
+                s2.push(s1.top());
+                s1.pop();
+            }
+        return s2.top();
+    }
+    
+    /** 判断队列是否为空 */
+    bool empty() {
+        return s1.empty()&& s2.empty();
+    }
+};
+```
+
+[Xingsheng Qi](https://github.com/ziggy7) 提供 用队列实现栈 C++解法代码：
+
+```CPP
+class MyStack {
+private:
+    queue<int>q;
+    int top_elem = 0;
+
+public:
+    MyStack() {
+
+    }
+    
+    /** 添加元素到栈顶 */
+    void push(int x) {
+        // x 是队列的队尾，是栈的栈顶
+        q.push(x);
+        top_elem = x;
+    }
+    
+    /** 删除栈顶的元素并返回 */
+    int pop() {
+        int size = q.size();
+        // 留下队尾 2 个元素
+        while (size > 2) {
+            q.push(q.front());
+            q.pop();
+            size--;
+        }
+        // 记录新的队尾元素
+        top_elem = q.front();
+        q.push(q.front());
+        q.pop();
+        // 删除之前的队尾元素
+        int tmp = q.front();
+        q.pop();
+        return tmp;
+    }
+    
+    /** 返回栈顶元素 */
+    int top() {
+        return top_elem;
+    }
+    
+    /** 判断栈是否为空 */
+    bool empty() {
+        return q.empty();
+    }
+};
+```
+
 [上一篇：递归反转链表的一部分](../数据结构系列/递归反转链表的一部分.md)
 
 [下一篇：算法学习之路](../算法思维系列/算法学习之路.md)
 
-[目录](../README.md#目录)
+[目录](../README.md#目录)
