数据结构：两栈共享空间

两顺序栈共享空间.c

//
// Created by 方朋 on 16/12/20.
//


#include <stdio.h>
#include "global.h"

/*
 * ADT 栈(stack)
 * InitStack(*S)    // 初始化一个空栈S
 * DestoryStack(*S) // 若栈存在则销毁
 * ClearStack(*S)   // 将栈清空
 * StackEmpty(S)    // 是否为空
 * GetTop(S, *e)    // 若栈存在且非空则用e返回S的栈顶元素
 * Push(*S, e)      // 入栈
 * Pop(*S, *e)      // 出栈
 * StackLength(L)   // 元素个数
 */

#define MAXSIZE 10

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

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

Status ClearStack(SqDoubleStack *S)
{
    return InitStack(S);
}
// 判断全栈是否为空
Status AllStackEmpty(SqDoubleStack S)
{
    return S.top1 == -1 && S.top2 == MAXSIZE;
}

// 判断栈1或栈2是否为空
int StackEmpty(SqDoubleStack S, int i)
{
    if (i == 1)
        return S.top1 == -1;
    return S.top2 == MAXSIZE;
}
// 获取栈1或栈2的栈顶元素
Status GetTop(SqDoubleStack S, int i, SElemType *e)
{
    if (StackEmpty(S, i)) return ERROR;
    int stack = i == 1 ? S.top1 : S.top2;
    *e = S.data[stack];
    return OK;
}

// 获取栈1或栈2长度
Status StackLength(SqDoubleStack S, int i)
{
    int len = 0;
    if (i == 1) {
        while (S.top1 > -1) {
            len++;
            S.top1--;
        }
    } else if (i == 2) {
        while (S.top2 < MAXSIZE) {
            len++;
            S.top2++;
        }
    }
    return len;
}

// 获取全栈长度
Status AllStackLength(SqDoubleStack S)
{
    return (S.top1 + 1) + (MAXSIZE - 1 - S.top2);
}

// 检查栈是否满了
int CheckStackFull(SqDoubleStack S)
{
    return S.top1 + 1 == S.top2;
}

// 栈1或栈2入栈
Status Push(SqDoubleStack *S, int i, SElemType e)
{
    if (CheckStackFull(*S)) return ERROR;
    if (i == 1) {
        // 往栈1插入
        S->data[++S->top1] = e;
    }
    if (i == 2) {
        // 往栈2插入
        S->data[--S->top2] = e;
    }

    return OK;
}

Status Pop(SqDoubleStack *S, int i, SElemType *e)
{
    if (StackEmpty(*S, i)) return ERROR;    // 栈1或栈2空
    if (i == 1) {
        *e = S->data[S->top1--];
    }
    if (i ==2) {
        *e = S->data[S->top2++];
    }
    return OK;
}

Status StackTraverse(SqDoubleStack S)
{
    int i = 0;
    printf("\n栈1元素:\n");
    while (S.top1 > -1) {
        printf("%d ", S.data[S.top1--]);
    }

    printf("\n栈2元素:\n");
    while (S.top2 < MAXSIZE) {
        printf("%d ", S.data[S.top2++]);
    }
    printf("\n");
    return OK;
}

int main(int argc, char **argv)
{
    int j;
    SqDoubleStack S;

    if(InitStack(&S) == OK) {
        for (j = 0; j < 5; ++j) {
            Push(&S, 1, j);
        }
        for (j = 5; j < 10; ++j) {
            Push(&S, 2, j);
        }
    }


    printf("Stack datas: ");
    StackTraverse(S);

    int e;
    Pop(&S, 1, &e);
    printf("Pop的1栈顶元素 e=%d\n", e);

    Pop(&S, 2, &e);
    printf("Pop的2栈顶元素 e=%d\n", e);

    printf("栈1是否为空: %d(1:空,0:否)\n", StackEmpty(S, 1));
    GetTop(S, 1, &e);

    printf("栈1栈顶元素 e=%d 栈的长度为:%d\n", e, StackLength(S, 1));
    ClearStack(&S);

    printf("清空栈后，栈空否：%d(1:空 0:否)\n", StackEmpty(S, 1));

}