Java用栈模拟队列

          首先我们需要清楚：栈，是一种后进先出的数据结构，只能我们从栈顶（top）往栈中压入（push）元素，也只能从栈顶（top）往外d出元素，所以最后进去的必须最早d出（pop）：

        而队列， 是一种先进先出的线性表结构，一般来说，它只允许在集合的前端进行删除 *** 作，而在集合的后端进行插入 *** 作：

        清楚了栈和队列的思想， 那我们如果想要定义一个底层用栈来实现的队列应该怎么做呢？

        很明显我们需要两个栈来完成，其中一个栈（我们命名为in）我们用来入队，另一个栈（命名为out）我们用来出队。具体过程为：当我们进行入队 *** 作时，实际是将元素入到栈（in），这样我们最先入队的元素就到了栈（in）底，而最后入队的元素就到了栈（in）顶，这时我们进行出队 *** 作时，如果直接从栈（in）往出拿，按照栈后进先出的思想我们从栈（in）顶拿出来的的反而是最后一个入队的元素，这并没有实现队列的先进先出；而我们想要的效果是栈（in）底的元素先出队依次直到栈（in）顶的元素最后一个出队。显然栈并不支持从栈底进行出栈 *** 作，这时我们就需要用另一个栈（out）将栈（in）里的元素先入栈，这样一来栈（in）里的栈顶元素就到了栈（out）的栈底，而栈（in）里的栈底元素就到了栈（out）的栈顶，此时我们进行出队 *** 作时，直接就可以从栈（out）的栈顶往外d出元素了。

        需要注意的一点是：我们在进行入队 *** 作时需要判断一下栈（out）是否为空，不为空时，我们需要先将栈（out）里的所有元素入到栈（in），然后再进行入队 *** 作，这是因为栈（out）不为空的话，说明此队列里还有元素，而这些元素是早已经入队的，所以需要将这些元素先入到栈（in），然后再进行其他元素的入队 *** 作，这样一来，我们在进行出队 *** 作时才能保证最先出队的是那些最先入队的。

        过程图解：

         代码实现：

import java.util.Stack;

public class MyQueue_Test {
	public static void main(String[] args) {
		MyQueue myque = new MyQueue();
		myque.offer("A1");
		myque.offer("A2");
		myque.offer("A3");
		myque.offer("A4");
		myque.offer("A5");
		System.out.println(myque.poll());
		System.out.println(myque.poll());
        //遍历队列并出队
		while(!myque.isEmpty()) {
			System.out.println(myque.poll());
		}
	}
}

class MyQueue {
	private Stack in = new Stack();
	private Stack out = new Stack();
    //入队方法
	public void offer(E e) {
		while (!out.isEmpty()) {
			in.push(out.pop());
		}

		in.push(e);
	}
    //出队方法
	public E poll() {

		while (!in.isEmpty()) {
			out.push(in.pop());
		}
		return out.pop();
	}
    //判断队列是否为空
	public boolean isEmpty() {
		return in.size() == 0 && out.size() == 0;
	}
}