定义顺序栈实现共享栈功能,用一长度为m的数值存放于双向栈,两个站点分别为Top1和Top2,如图所示,上溢条件为Top1=Top2,从键盘输入一串整数,奇数入stack1,偶数入stack2,直到上溢时停止输入,上溢条件即为栈满条件top2=top1+1。请告诉我C++代码,要求有必要的语言备注
时间: 2024-03-25 22:38:06 浏览: 46
顺序栈的c++实现
以下是C++代码实现顺序栈共享栈功能:
```
#include <iostream>
using namespace std;
#define MAXSIZE 100 // 栈的最大长度
typedef struct {
int data[MAXSIZE]; // 存储栈的数组
int top1; // 栈1的栈顶指针
int top2; // 栈2的栈顶指针
} SqStack;
// 初始化双向栈
void InitStack(SqStack &S) {
S.top1 = -1; // 初始化栈1的栈顶指针
S.top2 = MAXSIZE; // 初始化栈2的栈顶指针
}
// 判断栈是否为空
bool isEmpty(SqStack S, int stackNum) {
if (stackNum == 1) return S.top1 == -1;
else return S.top2 == MAXSIZE;
}
// 判断栈是否已满
bool isFull(SqStack S) {
return S.top1 == S.top2 - 1;
}
// 入栈
void Push(SqStack &S, int x, int stackNum) {
if (isFull(S)) {
cout << "Stack is full" << endl;
return;
}
if (stackNum == 1) {
S.data[++S.top1] = x; // 栈1入栈
} else {
S.data[--S.top2] = x; // 栈2入栈
}
}
// 出栈
void Pop(SqStack &S, int &x, int stackNum) {
if (isEmpty(S, stackNum)) {
cout << "Stack is empty" << endl;
return;
}
if (stackNum == 1) {
x = S.data[S.top1--]; // 栈1出栈
} else {
x = S.data[S.top2++]; // 栈2出栈
}
}
int main() {
SqStack S;
int n, x;
InitStack(S); // 初始化双向栈
cout << "请输入整数,奇数入栈1,偶数入栈2,直到栈满为止:" << endl;
while (!isFull(S)) {
cin >> n;
if (n % 2 == 0) Push(S, n, 2); // 偶数入栈2
else Push(S, n, 1); // 奇数入栈1
}
cout << "共享栈中的元素为:" << endl;
while (!isEmpty(S, 1)) { // 输出栈1中的元素
Pop(S, x, 1);
cout << x << " ";
}
while (!isEmpty(S, 2)) { // 输出栈2中的元素
Pop(S, x, 2);
cout << x << " ";
}
cout << endl;
return 0;
}
```
其中,双向栈中的 `top1` 表示栈1的栈顶指针,`top2` 表示栈2的栈顶指针。`Push` 函数实现入栈操作,`Pop` 函数实现出栈操作。在主函数中,通过 `InitStack` 函数初始化双向栈,然后通过输入整数,奇数入栈1,偶数入栈2,直到栈满为止。最后,通过 `Pop` 函数将栈1和栈2中的元素依次取出并输出。
阅读全文