本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖

面試題9：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

題目要求：
用兩個(gè)棧，實(shí)現(xiàn)隊(duì)列的從隊(duì)尾插入元素offer()和從隊(duì)頭拋出元素poll()
相關(guān)：用隊(duì)列實(shí)現(xiàn)棧

思路：
（1）對(duì)于插入操作，棧與隊(duì)列都是從隊(duì)尾進(jìn)行，因此一行代碼就可以完成offer()
（2）對(duì)于彈出操作，隊(duì)列先進(jìn)先出從隊(duì)頭開始，而棧后進(jìn)先出從隊(duì)尾開始，要想取到隊(duì)頭元素，就得需要第二個(gè)棧stack2的協(xié)助：彈出時(shí)將stack1的元素依次取出放到stack2中，此時(shí)stack2進(jìn)行彈出的順序就是整個(gè)隊(duì)列的彈出順序。而如果需要插入，放到stack1中即可。
總結(jié)下，stack1負(fù)責(zé)插入，stack2負(fù)責(zé)彈出，如果stack2為空了，將stack1的元素依次彈出并存放到stack2中，之后對(duì)stack2進(jìn)行彈出操作。

代碼：

package chapter2;
import java.util.Stack;

/**
 * Created by ryder on 2017/6/20.
 * 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
 */
class MyQueue<T>{
    private Stack<T> stack1 = new Stack<>();
    private Stack<T> stack2 = new Stack<>();
    
    public void offer(T data){
        stack1.push(data);
    }
    public T poll(){
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        else if(!stack1.isEmpty()){
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
            return stack2.pop();
        }
        else
            return null;
    }
}

public class P68_QueueWithTwoStacks {
    public static void main(String[] args){
        MyQueue<Integer> myQueue = new MyQueue<>();
        System.out.println(myQueue.poll());
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
        myQueue.offer(4);
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.poll());
    }
}

運(yùn)行結(jié)果

null
1
2
3
4
null