栈模拟队列

众所周知，Queue队列是一个先进先出（First In First Out）的有序表，只能在队尾添加元素，在队首取出元素。

然而，Stack栈是一种后进先出（LIFO：Last In First Out）的数据结构。 只能不断地往Stack中压入（push）元素，最后进去的必须最早弹出（pop）。

因此，要想用栈来模拟队列，就必须用两个栈来进行入队和出队的操作，用一个栈做入队栈，用另一个栈作为出队栈。

当第一次入队操作的时候，将入队的元素放入入队栈，第一次出队操作的时候，将入队栈的元素出栈放入出队栈，然后遍历出队栈；当做第二次入队操作的时候，需要先检查出队栈中是否还有元素，如果有元素，需将出队栈的剩余元素先放入入队栈，然后将需要入队的元素放入入队栈，当做第二次出队操作的时候，需要先检查入队栈中是否还有元素，如果有元素，需将入队栈的剩余元素先放入出队栈，然后将需要出队的元素放入出队栈，后面的操作和第二次的操作一样，以此类推。

实现代码如下：

//栈模拟队列
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;
	}
}

测试类如下：

public class Stack05 {
	public static void main(String[] args) {
		MyQueue queue=new MyQueue();
		queue.offer("A1");
		queue.offer("A2");
		queue.offer("A3");
		queue.offer("A4");
		System.out.println(queue.poll()+"出队");
		queue.offer("A5");   //入队新元素
		System.out.println(queue.poll()+"出队");
		//遍历
		while(!queue.isEmpty()) {
			System.out.println(queue.poll());
			}
	    }
	}

运行结果如下：

A1出队
A2出队
A3
A4
A5