利用两个栈sl和s2的操作可以模拟一个队列的操作,请写出使用两个栈实现入队、出队和判队列空的函数
时间: 2024-09-28 21:10:03 浏览: 43
山东大学《数据结构》讲义03栈和队列.docx
利用两个栈模拟队列的操作是一种常见的面试题场景,它通常涉及到数据结构的巧妙运用。在Java中,我们可以创建两个Stack对象,分别命名为sl(source stack)和s2(secondary stack)。为了实现队列的基本操作:
1. **入队(enqueue)**:
- 对于新元素`e`:
- 先将元素压入sl栈顶。
- 如果sl已满,无法再接收元素,则需要将sl中的所有元素逐个弹出并压入s2,因为队列的特点是先进先出(FIFO),这时s2相当于临时存储了元素直到sl可以接纳。
2. **出队(dequeue)**:
- 首先检查s2是否为空。如果s2为空并且sl也为空,说明队列为空,返回null或抛异常。
- 如果s2非空,直接从s2栈顶弹出元素作为出队结果。
- 否则,s2为空,sl中有元素,将sl的所有元素转移到s2,并删除sl的顶部元素,然后从s2栈顶弹出元素作为出队结果。
3. **判断队列是否为空(isQueueEmpty)**:
- 直接检查s2是否为空即可,因为当队列为空时,s2应该也是空的。
以下是简单的伪代码描述:
```java
void enqueue(E e) {
sl.push(e);
if (sl.isFull()) {
while (!sl.isEmpty()) {
s2.push(sl.pop());
}
}
}
E dequeue() {
if (s2.isEmpty() && sl.isEmpty()) return null; // 或抛异常
E result = s2.isEmpty() ? sl.pop() : s2.pop(); // 如果s2有元素,则优先取s2
// 将sl的元素转移到s2
while (!sl.isEmpty()) {
s2.push(sl.pop());
}
return result;
}
boolean isQueueEmpty() {
return s2.isEmpty();
}
```
阅读全文