[数据结构与算法]225. 用队列实现栈

225. 用队列实现栈

注意：
栈是类，可以直接实例化
队列是接口，不能被直接实例化，可以利用多态的思想用一个队列的实现类：LinkedList(底层是双向链表)

栈的push: 等价于 队列的offer
栈的pop: 等价于队列的poll

public class MyStack {
	Queue<Integer> q1 = new LinkedList<>();// 定义一个队列与栈的顺序相同
	Queue<Integer> q2 = new LinkedList<>();//辅助队列
	
	public MyStack(){
	}
	public void push(int x){
		q2.offer(x);
		while(!q1.isEmpty()){
			q2.offer(q1.poll());
		}// 此时q2装了所有元素，q1为空
		//交换q1和q2
		Queue<Integer> temp = q1;
		q1 = q2;
		q2 = temp;
	}

	public int pop(){
		return q1.poll();
	}
	public int top(){
		return q1.peek();
	}

	public boolean empty(){
		return q1.isEmpty();
	}
}

总结：
1、对于用队列来实现栈，主要考虑顺序问题，我开始做这个的时候脑袋不清晰，考虑到了用q2来作为添加新元素，再把q1的元素放到q2上，但是没有考虑到要去交换q2和q1，这样就保证了每次加入的元素都现在一个空的队列中。
2、队列是接口，并非是一个类，不能直接用来创建对象，所以可以用一个实现类，利用多态的思想即可。入队列：offer（）；出队列：poll()