如何使用Java堆栈实现队列

这篇文章主要讲解了“如何使用Java堆栈实现队列”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何使用Java堆栈实现队列”吧！

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.

• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

解题思路

读完题之后，第一步必然要想清楚栈和队列的区别，如下图所示，栈和队列的基本实现其实都可以看作一个list：

1）那如果是栈的话，[1, 2, 3]入栈之后，指针会指向3，出栈的时候就会pop这个list里的3；

2）如果是队列的话，[1, 2, 3]入队之后，指针会指向1，出队的时候就会pop这个list里的1。

也就是说如果是栈，这个list里从上到下会是[3, 2, 1]，而如果是队列，则是[1, 2, 3]。因此，问题就转化为：怎么将一个插入之后会变成[3, 2, 1]的list变成插入之后是[1, 2, 3]。

这个问题一下子很难找到答案，我们退一步思考另外一个问题：假如现在已经是[1, 2, 3]，现在要将4这个元素插入到这个list里面，怎么才能保持[1, 2, 3, 4]？（正如下图所示）

为了解决这个问题，就需要将4插入到这个list的底部（而不能直接插入到顶部），那什么情况下4才能插入到底部？注意到这个list是一个栈，只有这个栈是空栈的情况下，4才有可能插入到底部。所以，我们要构造出空栈的情况，那如果要将一个非空的栈变成空栈，势必要pop元素，而且这些元素还必须保存起来，不能丢弃，所以必然要有一个地方，必然要有另外一个数据结构来存储这些pop出来的元素。

基于上面的思考过程，我们自然会想到额外再使用一个栈

来存储这些pop出来的元素，如下图所示。将主栈stack2的元素逐一pop出来并且push到辅助栈stack1中，就可以清空主栈，让它变成一个空栈。

这样一来，主栈就可以将新的元素4放入到底部。与此同时，因为元素进入辅助栈stack1之后，顺序变成了逆序[3, 2, 1]，所以当这些元素再pop出来导到主栈stack2时，又会跟原来的顺序[1, 2, 3]一样。

至此，整个算法的逻辑就清晰了，我们来重新过一遍。首先，当主栈stack2没有元素的时候，那就直接放入主栈stack2即可。

接下来会进来第二个元素2，那就按照如下的步骤走：

当新元素3要插入的时候，继续这个操作即可：

可以看到，通过这种方法，可以始终保持主栈是以队列的顺序存储元素（参考本文的第一幅图）。至于pop和peek方法，都只要直接对主栈stack2进行判断和处理就可以了。

时间复杂度

按照上面的解法，队列的各种基本操作的时间复杂度分别为：

push操作：整个过程需要将元素从主栈stack2挪到辅助栈stack1（这一步的时间复杂度是O(n)），然后插入新元素（时间复杂度O(1)），最后再挪回主栈stack2（时间复杂度O(n)），所以时间复杂度是O(2n+1)，等于O(n)

pop操作：因为只需要对主栈stack2做判断，所以只需要O(1)

peek操作：因为只需要对主栈stack2做判断，所以只需要O(1)

最终实现

Java实现

class MyQueue {

        private LinkedList<Integer> stack1 = new LinkedList<>(); // the aux one
        private LinkedList<Integer> stack2 = new LinkedList<>(); // the true one

        /**
         * Initialize your data structure here.
         */
        public MyQueue() {
        }

        /**
         * Push element x to the back of queue.
         */
        public void push(int x) {
            if (stack2.isEmpty()) {
                stack2.push(x);
            } else {
                while (!stack2.isEmpty()) {
                    stack1.push(stack2.pop());
                }
                stack2.push(x);
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
        }

        /**
         * Removes the element from in front of queue and returns that element.
         */
        public int pop() {
            if (!stack2.isEmpty()) {
                return stack2.pop();
            }
            return -1;
        }

        /**
         * Get the front element.
         */
        public int peek() {
            if (!stack2.isEmpty()) {
                return stack2.peek();
            }
            return -1;
        }

        /**
         * Returns whether the queue is empty.
         */
        public boolean empty() {
            return stack2.isEmpty();
        }
    }

感谢各位的阅读，以上就是“如何使用Java堆栈实现队列”的内容了，经过本文的学习后，相信大家对如何使用Java堆栈实现队列这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！