用java实现用两个栈来实现一个队列,使用n个元素来完成n次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。数据范围:n≤1000
时间: 2024-03-22 17:38:22 浏览: 88
好的,这是一个经典的数据结构问题。Java中可以使用Stack类来实现栈,代码如下:
```java
import java.util.Stack;
public class QueueWithTwoStacks {
private Stack<Integer> stack1; // 用于插入元素
private Stack<Integer> stack2; // 用于删除元素
/** Initialize your data structure here. */
public QueueWithTwoStacks() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
/** Get the front element. */
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
```
我们使用两个栈来模拟一个队列,其中stack1用于插入元素,stack2用于删除元素。每次插入元素时,直接将元素压入stack1中;每次删除元素时,如果stack2为空,则先将stack1中的元素倒入stack2中,再从stack2的栈顶弹出元素。这样就可以实现用两个栈来实现一个队列的功能。
接下来我们可以使用QueueWithTwoStacks这个类来完成题目中的要求,如下所示:
```java
public class Main {
public static void main(String[] args) {
QueueWithTwoStacks queue = new QueueWithTwoStacks();
for (int i = 1; i <= 1000; i++) {
queue.push(i);
}
for (int i = 1; i <= 1000; i++) {
System.out.println(queue.pop());
}
}
}
```
这段代码会先向队列中插入1000个整数,然后依次从队列头部删除整数并输出。由于题目保证操作合法,所以这段代码可以正常运行并输出结果。
阅读全文