两个栈实现队列（经典面试题）java

问题描述：用两个栈实现队列的基本方法，比如向队尾添加元素（offer）、获取队头元素（peek）、获取并删除队头元素（poll）。 解决思路：栈是先进后出的结构。比如1、2、3顺序进栈，出栈顺序是3、2、1。如果3、2、1顺序进栈，然后依次出栈的顺序就是1、2、3。可以发现把一个栈中的元素依次出栈并存放到另一个栈中，那么出栈的顺序就是队列的顺序。这里注意一定要把一个栈中元素全部存放到另一个栈中才可以。 只要保证数据存放时存放在一个栈中，每次获取数据都从这个栈中把数据导入另一个栈，就可以保证数据按照先入先出的顺序输出了。如果有两个栈v1和v2。如果保证数据都存放在v1中，每次获取数据时把v1的数据全部存放到v2中，由v2获取数据，获取数据之后在把v2中的数据写回v1（保证数据按照栈的结构存放）。每次插入数据时只要向v1中插入数据，就可以保证数据存放的栈结构。 上面做法看着很好（我面试时就这么写的），但有一个缺点，每次查询完都要讲v2中的数据存回v1中，浪费大量的时间。是不是可以不用回存呢。仔细观察就会发现v2中的数据顺序出栈，就是队列顺序输出的结果。只要v2中有数据从v2中出栈就可以了，v2中没数据了，才把v1的数据全部压入v2。代码如下：

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

class MyQueue<E>{
    Stack<E> v1 = new Stack<E>();
    Stack<E> v2 = new Stack<E>();
    //返回并删除首元素
    public E poll(){
        if(v2.isEmpty()){
            while(!v1.isEmpty()){
                v2.push(v1.pop());
            }
        }
        if(v2.isEmpty())
            return null;
        return v2.pop();    
    }
    //返回首元素，不删除
    public E peek(){
        if(v2.isEmpty()){
            while(!v1.isEmpty()){
                v2.push(v1.pop());
            }
        }
        if(v2.isEmpty())
            return null;
        return v2.peek();
    }
    //添加元素
    public boolean offer(E e){
        v1.push(e);
        return true;
    }
}
public class Main {
          
   
    //测试
    public static void main(String[] args) {
        Queue<Integer> que = new LinkedList<>();
        MyQueue<Integer> myque = new MyQueue<>();
        Random ra =new Random(); 
        for(int i=0;i<100000;i++)
        {   
            int k = ra.nextInt()+1;
            if(k%3 == 0){
                que.offer(k);
                myque.offer(k);
            }
            else if(k%3 == 1){
                Integer n = que.poll();
                Integer m = myque.poll();
                if(n!=m && !n.equals(m))
                    System.out.println(n+" != "+m);                 
            }
            else{
                Integer n = que.peek();
                Integer m = myque.peek();
                if(n!=m && !n.equals(m))
                    System.out.println(n+" != "+m);
            }
        }
    }
}