怎么用两个栈来实现一个队列（两个队列实现一个栈）

怎么用两个栈来实现一个队列（两个队列实现一个栈）public class StackMakeUpByQueue { public static void main(String[] args) throws Exception { Stack<Integer> stack = new Stack<>(); for (int i = 0;i < 10; i ) { stack.push(i 1); } System.out.println(stack.pop()); // 删除 10 stack.push(11); // push 11 stack.push(12); // 删除12 System.out.println(stack.pop()); while (!stack.isEmpty()) { System.out.print(stack.pop() " "); }

本文参考书籍 《剑指offer》 作者何海涛

题目：用两个队列实现一个栈，请实现它的两个函数push，pop，分别从栈尾部添加元素，和从栈尾部移除元素。（和上一篇是相关题目）

首先我们来回顾下栈和队列的特性，栈的特性是先进后出，即它只能通过一个口出入，如下图，

队列的特性，先进先出，从队首出队，从对尾入队，如下图

解题思路

每次需要出栈的时候，就将队列中的值移动到另外一个队列里面，留最后一个，出栈。

即，每做一次出栈操作，就要把队列的值从一个队列转移到另外一个队列面，出栈后的被转移队列保持为空。

那么入栈的数值放在那里呢？放在栈尾，有数值的那个队列里面，如果两个为空，哪个都可以。

代码

import java.util.Queue; import java.util.concurrent.LinkedBlockingQueue; class Stack<T> { Queue<T> queue1 = new LinkedBlockingQueue(); Queue<T> queue2 = new LinkedBlockingQueue(); public T pop() throws Exception { if (!queue1.isEmpty() && queue2.isEmpty()) { while (queue1.size() > 1) { queue2.add(queue1.remove()); } return queue1.remove(); } if (queue1.isEmpty() && !queue2.isEmpty()) { while (queue2.size() > 1) { queue1.add( queue2.remove()); } return queue2.remove(); } throw new Exception("元素为空"); } public void push(T e) { if (!queue2.isEmpty()) { queue2.add(e); } else { queue1.add(e); } } public boolean isEmpty() { return queue1.isEmpty() && queue2.isEmpty(); } }

测试代码

public class StackMakeUpByQueue { public static void main(String[] args) throws Exception { Stack<Integer> stack = new Stack<>(); for (int i = 0;i < 10; i ) { stack.push(i 1); } System.out.println(stack.pop()); // 删除 10 stack.push(11); // push 11 stack.push(12); // 删除12 System.out.println(stack.pop()); while (!stack.isEmpty()) { System.out.print(stack.pop() " "); } } }