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

题目地址
题目太怪了！！！

stack是后进先出，队列是先进先出。

对于一个stack，如果要弹出“队首”元素，需要先将整个stack弹出，才能在最终弹出“队首”。那么需要一个结构来保存被弹出的元素，那么正好第二个stack派上用场。第一个stack弹出的元素，按顺序push进第二个stack，第二个stack按顺序pop就是队列了。对于再加入的元素，先push进第一个stack即可。

下面用（）模拟stack，可以清晰的观察整个过程。左边为首，右边为尾。
（1，2，3） - （）
（1，2） （3）
（1）（3，2）
（）（3，2，1）

Stack版

class CQueue {

     Stack s1 = new Stack();
     Stack s2 = new Stack();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        s1.push(value);
    }
    
    public int deleteHead() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
           
        }
        int r = -1;
        if(!s2.isEmpty()){
            r = s2.pop();
        }
         return r;
    }
}

执行用时: 44 ms
内存消耗: 46.5 MB

Deque版

class CQueue {

     Deque s1 = new linkedList();;
    Deque s2 = new linkedList();;
    
    public CQueue() {
    
    }

    public void appendTail(int value) {
        s1.push(value);
    }
    
    public int deleteHead() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
           
        }
        int r = -1;
        if(!s2.isEmpty()){
            r = s2.pop();
        }
         return r;
    }
}

执行用时: 42 ms
内存消耗: 47.2 MB

下面稍微聊聊两者的区别。

1. Stack

Stack是Vector的一个子类，它实现了一个标准的后进先出的栈。
单可以index访问。
常见操作如下

s.push();
s.peek();
s.pop()

但他是基于Vector实现的，而Vector是可以按index进行访问的，这导致Stack也是可以的。虽然看起来不是大问题，但违背了单一职责（ single responsibility）的设计原理。Java文档中也建议使用Deque来实现。

2. Dquen

Deque 是一个接口，是一个双向队列，既可以实现为队列，也可以实现为栈。常用的实现类包括ArrayDeuqe或者linkedList，栈常用linkedList,链表中对首尾的访问更快一些。

3. 一个例子

Stack stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3


Deque deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1

http://baddotrobot.com/blog/2013/01/10/stack-vs-deque/
https://stackoverflow.com/questions/12524826/why-should-i-use-deque-over-stack
https://www.baifachuan.com/posts/1ed50096.html