栈模拟队列

要想使用栈模拟出一个队列，我们首先必须要了解的是：队列和栈的数据结构；
队列：Queue是一种先进先出（FIFO：First In First Out）的数据结构。一般来说，它只允许在队首进行删除操作，队尾进行插入操作。

栈：Stack是一种后进先出（LIFO：Last In First Out）的数据结构。

Queue与Stack都为线性表结构
Stack的后进先出与Queue的先进先出正好相反
所以如果要用栈模拟队列，就必须要模拟队列先进先出的特点
在这里我们可以采用定义两个栈（一个入队栈、一个出队栈）的方式来模拟队列

模拟结构图如下：

实现代码如下：

class MyQueue{
	Stack in=new Stack();//入队栈
	Stack out=new Stack();//出队栈
	//入队操作
	public void offer(E e) {
		while(!out.empty()) {//入队时必须保证出队栈为空
			
			in.push(out.pop());//将出队栈弹出的元素压入 入队栈
		}
		in.push(e);//将添加元素压人入队栈
	}
	//出队操作
	public  E poll() {
		while(!in.empty()) {//同理出队时也必须保证入队栈为空
			out.push(in.pop());//将入队栈弹出的元素压入 出队栈
		}
		 return out.pop();//返回出队栈弹出的元素
		 
	}
	
	public boolean empty() {
		return in.empty()&&out.empty();
//		return in.size()==0&&out.size()==0;
	}
	
}

 这样，就用栈实现了队列，核心思想就是利用两个栈（入队栈与出队栈）互相配合。

//测试代码如下

public class test {
	public static void main(String[] args) {
		MyQueue que=new MyQueue<>();//先进先出
		que.offer("A1");//队首
		que.offer("A2");
		que.offer("A3");
		que.offer("A4");
		System.out.println(que.poll()+"出队");
		que.offer("A5");
		System.out.println(que.poll()+"出队");

		System.out.println("==============================");
		while(!que.empty()) {
			System.out.println(que.poll());
		}
	}
}

//测试结果如下：

A1出队
A2出队
==============================
A3
A4
A5