一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S),入栈Push(S,i.x),出栈Pop(S,i,x)算法,其中i为0或1,用以表示栈号,写出代码并写出主函数实现代码
时间: 2024-10-07 19:02:25 浏览: 13
在C++中,我们可以使用动态数组(vector)作为底层数据结构来实现这样一个双向栈(即有两个独立栈的数据结构)。以下是`InitStack`, `Push`, 和 `Pop` 函数的设计以及一个简单的主函数示例:
```cpp
#include <iostream>
#include <vector>
class DualStack {
private:
std::vector<int> stack[2]; // 双向栈,栈底分别在两端
public:
// 初始化栈
void InitStack() {
for (int i = 0; i < 2; ++i)
stack[i].clear();
}
// 根据栈号i入栈元素x
void Push(int i, int x) {
if (i == 0)
stack[i].push_back(x);
else
stack[i].insert(stack[i].begin(), x); // 从栈顶插入
}
// 根据栈号i出栈并返回元素到x
bool Pop(int i, int& x) {
if (i == 0) {
if (stack[i].empty())
return false;
x = stack[i].back();
stack[i].pop_back();
return true;
} else {
if (stack[i].size() <= 1)
return false;
x = *stack[i].rbegin(); // 从栈底取出
stack[i].pop_back();
return true;
}
}
};
// 主函数示例
int main() {
DualStack s;
s.InitStack();
s.Push(0, 5); // 入栈0号栈
s.Push(1, 10); // 入栈1号栈
int value1, value2;
// 出栈测试
if (s.Pop(0, value1)) {
std::cout << "Popped from 0th stack: " << value1 << std::endl;
} else {
std::cout << "Cannot pop from empty 0th stack" << std::endl;
}
if (s.Pop(1, value2)) {
std::cout << "Popped from 1st stack: " << value2 << std::endl;
} else {
std::cout << "Cannot pop from 1st stack" << std::endl;
}
return 0;
}
```
这个程序首先初始化了两个空栈,然后依次往每个栈中添加元素,最后尝试从中出栈。请注意,`Pop` 函数会检查栈是否为空或只有一个元素,以避免非法操作。