使用C++,利用两个栈sl和s2的操作可以模拟一个队列的操作,请写出使用两个栈实现入队、出队和判队列空的函数,并符合测试程序。
时间: 2024-09-30 16:04:08 浏览: 41
数据结构C++ 顺序栈、链栈、循环队列、链队列的主要操作(Word文档含代码和注释)
5星 · 资源好评率100%
对于您的要求,可以通过使用两个栈(stack)来模拟队列(queue)的行为。具体来说,一个栈(比如称为S1)用于添加元素(即入队操作),另一个栈(比如称为S2)用于删除元素(即出队操作)。当需要从队列中取出元素时,如果S2为空,则将S1中的所有元素依次弹出并压入S2,这样原本最后进入S1的元素会最先从S2中出来,从而实现了先进先出的原则。
以下是基于此思想编写的简化版代码示例:
```cpp
#include <iostream>
#include <stack>
using namespace std;
class QueueWithTwoStacks {
public:
stack<int> s1;
stack<int> s2;
// 入队操作
void EnQueue(int value) {
while (!s2.empty()) { // 如果s2不为空则清空它,保证顺序正确
s1.push(s2.top());
s2.pop();
}
s1.push(value); // 将新值推入s1
}
// 出队操作
int DeQueue() {
if (s1.empty() && s2.empty()) return -1; // 队列已空
if (s2.empty()) { // 只有当s2为空才从s1转移数据到s2
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
int topValue = s2.top(); // 记录顶部值
s2.pop(); // 弹出顶部元素
return topValue;
}
// 判队空函数
bool IsEmpty() const {
return s1.empty() && s2.empty();
}
};
// 测试函数以验证以上类的功能
void TestQueueFunctionality(QueueWithTwoStacks &queueObj) {
for(int i=1; i<=5; ++i){
queueObj.EnQueue(i*10);
}
cout << "First two elements dequeued: ";
for(int i=1; i<=2; ++i){
cout << queueObj.DeQueue() << ' ';
}
cout << endl;
for(int i=1; i<=4; ++i){
queueObj.EnQueue(i*20);
}
cout << "All remaining elements dequeued: ";
while (!queueObj.IsEmpty()){
cout << queueObj.DeQueue() << ' ';
}
}
int main(void) {
QueueWithTwoStacks q;
TestQueueFunctionality(q);
system("pause");
return 0;
}
```
这个示例展示了一个简单的队列实现,并且包含了入队(`EnQueue`)、出队(`DeQueue`)以及判断队列是否为空(`IsEmpty`)的基本功能。通过`TestQueueFunctionality`函数进行了基本功能的验证。请注意,上述代码仅作为参考实现,实际应用可能还需要考虑更多的边界条件和异常处理。
阅读全文