栈的基本内容

一  栈的定义

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

通常把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称为LIFO结构（Last In First Out）。

栈首先是一个线性表，也就是说，栈的元素具有线性关系，既前驱后继关系，在线性表中的表尾在栈中指的是栈顶。

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

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

二 栈的顺序储存结构

首先来看栈的结构定义：

typedef int selemtype;//类型根据实际需要而定，现在先定义为int类型
typedef struct
{
    selemtype data[maxsize];
    int top;//用于栈顶指针
}sqstack;

之后进行进栈的操作：

status push(sqstack*s,selemtype e)
{
    if(s->top==maxsize-1)//栈满
    {
        return error;
    }
    s->top++;//栈顶指针增加一
    s->data{s->top}=e;//将新插入的元素赋值给栈顶空间
    return ok;
}

最后出栈操作：

status pop(sqstack*s,selemtype e)
{
    if(s->top==-1)//栈满
    {
        return error;
    }
    *e=s->data[s->top];//将要删除的栈顶元素赋值给e
    s->top--;//栈顶指针减一
    return ok;
}

三 两栈共享空间

数组有两个端点，两个栈有两个栈底，让一个栈的栈底成为数组的始端，既下标为0处，另一个成为数组的末端，既下标为n-1处。两个栈增加新元素，两个端点就向中间延伸。

那什么时候栈满呢？想想极端情况，若栈2 是空栈，栈1 的top1等于n-1时，就是栈一满了。反之，当栈1 为空栈时，top2等于0时，为栈2 满。两个栈见面时，也就是两个指针之间相差1 时，既top1+1=top2为栈满。

四 栈的链式储存结构

同链表类似，链式储存结构的优点是基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那么此时的计算机操作系统基本上面临崩溃的边缘，而不是这个链式栈是否溢出的问题。

通常情况下都将栈顶放在链表的头部，这样头指针的作用基本上失去了意义，对于链式栈来说是不需要头结点的。

对于空栈来说，链表的原定义是头指针指向空，那么链式栈的空其实就是top=NULL的时候。

链式栈的进栈和出栈的操作与链表的插入删除操作基本一样，链表那里打好了基础链式栈基本就没有问题。

进栈操作：

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;
}

出栈操作：

Status pop(linkstack*s,selemtype*e)
{
    linkstackptr s=(linkstackptr)malloc(sizeof(stacknode));
    *e=S->top->data;
    p=S->top;//将栈顶结点赋值给p
    S->top=S->top->next;//使栈顶的指针移向下一位，指向后一结点
    free(p);//释放结点p
    S->count--;
    return OK;
}

链式栈的进栈和出栈操作都很简单，没有任何的循环操作，时间复杂度均为o（1）；

五 栈的应用

栈的应用主要是在递归的运用，在使用递归函数时，编译器使用栈实现递归，我们在平常调试代码的时候是注意不到的，实际上编译器进行函数的递归调用的时候就是使用了栈来存储和查找数据最后来进行汇总的。

栈还有一个应用就是四则运算表达式求值，既后缀（逆波兰）表示法定义，后缀表达式不同于我们平常的正常思维，在这里说不清楚，附上链接单独讲后缀表达式。https://blog.csdn.net/weixin_44015865/article/details/85098378