栈（Stack）是只允许在一端进行插入或删除操作的线性表。其特点是他的元素后进先出（Last In First Out （LIFO））。
在实现栈的时候需要设置一个成员用于存放栈顶游标（top）（储存栈顶元素的位置信息），有的把最后一个元素的下标作为栈顶记录。

顺序栈

设顺序栈为S,需要注意的如下：

入栈：
栈满时 S.top-S.base==S.stacksize

出栈：
栈空时 S.top == S.base

取栈顶元素：
++会改变自身值，而-1不会改变，故返回*(S.top-1);

顺序栈特点：
由于顺序栈和顺序表一样， 受到最大空间容量的限制， 虽然可以在 “满员” 时重新分配空间扩大容量， 但工作量较大，因此在应用程序无法预先估计栈可能达到的最大容量时，应该尽量避免使用顺序栈。
 

#include
#include

#define MAXSIZE 100
typedef int SElemType;

//顺序栈的存储结构
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;            //可用最大容量
}SqStack;

//初始化
void InitStack(SqStack &S)
{
    S.base = new SElemType[MAXSIZE];
    if (!S.base) exit;    
    S.top = S.base;
    S.stacksize = MAXSIZE;
}

//入栈
int Push(SqStack &S, SElemType e)
{
    if (S.top - S.base == S.stacksize) return 0;    //栈满

    *S.top = e;
    S.top++;
    return 1;
}

//出栈
int Pop(SqStack &S, SElemType &e)
{
    if (S.top == S.base) return 0;    //栈空

    S.top--;
    e = *S.top;
    return 1;
}

//取栈顶元素
SElemType GetTop(SqStack S)
{
    if (S.top != S.base)     //非栈空时返回
        return *(S.top-1);   //++会改变指针自身值，而-1不会改变
}

//遍历输出栈
void printStack(SqStack S)
{
    printf("栈底：");
    SElemType *p = S.base;
    while (p!=S.top)
    {
        printf("%d ", *p);
        p++;
    }
    printf("\n");
}

int main()
{
    SqStack S;
    int e;
    InitStack(S);
    printf("请输入一个要入栈的元素（-1表示结束）：");
    scanf("%d",&e);
    while (e!=-1)
    {
        Push(S,e);
        printf("请输入一个要入栈的元素（-1表示结束）：");
        scanf("%d", &e);
    }
    printStack(S);
    printf("出栈测试：");
    Pop(S, e);
    printStack(S);

    printf("取栈顶元素测试：");
    e=GetTop(S);
    printf("取出的栈顶元素为：%d\n",e);
}
 

链栈

由于栈的主要操作是在栈顶插入和删除， 显然以链表的头部作为栈顶是最方便的，且不需要附加一个头结点。

初始化：

栈顶指针S置空即可。

#include
#include

#define MAXSIZE 100
typedef int SElemType;

//链栈的存储结构
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

//初始化
void InitStack(LinkStack &S)
{
    S = NULL;    //构造一个空栈，栈顶指针置空即可
}

//入栈
int Push(LinkStack &S, SElemType e)
{
    //链栈不需要判断栈满

    StackNode *p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return 1;
}

//出栈
int Pop(LinkStack &S, SElemType &e)
{
    if (S==NULL) return 0;    //栈空

    StackNode *p = S;
    e = S->data;
    S = S->next;
    delete p;
    return 1;
}

//取栈顶元素
SElemType GetTop(LinkStack S)
{
    if (S!=NULL)     //非栈空时返回
        return S->data;   
}

//遍历输出栈
void printStack(LinkStack S)
{
    printf("栈顶->");
    StackNode *p = S;
    while (p!=NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkStack S;
    int e;
    InitStack(S);
    printf("请输入一个要入栈的元素（-1表示结束）：");
    scanf("%d",&e);
    while (e!=-1)
    {
        Push(S,e);
        printf("请输入一个要入栈的元素（-1表示结束）：");
        scanf("%d", &e);
    }
    printStack(S);
    printf("出栈测试：");
    Pop(S, e);
    printStack(S);

    printf("取栈顶元素测试：");
    e=GetTop(S);
    printf("取出的栈顶元素为：%d\n",e);
}