题目：
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
思路1：
了解栈和堆的数据结构。
栈：后进先出，顶端入栈，顶端出栈，好比弹夹。
队列：先进先出，后端入列，前端出列，好比水管。
代码如下：
/**
*
* 栈遵循后入先出的原则，从栈顶入，从栈顶出
*
* 队列遵循先进先出的原则，从后端入列，前端出列
*
* @author luxl
* @date 2020年12月7日
*/
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
Object[] arr = queue.toArray();
// 队列中移除所有元素，目的是入队列时，x时最新入的，也就是在最顶端
queue.removeAll(Arrays.asList(arr));
// 队列中新增最新元素
queue.add(x);
// 再新增移除的元素，可以控制原先的元素再x之后入列的
for (Object obj : arr) {
queue.add((Integer) obj);
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
思路2：
官方题解，申明双队列，一个负责存储数据，另外个用于临时存储数据(可以确保每次入队列的x都在队列最前面)。
代码如下：
class MyStack1 {
Queue<Integer> a;// 存储数据
Queue<Integer> b;// 存储临时数据，每次push之后清空
/** Initialize your data structure here. */
public MyStack1() {
a = new LinkedList<Integer>();
b = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
b.add(x);
// a的数据添加到b下面
while (!a.isEmpty()) {
b.add(a.poll());
}
// a，b对象互换
Queue<Integer> t = a;
a = b;
b = t;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return a.poll();
}
/** Get the top element. */
public int top() {
return a.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return a.isEmpty();
}
public static void main(String[] args) {
MyStack1 stack = new MyStack1();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
-------------------------------小白学算法
