Java中如何用栈来模拟队列

在数据结构中，栈是一种后进先出的线性表，而队列是一种先进先出的线性表，那么有没有可能让栈来实现队列的出队入队操作。

在栈中，当我们入栈时，会把元素压到栈底，出栈时从栈顶弹出一个元素，那么如果弹出的时候让栈顶元素再入一次栈，那么第二轮弹出的时候不就是原来栈底的元素嘛。于是思路有了，开始实现：

首先自定义MyQueue栈模拟队列类，创建两个栈，一个栈in来实现入队列及第一次入栈操作，另一个栈out实现出队列及弹入从in栈弹出的元素。

当有入队操作时，元素压入in栈中，当有出队操作时，元素从in栈弹入out栈再从out栈弹出，需要注意的是：如果当执行入队操作时，in栈和out栈都有元素，那么该操作弹入的元素一定不符合队列的先进先出原则，则需要对out栈进行判空，当out栈不为空时，就将out栈的元素全部弹入in栈，再进行入队。当out栈不为空时，可以直接进行入队。同理，出队操作也是如此。

代码如下：

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");
		
		// 遍历队列
		while(!queue.isEmpty()) {
			System.out.println(queue.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;
	}
}