admin管理员组文章数量:1636896
Implement Queue by Two Stacks
Description
As the title described, you should only use two stacks to implement a queue’s actions.
The queue should support push(element)
, pop()
and top()
where pop is pop the first(a.k.a front) element in the queue.
Both pop and top methods should return the value of first element.
Example
push(1)
pop() // return 1
push(2)
push(3)
top() // return 2
pop() // return 2
实现思路
- 设有两个栈A和栈B,每次添加新元素时,都放入栈A中,每次需要从数据结构中取元素,都从栈B中取。
- 一旦栈中没有可取元素了,就将A中所有元素压入栈B中,假设元素压入栈A顺序是:
1,2,3,4,5
,从左到右对应先后次序,如果从栈A中取出,则是5,4,3,2,1
(即先取5,最后取1),然后再放入栈B中,则在栈B中的元素顺序为5,4,3,2,1
,再从栈B取出元素,则后进先出,即依次取出1,2,3,4,5
,从而总体形成了一个(1)先进(1)先出的队列顺序。
public class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
private Stack<Integer> curStack;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int element) {
stack1.push(element);
}
public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int top() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
}
版权声明:本文标题:Implement Queue by Two Stacks 解题报告 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729234520a1191842.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论