使用c++,利用两个栈sl和s2的操作可以模拟一个队列的操作,请写出使用两个栈实现入队、出队和判队列空的函数
时间: 2024-09-28 20:10:21 浏览: 38
C++ 数据结构实现两个栈实现一个队列
5星 · 资源好评率100%
在C++中,我们可以利用两个栈`sl`(stack 1)和`s2`(stack 2)来模拟队列的行为。这是因为栈的数据结构允许我们按后进先出(LIFO)的原则添加元素,而另一个栈可以作为辅助来实现先进先出(FIFO)的操作。
以下是基本的函数实现:
```cpp
#include <stack>
class MyQueue {
private:
std::stack<int> sl;
std::stack<int> s2;
public:
// 入队操作
void enqueue(int value) {
sl.push(value);
}
// 出队操作(如果队列非空)
int dequeue() {
if (sl.empty()) { // 如果sl为空,说明队列已空
while (!s2.empty()) { // 将s2的所有元素转移到sl
sl.push(s2.top());
s2.pop();
}
if (sl.empty()) throw std::runtime_error("Queue is empty!"); // 队列仍空,抛出异常
}
int top = sl.top(); // 获取sl顶部元素
sl.pop(); // 移除sl顶部元素
return top; // 返回出队元素
}
// 判队列是否为空
bool isEmpty() {
return sl.empty() && s2.empty(); // 如果两个栈都空,则队列为空
}
};
```
在这个实现中,当我们需要出队时,首先检查`sl`是否为空。如果`sl`为空,说明队列从未被初始化过或者已经完全出队。此时,我们将`s2`中的所有元素逐个压入`sl`,然后再次尝试出队。如果最终`sl`依然为空,那么队列确实为空。
阅读全文