LeetCode_225 用队列实现栈

题目地址：https://leetcode-cn.com/problems/implement-stack-using-queues/

题目：

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

试题分析：

这道题和232这道题一样，只是数据结构反过来实现，利用队列来实现栈，实现原理也是雷同，都是通过两个队列来实现堆栈的FILO的功能，在操作上也是一个进队列一个出队列，每次在push和pop的时候都要进行循环的在两个队列中导出导入,232和225在面试过程中是非常常见的一道算法题，能够考验你对队列和栈的特性理解和灵活使用。

public class ImplementStackUsingQueues_225 {
    private Queue<Integer> queueIn;
    private Queue<Integer> queueOut;

    /** Initialize your data structure here. */
    public ImplementStackUsingQueues_225() {
        queueIn = new LinkedBlockingQueue<Integer>();
        queueOut = new LinkedBlockingQueue<Integer>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        while(!queueOut.isEmpty()){
            queueIn.add(queueOut.poll());
        }
        queueIn.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while(!queueOut.isEmpty()){
            queueIn.add(queueOut.poll());
        }
        int length = queueIn.size();
        for(int i=0;i<length-1;i++){
            queueOut.add(queueIn.poll());
        }
        return queueIn.poll();
    }

    /** Get the top element. */
    public int top() {
        while(!queueOut.isEmpty()){
            queueIn.add(queueOut.poll());
        }
        int length = queueIn.size();
        for(int i=0;i<length-1;i++){
            queueOut.add(queueIn.poll());
        }
        int result = queueIn.peek();
        queueOut.add(queueIn.poll());
        return result;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queueIn.isEmpty() && queueOut.isEmpty();
    }
}

源码路径：com.monkey01.queue.ImplementStackUsingQueues_225

配套测试代码路径：test目录com.monkey01.queue.ImplementStackUsingQueues_225Test

https://github.com/feiweiwei/LeetCode4Java.git