用C++编写,利用两个栈sl和s2的操作可以模拟一个队列的操作,除了栈基本功能外,请写出使用两个栈实现入队、出队和判队列空的函数。并附测试数据
时间: 2024-11-13 11:24:17 浏览: 2
在C++中,我们可以使用两个栈`sl`和`s2`来模拟一个队列。栈通常遵循后进先出(LIFO)的原则,通过适当的入栈和出栈操作,我们可以创建一个先进先出(FIFO)的队列效果。下面是一个简单的实现:
```cpp
#include <stack>
template <typename T>
class Queue {
private:
stack<T> sl; // 后进栈
stack<T> s2; // 前进栈
public:
// 初始化队列
void enqueue(const T& value) {
sl.push(value); // 入栈到后进栈
}
// 出队操作,如果队列为空则抛异常
T dequeue() {
if (s2.empty()) { // 如果前进栈为空,说明整个队列都已出完
while (!sl.empty()) {
s2.push(sl.top()); // 将后进栈所有元素移到前进栈
sl.pop(); // 清空后进栈
}
}
if (s2.empty()) throw std::runtime_error("Queue is empty"); // 队列真的空了
T value = s2.top(); // 返回并移除前进栈顶部元素
s2.pop();
return value;
}
// 判断队列是否为空
bool is_empty() const {
return sl.empty() && s2.empty();
}
};
// 测试数据
int main() {
Queue<int> q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
assert(!q.is_empty());
try {
cout << q.dequeue() << endl; // 输出 1
} catch (const std::exception& e) {
cout << "Caught exception: " << e.what() << endl; // 这里不会执行,因为已经出队了一次
}
assert(q.is_empty() == false);
try {
cout << q.dequeue() << endl; // 这次会抛异常,因为队列已经空了
} catch (const std::runtime_error& e) {
cout << "Caught exception: " << e.what() << endl; // 正确捕获异常,输出 "Queue is empty"
}
return 0;
}
```
在这个实现中,`enqueue`操作直接入栈,`dequeue`操作首先确保前进栈非空,然后出栈;如果前进栈为空,则从后进栈取出所有元素放到前进栈,最后再出栈。
阅读全文