如何使用Java堆栈实现队列-成都快上网建站

如何使用Java堆栈实现队列

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

创新互联公司是一家专注于成都网站设计、成都网站建设、外贸网站建设与策划设计,港北网站建设哪家好?创新互联公司做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:港北等地区。港北做网站价格咨询:13518219792

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 toppeek/pop from topsize, 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]。

如何使用Java堆栈实现队列

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

如何使用Java堆栈实现队列

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

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

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

如何使用Java堆栈实现队列

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

如何使用Java堆栈实现队列

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

如何使用Java堆栈实现队列

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

如何使用Java堆栈实现队列

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

如何使用Java堆栈实现队列

可以看到,通过这种方法,可以始终保持主栈是以队列的顺序存储元素(参考本文的第一幅图)。至于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 stack1 = new LinkedList<>(); // the aux one
        private LinkedList 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堆栈实现队列这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


本文名称:如何使用Java堆栈实现队列
转载来于:http://kswjz.com/article/pppihp.html
扫二维码与项目经理沟通

我们在微信上24小时期待你的声音

解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流