扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
这篇文章主要讲解了“如何使用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 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)
class MyQueue { private LinkedListstack1 = 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堆栈实现队列这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流