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

1、栈 (stack)

• 很多类似软件，比如 Word、Photoshop 等文档或图像编辑软件中，都有撤销操作，其实就是用栈这种方式来实现的
• 我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。
• 栈又称为后进先出 (Last In First Out) 的线性表，简称 LIFO 结构
  栈的插入操作: 叫做进栈，也称压栈、入栈
  栈的删除操作: 叫做出栈，也有的叫做弹栈

1.1、栈的抽象数据类型

1.2、栈的顺序存储结构及实现

• 栈的顺序存储结构用数组来实现，下标为 0 的一端作为栈底
• 若存储栈的长度为StackSize，则栈顶位置 top 必须小于 StackSize
• 当栈存在一个元素时，top 等于 0，因此通常把空栈的判定条件定为 top 等于 -1
• 栈的结构定义

typedef int Status; 
typedef int SElemType;   /* SElemType类型根据实际情况而定，这里假设为int */

/* 顺序栈结构 */
typedef struct
{
      SElemType data[MAXSIZE];
      int top;         /* 用于栈顶指针 */
}SqStack;

1.2.1、进栈操作

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

1.2.2、出栈操作

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ 
        if(S->top==-1)
                return ERROR;
        *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */
        S->top--;               /* 栈顶指针减一 */
        return OK;
}

• 栈的顺序存储结构不涉及任何循环语句，因此时间复杂度均为O(1)

1.3、栈的链式存储结构及实现

• 栈只有栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？ 头部
  
• 对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间
• 对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是 top=NULL 的时候
• 链栈的结构代码如下

/* 链栈结构 */
typedef struct StackNode
{
        SElemType data;
        struct StackNode *next;
}StackNode,*LinkStackPtr;


typedef struct
{
        LinkStackPtr top;
        int count;
}LinkStack;

1.3.1、进栈操作

/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
        s->data=e; 
        s->next=S->top; /* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
        S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */
        S->count++;
        return OK;
}

1.3.2、出栈操作

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
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);                    /* 释放结点p */        
        S->count--;
        return OK;
}

1.3.3、小结

• 链栈的进栈 push 和出栈 pop 操作都很简单，没有任何循环操作，时间复杂度均为 O(1)
• 对比一下顺序栈和链栈，它们在时间复杂度上是一样的，均为 O(1)
• 对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便；而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制
• 如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是使用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些