(16)王道数据结构-栈的顺序存储实现

方式一：

#include<stdio.h>
#define MaxSize 10      //定义栈中元素最大个数
typedef struct {
    int data[MaxSize];  //静态数组存放栈中元素
    int  top;           //栈顶指针
} SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, int x);
bool Pop(SqStack &S, int &x);
int GetTop(SqStack S, int &x);
int main(void) {
    SqStack S;
    int x, top;
    InitStack(S);
    Push(S, 1);
    Push(S, 2);
    Push(S, 3);
    Push(S, 4);
    Push(S, 5);
    Push(S, 6);
    Push(S, 7);
    Pop(S,x);
    Pop(S,x);
    Pop(S,x);
    Pop(S,x);
    printf("x = %d\n", x);
    top = GetTop(S, x);
    printf("top = %d\n", top);
    if (!StackEmpty(S)) {
        Push(S, 8);
        printf("x = %d\n", x);
    }
    return 0;
}

//初始化栈
void InitStack(SqStack &S) {
    S.top = -1;     //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {  //栈空
        return true;
    } else {
        return false;
    }
}

//新元素入栈
bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) { //栈满报错
        return false;
    }
    S.top = S.top + 1;          //指针加1
    S.data[S.top] = x;          //新元素入栈
    return true;
}

//出栈操作
bool Pop(SqStack &S, int &x) {
    if (S.top == -1) {  //栈空，报错
        return false;
    }
    x = S.data[S.top];  //栈顶元素先出栈
    S.top = S.top - 1;  //指针减1
    return true;
}

//读取栈顶元素
int GetTop(SqStack S, int &x) {
    if (S.top == -1) {  //栈空，报错
        return false;
    }
    x = S.data[S.top];  //x记录栈顶元素
    return x;
}

方式二

#include<stdio.h>
#define MaxSize 10      //定义栈中元素最大个数
typedef struct {
    int data[MaxSize];  //静态数组存放栈中元素
    int  top;           //栈顶指针
} SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, int x);
bool Pop(SqStack &S, int &x);
int GetTop(SqStack S, int &x);
int main(void) {
    SqStack S;
    int x, top;
    InitStack(S);
    Push(S, 1);
    Push(S, 2);
    Push(S, 3);
    Push(S, 4);
    Push(S, 5);
    Push(S, 6);
    Push(S, 7);
    Pop(S,x);
    Pop(S,x);
    Pop(S,x);
    Pop(S,x);
    printf("x = %d\n", x);
    top = GetTop(S, x);
    printf("top = %d\n", top);
    if (!StackEmpty(S)) {
        Push(S, 8);
        printf("x = %d\n", x);
    }
    return 0;
}

//初始化栈
void InitStack(SqStack &S) {
    S.top = -1;     //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {  //栈空
        return true;
    } else {
        return false;
    }
}

//新元素入栈
bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) { //栈满报错
        return false;
    }
    S.data[S.top++] = x;
    return true;
}

//出栈操作
bool Pop(SqStack &S, int &x) {
    if (S.top == -1) {  //栈空，报错
        return false;
    }
    x = S.data[--S.top];
    return true;
}

//读取栈顶元素
int GetTop(SqStack S, int &x) {
    if (S.top == -1) {  //栈空，报错
        return false;
    }
    x = S.data[S.top];  //x记录栈顶元素
    return x;
}

共享栈

两个栈共享同一片空间，栈满的条件是top0+1 = top1

#define MaxSize 10  //定义栈中元素的最大个数
typedef struct {
    int data[MaxSize];  //静态数组中存放栈中元素
    int top0;           //0号栈栈顶指针
    int top1;           //1号栈栈顶指针
} ShStack;

int main(void) {
    ShStack S;
    InitStack(S);
    return 0;
}

//初始化栈
void InitStack(ShStack &S) {
    S.top0 = -1;    //初始化栈顶指针
    S.top1 = MaxSize;
}