顺序栈与两栈共享空间的C语言实现

取栈顶

Status GetTop(SqStack s, SElemType *e) {
    if (s.top == -1) return ERROR;
    *e = s.data[s.top];
    return OK;
}

入栈

Status Push(SqStack *s, SElemType e) {
    if (s->top == MAXSIZE - 1) return ERROR; // 栈满
    s->top++;
    s->data[s->top] = e;
    return OK;
}

出栈

Status Pop(SqStack *s, SElemType *e) {
    if (s->top == -1) return ERROR;
    *e = s->data[s->top];
    s->top--;
    return OK;
}

遍历

Status StackTraverse(SqStack s) {
    int i = 0;
    while (i <= s.top) {
        visit(s.data[i++]);
    }
    printf("\n");
    return OK;
}

顺序栈的使用示例

int main() {
    int j;
    SqStack s;
    int e;
    if (InitStack(&s) == OK) {
        for (j = 1; j <= 10; j++) {
            Push(&s, j);
        }
        printf("栈中元素依次为： ");
        StackTraverse(s);
        Pop(&s, &e);
        printf("弹出的元素 e=%d\n", e);
        printf("栈空否：%d(1空0否)", StackEmpty(s));
        GetTop(&s, &e);
        printf("栈顶元素 e=%d 栈的长度为%d\n", e, StackLength(s));
        ClearStack(&s);
        printf("清空栈后，栈空否:%d(1空0否)\n", StackEmpty(s));
    }
    return 0;
}

顺序栈避免了插入删除时移动元素的问题，但缺点是数组大小必须事先指定，使用起来不够灵活。如果两个栈的元素变化趋势相反，可以采用一种技巧——两栈共享空间。

两栈共享空间

当有两个相同类型的栈，且一个栈在增长时另一个栈往往在缩短，就可以用一个数组同时存放两个栈，栈底分别固定在数组的两端，两个栈顶向中间延伸。这样能更充分地利用数组空间。

结构体中需要两个栈顶指针：

typedef struct {
    SElemType data[MAXSIZE];
    int top1; // 栈1栈顶指针
    int top2; // 栈2栈顶指针
} SqDoubleStack;

空栈状态下，top1 = -1，top2 = MAXSIZE；栈满的条件是 top1 + 1 == top2。

初始化

Status InitStack(SqDoubleStack *s) {
    s->top1 = -1;
    s->top2 = MAXSIZE;
    return OK;
}

判空

Status StackEmpty(SqDoubleStack s) {
    return (s.top1 == -1 && s.top2 == MAXSIZE);
}

求长度

int StackLength(SqDoubleStack s) {
    return s.top1 + 1 + (MAXSIZE - s.top2);
}

入栈（stackNumber标识栈1或栈2）

Status Push(SqDoubleStack *s, SElemType e, int stackNumber) {
    if (s->top1 + 1 == s->top2) return ERROR; // 栈满
    if (stackNumber == 1) {
        s->data[++s->top1] = e; // 栈1: 先top1+1再赋值
    } else if (stackNumber == 2) {
        s->data[--s->top2] = e; // 栈2: 先top2-1再赋值
    }
    return OK;
}

出栈

Status Pop(SqDoubleStack *s, SElemType *e, int stackNumber) {
    if (stackNumber == 1) {
        if (s->top1 == -1) return ERROR;
        *e = s->data[s->top1--];
    } else if (stackNumber == 2) {
        if (s->top2 == MAXSIZE) return ERROR;
        *e = s->data[s->top2++];
    }
    return OK;
}

遍历

Status StackTraverse(SqDoubleStack s) {
    int i = 0;
    while (i <= s.top1) visit(s.data[i++]);
    i = s.top2;
    while (i < MAXSIZE) visit(s.data[i++]);
    printf("\n");
    return OK;
}

两栈共享空间适合一个栈增长另一个栈缩短的动态情形，可以有效避免单独顺序栈空间浪费或不够用的尴尬。

参考资料：程杰.《大话数据结构》