题目描述
使用队列实现栈的下列操作：
- push(x) – 元素x入栈
- pop() – 移除栈顶元素
- top() – 获取栈顶元素
- empty() – 返回栈是否为空
注意：
- 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
解题思路
我们知道，队列的特性是元素先进先出，而栈的特性是元素的后进先出，本题中我们可以使用两个队列来实现栈的特性：
如下图所示，我们首先定义两个队列，用来实现栈的存储空间；当入栈时，让元素依次进一号队列；当出栈时，让一号队列的元素依次出队列并依次进入二号队列，将最后一个出一号队列的元素输出，因为最后一个出队列的元素也是最后一个“进栈”，因此完成出栈操作；此时元素存储在二号队列而一号队列为空，当需要再次出栈时，元素依次出二号队列进一号队列，最后出队列元素返回出栈，如此循环往复；
由此得到我们的方法——当有队列不为空时，进栈元素进入不为空的队列，队列都为空时元素进入随机的队列；出栈时将其他所有元素依次进到空队列，只将最后进栈的元素返回；判断栈是否为空的方法是判断是否有非空队列，有则栈不为空，否则栈为空
代码
import java.util.LinkedList;
import java.lang.Integer;
public class MyStack {
/** Initialize your data structure here. */
private LinkedList<Integer>[] queue=new LinkedList[2]; //用两个队列实现栈
private int queueIndex;
public MyStack() {
for(int i=0;i<2;i++)
{
queue[i]=new LinkedList<>();
}
queueIndex=0;
}
/** Push element x onto stack. */
public void push(int x) {
queue[queueIndex].offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
int element;
while(queue[queueIndex].size()>1)
{
int e=queue[queueIndex].pop();
queue[(queueIndex+1)%2].offer(e);
}
element=queue[queueIndex].pop();
queueIndex=(queueIndex+1)%2;
return element;
}
/** Get the top element. */
public int top() {
int element;
while(queue[queueIndex].size()>1)
{
int e=queue[queueIndex].pop();
queue[(queueIndex+1)%2].offer(e);
}
element=queue[queueIndex].pop();
queue[(queueIndex+1)%2].offer(element);
queueIndex=(queueIndex+1)%2;
return element;
}
/** Returns whether the stack is empty. */
public boolean empty() {
if(queue[0].isEmpty() && queue[1].isEmpty())
{
return true;
}
else
{
return false;
}
}
}