使用c++语言,在一个数组中实现两个堆栈。
时间: 2024-09-20 21:18:21 浏览: 36
堆栈-顺序存储实现代码.c
在C++中,可以使用数组同时实现两个堆栈。一个堆栈通常使用数组的一端作为头部,另一个堆栈则使用数组的另一端作为头部。这是因为堆栈遵循“后进先出”(LIFO)原则,所以当你在数组的一端压入元素时,它会自然地堆积在数组的另一端,形成了第二个“隐式”的堆栈。以下是简单的实现方法:
1. 定义两个堆栈,每个堆栈都有一个大小限制(例如数组长度的一半)和一个当前顶部索引:
```cpp
#include <iostream>
const size_t ARRAY_SIZE = 100; // 假设数组大小
size_t stack1_top = 0; // 堆栈1的顶部
size_t stack2_top = ARRAY_SIZE - 1; // 堆栈2的顶部
int stack[ARRAY_SIZE]; // 数组用于存储元素
bool is_empty(size_t top) {
return top == ARRAY_SIZE / 2; // 如果顶部等于数组一半,则为空
}
void push_to_stack1(int value) {
if (!is_empty(stack1_top)) return; // 防止溢出
stack[stack1_top++] = value;
}
void push_to_stack2(int value) {
if (!is_empty(stack2_top)) return;
stack[stack2_top--] = value; // 因为是反向堆栈,所以top减一
}
```
2. 要从堆栈中弹出元素,只需简单地交换顶部索引并调整:
```cpp
int pop_from_stack1() {
if (is_empty(stack1_top)) return -1; // 栈空错误处理
int popped_value = stack[stack1_top];
stack[stack1_top] = 0; // 或者清理空间,这里为了简化示例假设元素都是整数
stack1_top--;
return popped_value;
}
int pop_from_stack2() {
if (is_empty(stack2_top)) return -1;
int popped_value = stack[stack2_top];
stack[stack2_top] = 0;
stack2_top++;
return popped_value;
}
```
阅读全文