/*
顺序栈（C++版）
*/
#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXSIZE 100
typedef struct{
  int *base;
  int *top;
  int stacksize;
}SqStack;

void InitStack(SqStack &S){
    S.base = new int[MAXSIZE];
    if(!S.base){
        printf("创建失败");
        return;
    }
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return ;
}

// 入栈
void Push(SqStack &S, int e){
    if((S.top-S.base)==S.stacksize){
        printf("栈满\n");
        return ;
    }
    *S.top = e;
    S.top++;
    return ;
}
/*
注意：栈顶指针top 始终指向栈顶元素的上一个位置！！！
*/
// 出栈
void Pop(SqStack &S, int &e){
    if(S.base==S.top){
        printf("栈空\n");
        return ;
    }
    S.top--;
    e = *S.top;
    return ;
}

// 取栈顶元素（不删除）
void GetTop(SqStack &S, int &e){
    if(S.top==S.base){
        printf("栈空\n");
        return ;
    }
    e = *(S.top-1);
    return ;
}
int main()
{
    int e;
    SqStack S;
    InitStack(S);
    // 出栈
    Pop(S, e);
    // 取出栈顶元素
    GetTop(S, e);

    // 入栈
    Push(S, 1);
    Push(S, 2);
    Push(S, 3);
    Push(S, 4);
    Push(S, 5);
    Push(S, 6);

    GetTop(S, e);
    printf("%d\n", e);

    Pop(S, e);
    printf("%d\n", e);

    GetTop(S, e);
    printf("%d\n", e);
    return 0;
}

/*
链栈（C++版）
*/
#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct StackNode{
    int data;
    StackNode *next;
}StackNode, *LinkStack;

void InitStack(LinkStack &S){
    S = NULL;
    return ;
}

// 入栈
void Push(LinkStack &S, int e){
    LinkStack p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return ;
}

// 出栈
void Pop(LinkStack &S, int &e){
    if(S==NULL){
        printf("栈空\n");
        return ;
    }
    e = S->data;
    LinkStack p = S;
    S = S->next;
    delete p;
    return ;
}

// 取栈顶元素（不删除）
void GetTop(LinkStack S, int &e){
    if(S==NULL){
        printf("栈空\n");
        return ;
    }
    e = S->data;
    return ;
}

int main()
{
    int e;
    LinkStack S;
    // 初始化
    InitStack(S);
    // 出栈
    Pop(S, e);
    // 取栈顶元素
    GetTop(S, e);

    // 入栈
    Push(S, 1);
    Push(S, 2);
    Push(S, 3);
    Push(S, 4);
    Push(S, 5);
    Push(S, 6);

    GetTop(S, e);
    printf("%d\n", e);

    Pop(S, e);
    printf("%d\n", e);

    GetTop(S, e);
    printf("%d\n", e);

    return 0;
}