CB4-双栈共享存储¶

代码实现¶

C
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000  // 两个栈共享的存储区大小

/**
 * 双栈共享存储结构定义
 * 两个栈顶相向增长，实现空间优化
 */
typedef struct {
    int data[MAXSIZE];  // 共享存储区
    int top1;           // 栈1的栈顶指针（从左向右增长）
    int top2;           // 栈2的栈顶指针（从右向左增长）
} Stack;

/**
 * 初始化双栈共享存储结构
 * @param s 指向双栈结构的指针
 */
void init(Stack* s) {
    s->top1 = -1;           // 栈1初始为空，栈顶为-1
    s->top2 = MAXSIZE;      // 栈2初始为空，栈顶为MAXSIZE
}

C
/**
 * 向指定栈入栈元素
 * @param s 指向双栈结构的指针
 * @param i 栈号（1表示栈1，2表示栈2）
 * @param x 要入栈的元素
 * @return 入栈成功返回true，栈满返回false
 */
bool push(Stack* s, int i, int x) {
    // 参数合法性检查
    if (i != 1 && i != 2) {
        return false;
    }

    // 检查两个栈是否相遇（存储区已满）
    if (s->top2 - s->top1 == 1) {
        printf("存储区已满，无法入栈\n");
        return false;
    }

    // 根据栈号执行相应的入栈操作
    if (i == 1) {
        // 栈1：从左向右增长，先移动栈顶指针再存储元素
        s->data[++s->top1] = x;
    } else if (i == 2) {
        // 栈2：从右向左增长，先移动栈顶指针再存储元素
        s->data[--s->top2] = x;
    }

    return true;
}

C
/**
 * 从指定栈出栈元素
 * @param s 指向双栈结构的指针
 * @param i 栈号（1表示栈1，2表示栈2）
 * @param x 指向存储出栈元素的指针
 * @return 出栈成功返回true，栈空返回false
 */
bool pop(Stack* s, int i, int* x) {
    // 参数合法性检查
    if (i != 1 && i != 2) {
        return false;
    }

    // 根据栈号执行相应的出栈操作
    if (i == 1) {
        // 栈1出栈
        if (s->top1 == -1) {
            printf("栈1为空，无法出栈\n");
            return false;  // 栈1为空
        }
        *x = s->data[s->top1--];  // 先获取元素，再移动栈顶指针
    } else if (i == 2) {
        // 栈2出栈
        if (s->top2 == MAXSIZE) {
            printf("栈2为空，无法出栈\n");
            return false;  // 栈2为空
        }
        *x = s->data[s->top2++];  // 先获取元素，再移动栈顶指针
    }

    return true;
}

C
/**
 * 判断指定栈是否为空
 * @param s 双栈结构
 * @param i 栈号
 * @return 空栈返回true，非空返回false
 */
bool isEmpty(Stack s, int i) {
    if (i == 1) {
        return s.top1 == -1;
    } else if (i == 2) {
        return s.top2 == MAXSIZE;
    }
    return true;  // 非法栈号
}

C
/**
 * 判断指定栈是否已满
 * @param s 双栈结构
 * @return 栈满返回true，未满返回false
 */
bool isFull(Stack s) {
    return s.top2 - s.top1 == 1;
}

C
/**
 * 获取指定栈的元素个数
 * @param s 双栈结构
 * @param i 栈号
 * @return 栈中元素个数
 */
int getSize(Stack s, int i) {
    if (i == 1) {
        return s.top1 + 1;
    } else if (i == 2) {
        return MAXSIZE - s.top2;
    }
    return 0;
}

双栈共享存储结构图解¶

Text Only

存储区结构：
┌─────────────────────────────────────────────────┐
│  0  │  1  │  2  │  ...  │ ... │  n-2 │  n-1  │
├─────┼─────┼─────┼───────┼─────┼──────┼───────┤
│     │     │     │       │     │      │       │
└─────┴─────┴─────┴───────┴─────┴──────┴───────┘
  ↑                             ↑
top1(栈1)                top2(栈2)

栈1增长方向：→ → → → → → →
栈2增长方向：← ← ← ← ← ← ←

栈满条件：top2 - top1 == 1 (相邻)

操作流程图解¶

初始状态：¶

Text Only
1 2 3	`存储区：[ ][ ][ ][ ][ ][ ][ ][ ] ↑ ↑ top1=-1 top2=MAXSIZE`

栈1入栈操作：¶

Text Only
1 2 3 4 5 6 7 8 9	`push(s, 1, 10)：存储区：[10][ ][ ][ ][ ][ ][ ][ ] ↑ ↑ top1=0 top2=MAXSIZE push(s, 1, 20)：存储区：[10][20][ ][ ][ ][ ][ ][ ] ↑ ↑ top1=1 top2=MAXSIZE`

栈2入栈操作：¶

Text Only

push(s, 2, 30)：
存储区：[10][20][ ][ ][ ][ ][30][ ]
              ↑           ↑     ↑
            top1=1      top2=6  MAXSIZE

push(s, 2, 40)：
存储区：[10][20][ ][ ][ ][40][30][ ]
              ↑      ↑           ↑
            top1=1  top2=5    MAXSIZE

栈满状态：¶

Text Only
1 2 3 4 5	`存储区：[10][20][30][ ][40][50][60][ ] ↑ ↑ ↑ ↑ top1=2 \|\| top2=4 \|\| 栈满：top2-top1=1`

出栈操作：¶

Text Only

pop(s, 1, &x)：
x = 20, top1 = 1
存储区：[10][20][ ][ ][ ][40][50][60][ ]
         ↑        ↑     ↑
       top1=1    ||   top2=5
                 ||
pop(s, 2, &x)：
x = 40, top2 = 6
存储区：[10][ ][ ][ ][ ][40][50][60][ ]
         ↑              ↑
       top1=1        top2=6

复杂度分析¶

时间复杂度：O(1)¶

入栈操作：直接通过数组下标访问，O(1)
出栈操作：直接通过数组下标访问，O(1)
判空操作：简单比较操作，O(1)
总体时间复杂度：O(1)

空间复杂度：O(1)¶

额外空间：只使用常数个变量（top1、top2等）
存储空间：共享存储区大小固定为MAXSIZE
算法额外空间复杂度：O(1)

算法优化版本¶

C
/**
 * 线程安全版本（添加互斥锁）
 */
#ifdef THREAD_SAFE
#include <pthread.h>

typedef struct {
    int data[MAXSIZE];
    int top1;
    int top2;
    pthread_mutex_t mutex;
} ThreadSafeStack;

bool push_safe(ThreadSafeStack* s, int i, int x) {
    pthread_mutex_lock(&s->mutex);

    bool result = false;
    if (i != 1 && i != 2) {
        goto cleanup;
    }

    if (s->top2 - s->top1 == 1) {
        goto cleanup;
    }

    if (i == 1) {
        s->data[++s->top1] = x;
    } else if (i == 2) {
        s->data[--s->top2] = x;
    }
    result = true;

cleanup:
    pthread_mutex_unlock(&s->mutex);
    return result;
}
#endif

/**
 * 动态扩容版本
 */
typedef struct {
    int* data;
    int top1;
    int top2;
    int capacity;
} DynamicSharedStack;

bool resize(DynamicSharedStack* s) {
    int new_capacity = s->capacity * 2;
    int* new_data = (int*)realloc(s->data, new_capacity * sizeof(int));
    if (new_data == NULL) {
        return false;
    }

    // 调整栈2中元素的位置
    int old_size2 = s->capacity - s->top2;
    if (old_size2 > 0) {
        for (int i = 0; i < old_size2; i++) {
            new_data[new_capacity - 1 - i] = new_data[s->capacity - 1 - i];
        }
        s->top2 = new_capacity - old_size2;
    }

    s->data = new_data;
    s->capacity = new_capacity;
    return true;
}

错误处理完善版本¶

C
/**
 * 带详细错误信息的版本
 */
typedef enum {
    OPERATION_SUCCESS,
    INVALID_STACK_ID,
    STACK_OVERFLOW,
    STACK_UNDERFLOW
} OperationResult;

OperationResult push_detailed(Stack* s, int i, int x) {
    if (i != 1 && i != 2) {
        return INVALID_STACK_ID;
    }

    if (s->top2 - s->top1 == 1) {
        return STACK_OVERFLOW;
    }

    if (i == 1) {
        s->data[++s->top1] = x;
    } else {
        s->data[--s->top2] = x;
    }

    return OPERATION_SUCCESS;
}

OperationResult pop_detailed(Stack* s, int i, int* x) {
    if (i != 1 && i != 2) {
        return INVALID_STACK_ID;
    }

    if (i == 1) {
        if (s->top1 == -1) {
            return STACK_UNDERFLOW;
        }
        *x = s->data[s->top1--];
    } else {
        if (s->top2 == MAXSIZE) {
            return STACK_UNDERFLOW;
        }
        *x = s->data[s->top2++];
    }

    return OPERATION_SUCCESS;
}

算法特点¶

核心思想：两个栈共享同一存储空间，栈顶相向增长，充分利用存储空间。

关键技术： 1. 双栈顶指针：top1和top2分别管理两个栈 2. 相向增长：栈1从左向右，栈2从右向左 3. 共享存储：最大化空间利用率 4. 边界检测：准确判断栈满和栈空条件

优势： - 空间效率高：两个栈动态共享存储空间 - 操作效率高：所有操作都是O(1)时间复杂度 - 灵活性好：根据实际需求动态分配空间

应用场景： - 内存受限的嵌入式系统 - 需要同时使用两个栈的算法 - 表达式求值（操作数栈和操作符栈） - 函数调用和返回地址管理

关键边界条件： - 栈满：top2 - top1 == 1 - 栈1空：top1 == -1 - 栈2空：top2 == MAXSIZE

这种双栈共享存储的设计是数据结构中的经典优化技术，在实际应用中具有很高的实用价值。

双栈设计在实际场景中的应用¶

双栈共享存储设计在表达式求值、括号匹配等场景中有着广泛而重要的应用：

1. 表达式求值（经典应用）¶

C
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXSIZE 1000

typedef struct {
    int data[MAXSIZE];
    int top1;  // 操作数栈
    int top2;  // 操作符栈
} ExpressionStack;

void init_expr_stack(ExpressionStack* s) {
    s->top1 = -1;
    s->top2 = MAXSIZE;
}

// 操作数入栈（栈1）
bool push_operand(ExpressionStack* s, int operand) {
    if (s->top2 - s->top1 == 1) return false;
    s->data[++s->top1] = operand;
    return true;
}

// 操作符入栈（栈2）
bool push_operator(ExpressionStack* s, char op) {
    if (s->top2 - s->top1 == 1) return false;
    s->data[--s->top2] = op;
    return true;
}

// 操作数出栈
bool pop_operand(ExpressionStack* s, int* operand) {
    if (s->top1 == -1) return false;
    *operand = s->data[s->top1--];
    return true;
}

// 操作符出栈
bool pop_operator(ExpressionStack* s, char* op) {
    if (s->top2 == MAXSIZE) return false;
    *op = s->data[s->top2++];
    return true;
}

/**
 * 中缀表达式求值
 */
int evaluate_expression(const char* expr) {
    ExpressionStack s;
    init_expr_stack(&s);

    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];

        if (isspace(ch)) continue;

        if (isdigit(ch)) {
            // 解析数字
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;  // 回退一位
            push_operand(&s, num);
        }
        else if (ch == '(') {
            push_operator(&s, ch);
        }
        else if (ch == ')') {
            // 计算括号内的表达式
            while (s.top2 < MAXSIZE && s.data[s.top2] != '(') {
                char op;
                int b, a;
                pop_operator(&s, &op);
                pop_operand(&s, &b);
                pop_operand(&s, &a);

                switch (op) {
                    case '+': push_operand(&s, a + b); break;
                    case '-': push_operand(&s, a - b); break;
                    case '*': push_operand(&s, a * b); break;
                    case '/': push_operand(&s, a / b); break;
                }
            }
            s.top2++;  // 弹出'('
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            // 处理操作符优先级
            while (s.top2 < MAXSIZE && s.data[s.top2] != '(' &&
                   get_priority(s.data[s.top2]) >= get_priority(ch)) {
                char op;
                int b, a;
                pop_operator(&s, &op);
                pop_operand(&s, &b);
                pop_operand(&s, &a);

                switch (op) {
                    case '+': push_operand(&s, a + b); break;
                    case '-': push_operand(&s, a - b); break;
                    case '*': push_operand(&s, a * b); break;
                    case '/': push_operand(&s, a / b); break;
                }
            }
            push_operator(&s, ch);
        }
    }

    // 处理剩余操作符
    while (s.top2 < MAXSIZE) {
        char op;
        int b, a;
        pop_operator(&s, &op);
        pop_operand(&s, &b);
        pop_operand(&s, &a);

        switch (op) {
            case '+': push_operand(&s, a + b); break;
            case '-': push_operand(&s, a - b); break;
            case '*': push_operand(&s, a * b); break;
            case '/': push_operand(&s, a / b); break;
        }
    }

    int result;
    pop_operand(&s, &result);
    return result;
}

int get_priority(char op) {
    switch (op) {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
        default: return 0;
    }
}

2. 多种类型括号匹配¶

C
/**
 * 多种括号类型匹配检查
 */
typedef struct {
    char data[MAXSIZE];
    int top1;  // 左括号栈
    int top2;  // 右括号栈（用于错误处理）
} BracketStack;

bool check_multiple_brackets(const char* expr) {
    BracketStack s;
    s.top1 = -1;
    s.top2 = MAXSIZE;

    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];

        if (ch == '(' || ch == '[' || ch == '{') {
            // 左括号入栈1
            if (s.top2 - s.top1 == 1) return false;  // 栈满
            s.data[++s.top1] = ch;
        }
        else if (ch == ')' || ch == ']' || ch == '}') {
            // 右括号检查匹配
            if (s.top1 == -1) {
                // 右括号多余，可入栈2记录错误位置
                if (s.top2 - s.top1 == 1) return false;
                s.data[--s.top2] = i;  // 记录错误位置
                return false;
            }

            char left_bracket = s.data[s.top1--];
            if (!is_matching_pair(left_bracket, ch)) {
                return false;  // 类型不匹配
            }
        }
    }

    return (s.top1 == -1);  // 所有括号都匹配
}

bool is_matching_pair(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

3. 函数调用栈模拟¶

C
/**
 * 函数调用栈模拟（局部变量和返回地址）
 */
typedef struct {
    int data[MAXSIZE];
    int top1;  // 局部变量栈
    int top2;  // 返回地址栈
} FunctionStack;

void init_function_stack(FunctionStack* s) {
    s->top1 = -1;
    s->top2 = MAXSIZE;
}

// 保存局部变量
bool save_local_var(FunctionStack* s, int var) {
    if (s->top2 - s->top1 == 1) return false;
    s.data[++s.top1] = var;
    return true;
}

// 保存返回地址
bool save_return_address(FunctionStack* s, int addr) {
    if (s->top2 - s.top1 == 1) return false;
    s.data[--s.top2] = addr;
    return true;
}

// 恢复局部变量
bool restore_local_var(FunctionStack* s, int* var) {
    if (s->top1 == -1) return false;
    *var = s->data[s->top1--];
    return true;
}

// 恢复返回地址
bool restore_return_address(FunctionStack* s, int* addr) {
    if (s->top2 == MAXSIZE) return false;
    *addr = s->data[s->top2++];
    return true;
}

4. 浏览器前进后退功能¶

C
/**
 * 浏览器历史记录管理
 */
typedef struct {
    char history[MAXSIZE][100];  // 历史记录
    int top1;  // 后退历史栈
    int top2;  // 前进历史栈
} BrowserStack;

void init_browser(BrowserStack* s) {
    s->top1 = -1;
    s->top2 = MAXSIZE;
}

// 访问新页面
bool visit_page(BrowserStack* s, const char* url) {
    if (s->top2 - s->top1 == 1) return false;

    // 清空前进历史
    s->top2 = MAXSIZE;

    // 添加到后退历史
    strcpy(s->history[++s->top1], url);
    return true;
}

// 后退
bool go_back(BrowserStack* s, char* current_url) {
    if (s->top1 <= 0) return false;  // 无法后退

    // 当前页面加入前进历史
    strcpy(s->history[--s->top2], s->history[s->top1]);

    // 后退到上一页
    strcpy(current_url, s->history[--s->top1]);
    return true;
}

// 前进
bool go_forward(BrowserStack* s, char* current_url) {
    if (s->top2 == MAXSIZE) return false;  // 无法前进

    // 当前页面加入后退历史
    strcpy(s->history[++s->top1], s->history[s->top2]);

    // 前进到下一页
    strcpy(current_url, s->history[s->top2++]);
    return true;
}

5. 表达式转换（中缀转后缀）¶

C
/**
 * 中缀表达式转后缀表达式
 */
typedef struct {
    char output[MAXSIZE][20];  // 输出队列
    char operators[MAXSIZE];   // 操作符栈
    int output_count;
    int top2;  // 操作符栈顶
} InfixToPostfixStack;

void init_conversion_stack(InfixToPostfixStack* s) {
    s->output_count = 0;
    s->top2 = MAXSIZE;
}

bool convert_to_postfix(const char* infix, char* postfix) {
    InfixToPostfixStack s;
    init_conversion_stack(&s);

    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];

        if (isalnum(ch)) {
            // 操作数直接输出
            char operand[2] = {ch, '\0'};
            strcpy(s.output[s.output_count++], operand);
        }
        else if (ch == '(') {
            // 左括号入栈
            if (s.top2 - (-1) == 1) return false;
            s.operators[--s.top2] = ch;
        }
        else if (ch == ')') {
            // 弹出直到左括号
            while (s.top2 < MAXSIZE && s.operators[s.top2] != '(') {
                char op[2] = {s.operators[s.top2++], '\0'};
                strcpy(s.output[s.output_count++], op);
            }
            s.top2++;  // 弹出左括号
        }
        else if (is_operator(ch)) {
            // 操作符处理优先级
            while (s.top2 < MAXSIZE && s.operators[s.top2] != '(' &&
                   get_priority(s.operators[s.top2]) >= get_priority(ch)) {
                char op[2] = {s.operators[s.top2++], '\0'};
                strcpy(s.output[s.output_count++], op);
            }
            if (s.top2 - (-1) == 1) return false;
            s.operators[--s.top2] = ch;
        }
    }

    // 弹出剩余操作符
    while (s.top2 < MAXSIZE) {
        char op[2] = {s.operators[s.top2++], '\0'};
        strcpy(s.output[s.output_count++], op);
    }

    // 构造后缀表达式
    postfix[0] = '\0';
    for (int i = 0; i < s.output_count; i++) {
        strcat(postfix, s.output[i]);
        if (i < s.output_count - 1) strcat(postfix, " ");
    }

    return true;
}

6. 实际应用性能对比¶

C
// 性能测试示例
void performance_comparison() {
    const char* test_expr = "((15/(7-(1+1)))*3)-(2+(1+1))";

    // 单栈实现
    clock_t start = clock();
    for (int i = 0; i < 100000; i++) {
        evaluate_expression_single_stack(test_expr);
    }
    clock_t single_stack_time = clock() - start;

    // 双栈实现
    start = clock();
    for (int i = 0; i < 100000; i++) {
        evaluate_expression(test_expr);
    }
    clock_t double_stack_time = clock() - start;

    printf("单栈实现耗时: %ld\n", single_stack_time);
    printf("双栈实现耗时: %ld\n", double_stack_time);
}

应用场景总结¶

主要优势：¶

内存效率：两个相关栈共享存储空间
操作效率：所有操作都是O(1)时间复杂度
逻辑清晰：分离不同类型的数据管理

典型应用场景：¶

编译器设计：表达式解析、语法分析
计算器应用：数学表达式求值
网页浏览器：历史记录管理
函数调用：局部变量和返回地址管理
文本编辑器：括号匹配检查
游戏开发：撤销/重做功能

实际项目中的应用：¶

数据库查询解析器：SQL表达式解析
JavaScript引擎：表达式求值
IDE代码分析：语法检查和括号匹配
科学计算器：复杂数学表达式计算

双栈共享存储设计是数据结构优化的经典案例，通过巧妙的空间共享机制，在实际应用中提供了高效、节省内存的解决方案。