//數組堆疊的實現
#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;
}