Question: How to use two stacks to implement a queue, that is, two methods to implement a queue-appendTail (insertion) and deleteHead (deletion).
Analysis: The core idea is that one stack stores forward and the other stack stores backward. The forward storage stack is used for insertion, and the reverse storage stack is used for deletion.
The implemented Java code is as follows:
Copy the code code as follows:
import java.util.Stack;
public class QueneWithTwoStacks<E> {
private Stack<E> stack1;
private Stack<E> stack2;
public void appendTail(E e) {
stack1.push(e);
}
public E deleteHead() throws Exception {
if (stack2.size() <= 0) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
if (stack2.size() == 0) {
throw new Exception("Queue is empty!");
}
return stack2.pop();
}
}