数据结构：栈和队列的相互实现

栈实现队列

思路

栈的特点是先进后出，队列的特点是先进先出，这就意味着我们无法通过一个栈来实现队列，那两个栈呢？

事实上，两个栈是可以实现队列的，stack1 和 stack2 思路如下：

**入队列：**先把所有元素都放到 stack1 中。

**出队列：**判断 stack2 是否为空

• 为空则把 stack1 中元素按照出栈顺序放到 stack2 中，同时返回 stack2 栈顶元素。
• 不为空则直接返回 stack2 栈顶元素。

定义基础变量

class MyQueue { 
    public ArrayDeque<Integer> stack1; 
    public ArrayDeque<Integer> stack2; 
    
    public MyQueue() { 
        stack1 = new ArrayDeque<>(); 
        stack2 = new ArrayDeque<>(); 
    } 
}

入队列

offer 方法

根据上面思路，新元素放在 stack1 中。

public void offer(int x) { 
    stack1.push(x); 
} 

出队列

poll 方法

在实现具体内容之前，我们要先判断两个栈是否都为空。

这里需要写个 empty 方法，判断条件是：两个栈是否为空。

public boolean empty() { 
    return stack1.isEmpty() && stack2.isEmpty(); 
}

根据上面的思路，来完成出队列。

出队列：判断 stack2 是否为空

• 为空则把 stack1 中元素按照出栈顺序放到 stack2 中，同时返回 stack2 栈顶元素
• 不为空则直接返回 stack2 栈顶元素。

public int poll() { 
    if(empty()){ 
        return -1; 
    } 
    if(stack2.isEmpty()){ 
        (!stack1.isEmpty()){ 
            
            stack2.push(stack1.pop()); 
        } 
    } 
     stack2.pop(); 
}