这篇文章主要讲解了“如何使用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)
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堆栈实现队列这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
