用栈实现队列
程序员文章站
2024-01-28 21:44:46
...
我们知道,栈是先进后出的数据结构,队列是先进先出的数据结构,用栈实现队列,可以用两个栈实现,如下图所示,先入栈的也是先出栈的
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
//在这里是不是有人和我犯了同样的错误呢?直接返回 stack2.pop();
//出栈的时候需要判断 stack2 是不是空栈
//如果是空栈,就不能 pop
//所以当是空栈时,我们需要将 stack1 中的元素插入到 stack2 中,前提是 stack1 不能为空
//如果不是空栈,直接返回 stack2.pop();
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
//同样,返回栈顶元素和出栈类似,需要作以判断
public int peek() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
//判断空时需要同时两个栈都为空
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}