队列实现栈（java）

栈的特性是后进先出。栈的两个主要操作，一个是出栈，一个是入栈。

队列的特性是先进先出。队列的两个主要操作，一个是队尾追加元素，一个是队首取出元素。

要用队列实现栈，那么需要两个队列，一个正式队列，一个预备队列。正式队列相当于栈，用来存储入栈的元素；预备队列用来在出栈的时候，将队首到队尾前一个元素进行临时存储，待出栈操作完成后，再将预备队列中的元素取出放到正式队列中。

代码实现如下：

package algorithm;

import java.util.LinkedList;
import java.util.Queue;

public class StackByQueue {

    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }

}

class MyStack {

    Queue<Object> normalQueue = new LinkedList<Object>();// 正式队列
    Queue<Object> prepareQueue = new LinkedList<Object>();// 预备队列

    // 出栈
    public Object pop() {
        while (normalQueue.size() > 1) {
            prepareQueue.add(normalQueue.poll());
        }
        Object poll = normalQueue.poll();
        while (prepareQueue.size() > 0) {
            normalQueue.add(prepareQueue.poll());
        }
        return poll;
    }

    // 入栈
    public void push(Object obj) {
        normalQueue.add(obj);
    }

}