Implement the following operations of a stack using queues.
1. push(x) -- Push element x onto stack.
2. pop() -- Removes the element on top of the stack.
3. top() -- Get the top element.
4. empty() -- Return whether the stack is empty.
Example:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false
简单来说就是用队列实现栈结构。
栈的结构像叠砖头一样,一块一块往上叠,然后每次都是先从顶部一块块往下取下来,它是先进后出,后进先出的一种结构。
举些例子:
push(1):把1压进栈中
push(2):把2压进栈中
pop():栈顶元素出栈
队列的结构就像排队打饭一样,先来的在前面,后来的在后面,先来的可以打完饭然后走人,就相当于出队,后来的最后才能打饭,它是先进先出,后进后出的一种结构。
举些例子:
push(1):让1进入队列
push(2):让2进入队列
pop():队首元素打完饭了出队列
首先我们假设其中有一个队列已经实现了栈的结构,其中队首的元素就是栈顶元素,即如下图。
如果此时有一个元素要压进栈顶,弹栈的时候它是要第一个出栈的,那么换句话说,如果用队列实现的话,它就要在队列的头部,这样才能第一个出队,以便实现弹栈时候第一个被弹出去。那么像上图所示如果只用一个队列的话,把该元素放进队列只能放在该队列的尾部。所以,我们再用另外一个辅助队列,下面用例子说明
如果push(3):即相当于把3压进栈,即我们要实现的是把3进到队列的首部。
我们可以先把3进到一个辅助的空队列,这样他就成为队首元素,即相当于栈顶元素,因为队首和栈顶元素都是先出去的。
然后把原先的队列(即为实现好的栈结构,队首即为栈顶,队尾即为栈底)依次进到辅助队列内。
然后辅助Queue变成Queue,Queue变为辅助Queue,下次push元素时直接放到空的那个辅助队列中。
这样,就实现了用两个队列实现栈的算法。
实现代码:
import java.util.Queue;
public class MyStack {
Queue<Integer> q1 = new LinkedList<>(); //栈功能队列
Queue<Integer> q2 = new LinkedList<>(); //辅助队列
/** Initialize your data structure here. */
public MyStack() {
}
/** Push element x onto stack. */
public void push(int x) {
q2.add(x); //将元素x放入空的辅助队列中
if(!q1.isEmpty()) { /*吧栈功能队列的元素依次出队放进辅助队列中*/
q2.addAll(q1);
q1.clear();
}
/*把辅助队列置为栈功能队列,把栈功能队列置为辅助队列
此时辅助队列依然是空的*/
Queue<Integer> qtemp = q1;
q1 = q2;
q2 = qtemp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return q1.poll();
}
/** Get the top element. */
public int top() {
return q1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty();
}
}
好了,今天的算法刷题到此为止讲述完毕,如果您对题目有更好的解法或者更好的想法,或者您对题目有什么疑惑或者我讲错的地方,又或者您有其他的有趣的题目想让我们讲解的,欢迎评论区留言告诉我们,我们一定进行回复,让我们共同交流共同进步!
IT界的泥石流带你一同刷题!一同进步!一同成长!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。