双栈共享一维数组算法

双栈共享一维数组的算法是一种内存优化技巧，通常用于那些需要同时使用两个栈的数据结构场景，但实际存储空间有限的情况。这种方法利用了一个一维数组来模拟两个独立的栈，每个栈的顶部元素都在数组的不同位置。

基本思路是：

1. **数组索引**：为每个栈分配特定的一段数组区域。比如，我们可以用数组的前半部分（从0到数组长度/2 - 1）表示第一个栈，后半部分（从数组长度/2到数组长度-1）表示第二个栈。

2. **移动界限**：当一个栈满时，我们将它的顶部指针移动到另一个栈的底部位置。例如，如果第一个栈满了，我们把它的top指针移到数组长度/2，这样它就占据了第二个栈的空间。

3. **操作逻辑**：插入和删除操作需要检查相应的栈边界。对于入栈，只需检查目标栈的top是否达到其占用的数组区间的末尾；对于出栈，先更新top指针，然后检查新的top是否会跨过数组分界线。

4. **访问元素**：为了安全地访问元素，需要确保当前栈的top在其占用的区域内。可以通过检查top指针的位置来判断。

以下是一个简单的C++代码示例：

#include <vector>

struct Stack {
    int* top;
    int size, capacity;
};

Stack stack1, stack2; // 创建两个虚拟的栈
stack1.top = stack2.capacity / 2;
stack2.top = stack1.capacity;

// 入栈操作
void push(Stack& s, int value) {
    if (s.top == s.capacity) {
        // 如果栈满，切换到另一个栈
        s.top = stack1.top == stack1.capacity / 2 ? stack2.capacity : stack1.capacity / 2;
    }
    *(s.top++) = value;
}

// 出栈操作
int pop(Stack& s) {
    if (s.top == s.capacity / 2) {
        // 如果栈底到达了交换点，说明之前已经跨过了，需要重新调整
        s.top = stack1.top == stack1.capacity / 2 ? 0 : stack1.capacity / 2;
    }
    return *(--s.top);
}