栈模拟队列

首先清楚栈和队列各自的特点

1.

队列（queue）：①集合 ②遵循先进先出（FIFO:first in first out ），后进后出的原则。 ③只能队头出队，队尾入队

栈（stack）：①类②是一种后进先出（LIFO：last in first out）的数据结构。③只能不断往栈（stack）里压入（push）元素，最后进去的最早弹出（pop）

2.思路

栈要实现队列的功能，就要实现元素先进先出的功能，而栈为后进先出，所以需要借助两个栈完成："入队栈（in）"让最后进去的元素在栈顶先弹出之后在"出队栈（out）"中被最先压入栈，这样最先进去的元素就会在"出队栈"的栈顶，从而实现了先进去的元素也最先弹出的功能

3.实现

先定义MyQueue类，用这两个栈来模拟queue的offer()方法入队和poll()方法出队。

注意：在实现offer()方法入队时要保证出队栈为空，poll()方法出队时要保证入队栈为空。

代码实现：

package com.apesource.demo07;

import java.util.Stack;

public class Test01 {
	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");
		
		
	}

}
//“栈”模拟“队列”
//指的泛型确保集合类未知的集合类型(eg:上面的String)
class MyQueue{
	
	private Stack in = new Stack();//入队栈
	private Stack out = new Stack();//出队栈
	
	
	//入队
	//方法里还不能确定类型，所以参数是E e
	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();
	}
}