【正确答案】假设使用队列q1与队列q2模拟栈s,q1为入队列,q2为出队列。
实现思路如下:可以认为队列q1提供压栈的功能,队列q2提供弹栈的功能。
当要压栈时,入队列q1即可,而当要弹栈时,出队列则需要分为以下两种情况考虑:
1)如果队列q1中只有一个元素,那么让队列q1中的元素出队列并输出即可。
2)如果队列q1中有多于一个元素,那么让队列q1中所有元素出队列,入队列q2,最后一个元素不入队列q2,输出该元素,然后将队列q2所有元素入队列q1。
实现代码如下:
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class MyStack<T>
{
private Queue<T>q1=new LinkedBlockingQueue<T>();;
private Queue<T>q2=new LinkedBlockingQueue<T>();
public void push(T value)
{
q1.add(value);
}
public boolean empty()
{
if(q1.isEmpty())
return true;
else
return false;
}
public T pop()
{
if(q1.size()=0)
return null;
else if(q1.size()=1)
return q1.poll();
else
{
while(q1.size()>1)
q2.add(q1.poll());
T result=-q1.poll();
while(!q2.isEmpty())
q1.add(q2.poll());
return result;
}
}
public static void main(String[]args)
{
MyStack<Integer>stack=new MyStack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
stack.push(4);
System.out.println(stack.pop());
}
}
程序的运行结果为:
3
4
【答案解析】