栈：限定仅在表尾进行插入和删除操作的线性表。

栈的定义

允许插入和删除的一段称为栈顶，另一端称为栈底。

不含任何数据元素的栈称为空栈。

后入先出(Last In First Out)线性表，简称LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。

栈的删除操作，叫做出栈，也称弹栈。

3个元素1，2，3依次进栈，有5种可能的出栈次序：

1、2、3进，再3、2、1出，次序为321
1进，1出，2进，2出，3进，3出，次序为123
1进，2进，2出，1出，3进，3出，次序为213
1进，1出，2进，3进，3出，2出，次序为132
1进，2进，2出，3进，3出，1出，次序为231

肯定不会出现312的情况，因为若3先出栈，则3必曾进过栈，则1、2已经进栈了，则2在1之上，不可能1先出栈

栈的抽象数据类型

mark

栈的顺序存储结构

定义一个栈顶指针top来表示栈顶在数组中的位置

结构代码

typedef int SElemType;
typedef struct
{
    SElemType data[MAXSIZE];
    int top;
}SqStack;

进栈操作

//插入元素e为新的栈顶元素
Status Push (SqStack *S,SElemType e)
{
    if (S->top == MAXSIZE-1)//是否栈满
        return ERROR;
    S->top++;
    S->data[S->top] = e;//将新插入的指针赋值给栈顶空间
    return OK;
}

出栈操作

//若栈非空，则删除栈顶元素，用e返回其值
Status Pop (SqStack *S,SElemType *e)
{
    if (S->top == -1)//空栈top值为-1
        return ERROR;
    *e = S->data[S->top];
    S->top--;
    return OK;
}

时间复杂度均为O(1)

两栈共享空间

一个栈的栈底为数组下标为0处，另一个的栈底为数组下标为n-1处

当两个指针间相差1时，即top1 + 1 = top2时为栈满(栈1满时，top1 = n-1,top2 = n;栈2满时，top1 = -1，top2 = 0)

结构代码

typedef struct
{
    SElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;

进栈操作

Status Push (SqDoubleStack *S,SElemType e,int stackNumber)
{
    if (S->top1+1 == S->top2)//栈已满，不能再push新元素
        return ERROR;
    if (stackNumber == 1)//栈1有元素进栈
        S->data[++S->top1] = e;
    else if (stackNumber == 2)//栈2有元素进栈
        S->data[--S->top2] = e;
    return OK;
}

出栈操作

Status Pop (SqDoubleStack *S,SElemType *e,int stackNumber)
{
    if (stackNumber == 1)
    {
        if (S->top1 == -1)
            return ERROR;//栈1为空栈
        *e = S->data[S->top1--];
    }
    else if (stackNumber == 2)
    {
        if (S->top2 == n)
            return ERROR;//栈2为空栈
        *e = S->data[S->top2++];
    }
    return OK;
}

通常当两个栈具有相同数据类型且空间需求有相反关系时使用这样的数据结构

栈的链式存储结构

通常将栈顶放在单链表的头部，头指针充当栈顶指针，不需要头结点。

结构代码

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;//结点总数
}LinkStack;

进栈操作

Status Push (Linkstack *S,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    
    s->data = e;
    s->next = S->top;
    S->top = s;
    S->count++;
    return OK;
}

出栈操作

Status Pop (LinkStack *S;SElemType *e)
{
    LinkStackPtr p;
    
    if (StackEmpty(*S))
        return ERROR;
    *e = S->top->data;
    p=S->top;//将栈顶结点赋值给p
    S->top = S->top->next;//栈顶指针下移一位
    free(p);
    S->count--;
    return OK;
}

如果栈的使用过程中元素变化不可预料，那么最好用链栈，反之若变化在可控范围内，则最好用顺序栈

栈的引入简化了程序设计问题，划分了不同层次，使思考范围缩小，更加聚焦于我们要解决的问题的核心。

栈的应用–递归：在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中；在退回阶段，位于栈顶的局部变量、参数、和返回地址被弹出，用于返回调用层次中执行代码的剩余部分，也就是恢复了调用状态。