//数组栈的实现
#include<stdio.h>
 
#define MaxSize 50
 
typedef struct Stack_Array{
	int data[MaxSize];
	int top;
}Sqstack,*pSqstack;
 
void Initstack();					//初始化
int Isempty();						//判断栈空
int Push();						//入栈
int Pop();						//出栈
int Gettop();						//get栈顶元素
 
int main(void)						//测试
{
	int val;
	Sqstack s1;
	pSqstack ps1=&s1;
	Initstack(&s1);					//初始化
 
	if(Isempty(&s1))				//判断栈空
		printf("栈为空！\n");
	else printf("栈不为空！\n");
 
	printf("输入压栈元素的值");		//压栈1
	scanf("%d",&val);
	Push (ps1,&val);
 
	printf("输入压栈元素的值");		//压栈2
	scanf("%d",&val);
	Push (ps1,&val);
 
	if(Isempty(ps1))				//判断栈空
		printf("栈为空！\n");
	else printf("栈不为空！\n");
 
	if(Gettop(ps1,&val))			//GET栈顶元素
		printf("栈顶值为%d\n",val);
	else printf("栈顶元素查找失败！\n");
 
	if(Pop(ps1,&val))				//出栈
		printf("出栈成功，出栈元素为%d\n",val);
	else printf("出栈失败！\n");
 
	return 0;
}
//初始化
void Initstack (pSqstack ps1)
{
	ps1->top=-1;
	return;
}
//判断栈空
int Isempty(pSqstack ps1)
{
	if(ps1->top==-1)
		return 1;
	else return 0;
}
//若栈不满，则进行压栈
int Push(pSqstack ps1,int *val)//*val:接受一个地址(int *(&val))
{
	if(ps1->top==MaxSize)
		return 0;
	else
	{
		ps1->top++;
		ps1->data[ps1->top]=*val;//这里传递的是值，这里的*val是*(&val),&val是由主调函数输入
                //也可写作ps1->data[++ps1->top]=*val; 一定是++ps1->top
		return 1;
	}
}
//若栈不空，则进行出栈，用val返回栈顶元素
int	Pop(pSqstack ps1,int *val)
{
	if(Isempty(ps1))
		return 0;
	else
	{
		*val=ps1->data[ps1->top--];
		return 1;
	}
}
//get栈顶元素，用val返回栈顶元素
int Gettop(pSqstack ps1,int *val)
{
	if(Isempty(ps1))
		return 0;
	else 
	{
		*val=ps1->data[ps1->top];
		return 1;
	}
}

//栈的链式存储实现
#include <stdio.h>
#include <stdlib.h>

#define Stack_Init_Size 10 // 初始化栈的最大长度
#define StackIncrement 10 // 若栈最大空间不够时，需要增加的长度
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *base; // 栈底指针
    ElemType *top; // 栈顶指针
    int stack_size; // 栈的最大长度
} SqStack;

// 初始化栈
Status InitStack(SqStack *S) {
    // 分配初始空间
    S->base = (ElemType *) malloc(Stack_Init_Size * sizeof(ElemType));
    if (!S->base) {
        exit(0);
    }
    S->top = S->base; /// 栈顶与栈底相同
    S->stack_size = Stack_Init_Size; // 栈的最大长度等于初始长度
    return 1;
}

// 判断栈是否为空，只需要判断栈顶指针与栈底指针是否相同即可
Status EmptyStack(SqStack *S) {
    return S->base == S->top;
}

// 获取栈的实际长度，栈顶减去栈底指针即为栈的长度
Status LengthStack(SqStack *S) {
    if (S->top == S->base) {
        return 0;
    }
    return (Status) (S->top - S->base);
}

// 获取栈顶的元素，参数e用来存放栈顶的元素
Status GetTopStack(SqStack *S, ElemType *e) {
    if (S->top == S->base) {
        return 0;
    } 
    *e = *(S->top - 1);
    return 1;
}

// 进栈，参数e是要进栈的元素
Status PushStack(SqStack *S, ElemType e) {
    // 若栈的最大长度不会够用时，重新开辟，增大长度
    if (S->top - S->base >= S->stack_size) {
        S->base = (ElemType *)realloc(S->base, (S->stack_size + StackIncrement) * sizeof(ElemType));
        if (!S->base) {
            return 0;
        }
        // 栈顶指针为栈底指针加上栈之前的最大长度
        S->top = S->base + S->stack_size;
        // 栈当前的最大长度等于栈之前的最大长度与增加的长度之和
        S->stack_size += StackIncrement;
    }
    *S->top++ = e; // 先赋值，后栈顶指针上移
    return 1;
}

// 出栈，参数e用来存放出栈的元素
Status PopStack(SqStack *S, ElemType *e) {
    if (S->base == S->top) {
        return 0;
    }
    *e = *--S->top; // 栈顶指针先下移，后赋值
    return 1;
}

// 销毁栈，释放栈空间，栈顶栈底指针置为NULL，长度置为0
Status DestroyStack(SqStack *S) {
    free(S->base);
    S->base = S->top = NULL;
    S->stack_size = 0;
    return 1;
}

// 遍历栈，依次打印每个元素
Status StackTraverse(SqStack *S) {
    ElemType *p;

    if (S->top == S->base) {
        printf("Stack is NULL.\n");
        return 0;
    }
    p = S->top;
    // 由栈顶依次向下遍历
    while (p > S->base) {
        p--;
        printf("%d ", *p);
    }
    printf("\n");
    return 1;
}

int main() {
    SqStack q, *S;
    S = &q;

    int i, n, e;

    printf("Creat a NULL Stack :\n");
    InitStack(S);

    printf("input the length of the Stack :\n");
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d", &e);
        PushStack(S, e);
    }
    printf("Is the stack NULL?\n");

    if (EmptyStack(S)) {
        printf("Yes!\n");
    } else {
        printf("No!\n");
    }
    printf("The length of stack is %d.\n", LengthStack(S));

    printf("The stack is :\n");
    StackTraverse(S);

    e = GetTopStack(S, &e);
    printf("The top data is %d.\n", e);

    printf("input the data to the stack :\n");
    scanf("%d", &e);
    PushStack(S, e);
    printf("The new stack is :\n");
    StackTraverse(S);

    printf("Delete the top data : ");
    e = PopStack(S, &e);
    printf("%d\n", e);

    printf("The new stack is :\n");
    StackTraverse(S);

    printf("Destroy the stack :\n");
    DestroyStack(S);
    StackTraverse(S);

    return 0;
}