用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列

https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

这题做了好几遍了，但是每次做的时候都要思考一会，在此将思路记下来。

用测试驱动开发TDD的思路做题

• 队列是FIFO，栈是FILO
• 每次入队的时候只能将元素保存在栈中，即stack.push()
• 每次出队的时候只能将元素出栈，使用stack.pop()
• 现在我们有两个栈，要实现队列FIFO的功能，自然想到要将入队元素保存在第一个栈（入队栈）中，将出队元素保存在第二个栈（出队栈）中。
• 元素入队比较容易处理，将其加到入队栈即可。
• 元素出队则需要仔细思考：怎么保证每次出队的都是最先入队的元素呢？
  • 先构建一个简单的测试样例：三个元素1,2,3先后入队，入队栈：[1,2,3]。
    • 那只要依次将入队栈的元素pop到出队栈即可，出队栈变为：[3,2,1]，这样出队栈每次pop的就是最先入队的元素。
    • 根据这种情况，我们总结出的算法是：每次元素出队时，都依次将入队栈的元素pop到出队栈，再让出队栈pop。
  • 让我们构建另一个测试样例：1,2先后入队，出队一次，3入队，出队一次。
    • 使用上面总结出的算法，我们会发现出队元素是1,3，而正确结果应该是1,2。错误的原因是3与2在出队栈中的顺序调转了，在3入队+出队一次后，3居然成为了出队栈的栈顶元素。
    • 认真思考一下，出队栈的元素顺序在一轮依次将入队栈的元素pop到出队栈中才能得到保护，如果有多轮依次将入队栈的元素pop到出队栈，那么出队栈的元素顺序会被破坏。
    • 因此，只有在出队栈为空时，才进行依次将入队栈的元素pop到出队栈的操作。若出队栈不为空，直接让出队栈pop即可。

class CQueue {
public:
    std::stack<int> a,b;
    CQueue() {
    }
    
    void appendTail(int value) {
        a.push(value);
    }
    
    int deleteHead() { 
        // 若出队栈不为空，直接pop
        if (!b.empty()) {
            int head = b.top();
            b.pop();
            return head;
        }
        // 出队栈为空，依次将入队栈的元素pop到出队栈
        while (!a.empty()) {
            b.push(a.top());
            a.pop();
        }
        if (!b.empty()) {
            int head = b.top();
            b.pop();
            return head;
        }
        return -1;
    }
};