目录
1 题目描述
2 解题思路
3 代码实现
1 题目描述
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈pop() -- 移除栈顶元素top() -- 获取栈顶元素empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
2 解题思路
我们可以定义两个队列集合Queue，但此时万万不可直接实例化Queue集合——Queue集合是抽象的，不能直接实例化，可以通过子类LinkedList来实例化。
首先，我们先来看一下Queue<E>中的方法：
add(E e);//向队列中添加元素e
boolean offer(E e);//向队列中添加元素e，如果成功则返回true
E remove();//取出队头元素并删除；若队列为空，则抛出NoSuchElementException异常
E poll();//取出队头元素并删除；若队列为空，则返回null
E element();//取出队头元素但不删除；若队列为空，则抛出NoSuchElementException异常
E peek();//取出队头元素但不删除；若队列为空，则返回null
了解了这些方法，我们再考虑：
因为队列是先进先出机制，栈是先进后出机制，要用队列实现栈，我们假设要将n个元素入“栈”，入到一个不为空的队列中，要是进行出“栈”时，出的是队列中的队尾元素，所以我们可以定义size来记录队列中的元素个数，将size-1个元素移到另一个队列中，将剩下的那一个元素出“栈”就可以了。
再考虑：
入“栈”时，将该元素入到不为空的队列中，每次我们可以将前面size-1个元素移到另一个空队列中，再进行出“栈”就好了。
总结一下：每次出“栈”和入“栈”都出、入到不为空的队列中；注意出“栈”时队列为空的情况。
3 代码实现
class MyStack {
//定义两个队列
private Queue<Integer> queue1;
private Queue<Integer> queue2;
private int size;
/** Initialize your data structure here. */
public MyStack() {
this.queue1 = new LinkedList<Integer>();
this.queue2 = new LinkedList<Integer>();
this.size = 0;
}
/** Push element x onto stack. */
public void push(int x) {
//哪个队列为空，就向哪个队列添加元素
if(queue1.peek() != null){
queue1.offer(x);
}else if(queue2.peek() != null){
queue2.offer(x);
}else{
//都为空，则向queue1中添加元素
queue1.offer(x);
}
size++;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
if(empty()){
throw new RuntimeException("无数据");
}
//记录将要被删除的元素，并将其作为返回值
int e = 0;
if(queue2.peek() != null){
//将queue2中的size-1个元素移到queue1中
for(int i = 0; i < size - 1; i++){
queue1.offer(queue2.poll());
}
e = queue2.poll();
}else{
for(int i = 0; i < size - 1; i++){
queue2.offer(queue1.poll());
}
e = queue1.poll();
}
this.size--;
return e;
}
/** Get the top element. */
public int top() {
if(empty()){
throw new RuntimeException("无数据");
}
int e = 0;
if(queue2.peek() != null){
for(int i = 0; i < size; i++){
e = queue2.poll();
queue1.offer(e);
}
}else{
for(int i = 0; i < size; i++){
e = queue1.poll();
queue2.offer(e);
}
}
return e;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return size == 0;
}
public int size(){
return this.size;
}
}
