用两个栈实现队列
import java.util.Stack;
public class Algorithm {
public static void main(String[] args) {
MyQueue myQueue = new MyQueue();
for (int i = 0; i < 10; i++) {
myQueue.push(i);
if (i % 2 == 0){
myQueue.pop();
}
System.out.println(myQueue.peek());
}
}
}
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
int topElement;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
/**
* 队首元素是第一个入栈的元素,因此栈为空时入栈的元素就是队首元素
*/
if (stack1.isEmpty()){
topElement = x;
}
stack1.push(x);
}
public int pop() {
/**
* 当需要出队时,队首元素在栈底,把栈底元素上面的元素全部转移到另一个栈
* 新栈的栈顶就是新的队首
* 此时stack2的出栈顺序和队列的出队顺序一致,不用急着把元素再还原回去,如果再次调用pop(),直接让stack2出栈,直到stack2为空
*/
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if (!stack2.isEmpty()) {
return stack2.peek();
}
/**
* 如果stack2空了,那队首就是stack1的栈底(即最先入栈的那个元素)
*/
return topElement;
}
public boolean empty() {
/**
* stack1和stack2同时为空,队列才为空
*/
return stack1.isEmpty() && stack2.isEmpty();
}
}
https://leetcode-cn.com/problems/implement-queue-using-stacks/