在Java中，队列实现栈 & 栈实现队列基本思路

队列(Queue)和栈(Stack)作为集合中经常使用到的两种集合，它们各自有各自的特点。队列继承自它的上级接口Collection。作为线性表结构，它遵循先进先出、后进后出(FIFO)的基本原则。它只允许在集合的首部进行出队 *** 作，而在集合的尾部进行入栈 *** 作。栈是基于Vector实现的后进先出(LIFO)的栈。它只允许在栈的顶部进行入栈和出栈 *** 作。

队列(Queue)的基本 *** 作是：

①：把元素添加到队列末尾

②：从队列头部取出元素

根据这两个 *** 作我们可以通过两个栈来模拟队列的 *** 作

(PS:GIF来源于互联网)

e.g 以1、2、3数据为例

具体思路：首先将1、2、3全部压入栈一，然后根据栈的后进先出特点，将3、2、1以此顺序出栈压入栈二，此时栈二中元素顺序为1、2、3。此时在通过栈二出栈元素就形成了队列出栈的顺序FIFO。

具体代码如下：

package cn.com.XYNU;

import java.util.Stack;

public class Demo01 {
	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());
		System.out.println(queue);
		
//		while(!queue.isEmpty()) {
//			System.out.println(queue.poll());
//		}
		
	}
}

class MyQueue{
	
	private Stack stack1 = new Stack(); 
	private Stack stack2 = new Stack();
	// 入队
	public void offer(E e) {
		while(!stack2.isEmpty()) {
			stack1.push(stack2.pop());
		}
		stack1.push(e);
	}
	
	// 出队
	public E poll() {
		while(!stack1.isEmpty()) {
			stack2.push(stack1.pop());
		}
		return stack2.pop();
	}
	
	// 判断队列是否为空
	public boolean isEmpty() {
		return stack1.isEmpty() && stack2.isEmpty();
	}
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		while(!stack2.isEmpty()) {
			stack1.push(stack2.pop());
		}
		
		return stack1.toString();
		
	}
}

栈(Stack)的基本 *** 作是：

①：将元素压入栈(push(E))

②：把栈顶的元素"d出"(pop(E))

同样的，根据这两个 *** 作我们可以通过两个队列来模拟栈的 *** 作

具体思路：首先将首元素插入其中一个空队列中，将剩余元素插入另一个空队列中，在进行出栈 *** 作时，要出不为空的栈，如果队列一为为空队列，将最后一个元素留在队列一中，其余元素插入队列二中，此时出队列一中的最后一个元素，也就形成了栈的后进先出原则了。接着判断队列二是否为非空队列，重复上一步 *** 作，继续出栈。

具体代码如下：

package cn.com.XYNU;

import java.util.LinkedList;
import java.util.Queue;

public class Demo {

	public static void main(String[] args) {
		// 通过队列实现栈
		MyStack stack = new MyStack();
		stack.push("A1");
		stack.push("A2");
		stack.push("A3");
		System.out.println(stack.isEmpty());// 判断栈是否为空
		
		// 逐个元素出栈
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		
		// 再向栈中压入一个元素，再出栈
		stack.push("A4");
		System.out.println(stack.pop());
		
		// 将所有元素都"d出"
		System.out.println(stack.pop());
		
		System.out.println(stack.isEmpty());// 判断栈是否为空
		
	}

}

class MyStack{
	private Queue queue1 = new LinkedList();
	private Queue queue2 = new LinkedList();
	
	// 入栈(入不为空的栈)
	public void push(E e) {
		if(!queue1.isEmpty()) {
			queue1.offer(e);
		}else if(queue2.isEmpty()){
			queue2.offer(e);
		}else {
			queue1.offer(e);
		}
	}
	
	// 出栈(出不为空的栈)
	public E pop() {
		if(queue1.isEmpty() && queue2.isEmpty()) {
			return  null;
		}
		if(!queue1.isEmpty()) {
			int size = queue1.size() - 1;
			for (int i = 0; i < size; i++) {
				queue2.offer(queue1.poll());
			}
			return queue1.poll();
		}
		if(!queue2.isEmpty()) {
			int size = queue2.size() - 1;
			for (int i = 0; i < size; i++) {
				queue1.offer(queue2.poll());
			}
			return queue2.poll();
		}
		return null;
	}
	
	// 判断栈是否为空
	public boolean isEmpty() {
		return queue1.isEmpty() && queue2.isEmpty();
	}
	
}