Double queue implementation stack?Dual stack implementation queue?

双队列实现栈

A single queue cannot implement a stack,Double queue is ok,如下分析（例如出栈）

 

 

注意：

• Which queue is not empty put the element into which queue
• 若两个都为空,You can put it in any queue 

如下代码：

class MyStack {
    public Queue<Integer> q1;
    public Queue<Integer> q2;
    public int usedSize;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    //压栈
    public void push(int x) {
        //哪个队列不为空,Put it in there,Leave it all emptyq1
        if(!q1.isEmpty()){
            q1.offer(x);
        }
        else if(!q2.isEmpty()){
            q2.offer(x);
        }
        else{
            q1.offer(x);
        }
        usedSize++;
    }
    //出栈
    public int pop() {
        //哪个队列不为空,Just take the element from there and put it in another queue
        if(empty()){
            return -1;
        }
        if(!q1.isEmpty()){
            //转移usedSize - 1个元素到另一个队列
            //for(int i = 0; i < usedSize - 1; i++)//不能这样写,usedSizeIt will continue to decrease as the stack is popped
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q2.offer(q1.poll());
            }
            usedSize--;
            return q1.poll();
        }
        else{
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q1.offer(q2.poll());
            }
            usedSize--;
            return q2.poll();
        }
    }
    
    public int top() {
        //哪个队列不为空,Just take the element from there and put it in another queue
        if(empty()){
            return -1;
        }
        int tmp = 0;
        if(!q1.isEmpty()){
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q2.offer(q1.poll());
            }
            tmp = q1.peek();
            q2.offer(q1.poll());
        }
        else{
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q1.offer(q2.poll());
            }
            tmp = q2.peek();
            q1.offer(q2.poll());
        }
        return tmp;
    }
    //判空
    public boolean empty() {
        return usedSize == 0;
    }
}

---

双栈实现队列

A single stack cannot implement a queue,Dual stack is possible,如下分析（例如出队）

 

 

 

 注意：

• Be sure to check before leaving the teams2中是否有元素,If there is, it can pop up directly,If not agains1全部压入s2中
• The same goes for checking the head of the queue(peek)

代码如下：

class MyQueue {
    public Stack<Integer> s1;//入栈
    public Stack<Integer> s2;//出栈
    public MyQueue() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    //进队
    public void push(int x) {
        s1.push(x);
    }
    //出队
    public int pop() {
        if(empty()) {
            return -1;
        }
        //s2like a cistern,Once out of the queue,full pressures1
        //前提一定要是s2为空！若不为空,再压入s2,The order is different！
        if(s2.empty()){
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        //如果s2里有元素,pop up directly
        return s2.pop();
    }
    public int peek() {
        if(empty()) {
            return -1;
        }
        //s2like a cistern,Once out of the queue,full pressures1
        //前提一定要是s2为空！若不为空,再压入s2,The order is different！
        if(s2.empty()){
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.peek();
        }
        //如果s2里有元素,pop up directly
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

---