【leetcode】232. 用栈实现队列（Java）

【leetcode】232. 用栈实现队列（Java） 题目描述

题目链接: 232. 用栈实现队列.

题解

使用双栈模拟队列

• 1 2 3 4 5顺序入模拟队列，想要按照1 2 3 4 5的顺序出去，那么栈之中存储的顺序就要是【5,4,3,2,1->(栈顶）。所以每当push进来一个数的时候，就利用辅助栈，把它压入另一个栈的栈底
• 当执行push *** 作时,用d2作为辅助，把新push的进来的数压入d1栈底;
• 当执行pop()和peek() *** 作时，直接返回d1的栈顶就好;

class MyQueue {
    Deque d1;
    Deque d2;

    public MyQueue() {  
        d1 = new linkedList<>();
        d2 = new linkedList<>();
    }
    
    public void push(int x) {
        while (!d1.isEmpty()){
            d2.addLast(d1.pollLast());
        }
        d1.addLast(x);
        while (!d2.isEmpty()){
            d1.addLast(d2.pollLast());
        }
    }
    
    public int pop() {
        return d1.pollLast();
    }
    
    public int peek() {
        return d1.peekLast();
    }
    
    public boolean empty() {
        return d1.isEmpty();
    }
}