3 用两个栈实现队列
题目描述
用两个栈来实现一个队列,完成队列的push和pop操作。队列中的元素为int类型。
思路
由于栈具有反转的功能,将两个栈分为push栈(stack1)和pop栈(stack2)。将操作的节点分成不同批次。stack1用来收集下一批待出队的节点,可直接加入。stack2用来反转数据,从而可以实现出队功能。对于stack2来说,如果stack2中没有数据,则将此时stack1中的数据当成“一批”,反转压入pstack2;如果stack2中还有数据,说明“这一批”可直接出队的数据还没用完,不必从push栈中加入新的一批数据。
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { // 用于形成新一批的数据 stack1.push(node); } public int pop() { // 如果stack1、stack2都为空,说明队列中没有数据 if(stack1.empty() && stack2.empty()){ throw new RuntimeException("Queue is empty!"); } // 如果stack2为空,说明这一批出队数据用完了,从stack1中拿来新一批数据,再出队 if(stack2.empty()){ // 循环遍历,将stack1中的所有数据取出,反转压入stack2 while(!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } }