数据结构与算法（五）栈

一.定义：

栈是限定仅在表尾进行插入或删除操作的线性表，因此，对栈来说，表尾端具有其特殊含义，称为栈顶（top），表头端称为栈底（bottom）。不含元素的空表称为空栈。

栈是重要的线性结构之一，从数据结构的角度来说，栈也是线性表

在理解栈的含义要注意：

首先，它是一个线性表，也就是说栈元素具有线性关系，是一对一的，即是前驱后继关系，只不过它是一种特殊的线性表。定义中所说的在线性表的表尾进行插入删除操作，这里的表尾指的是栈顶，而不是栈底。

二.对栈的操作：

栈的插入操作，叫做进栈（push），也称为压栈，入栈，类似子弹上膛；

栈的删除操作，叫做出栈（pop）。

假设栈 ，则称 ​​​​​​​为栈底元素，为栈顶元素。栈中元素按​​​​​​​ ​​的次序进栈​​，出栈时的第一个元素应为栈顶元素。换句话说，栈的修改是按照先进后出的原则进行的​；因此，栈又被称为后进先出（last in first out）的线性表（简称LIFO结构）。

三.栈的抽象数据类型

栈的数据元素类型在应用程序内定义，并称插入元素的操作为入栈，删除栈顶元素的操作为出栈。

四.栈的表示和实现

和线性表类似，栈也有两种存储表示方法。

1.顺序栈：

即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，我们先来看看栈的定义：

typedef int SElemType;//SElemType 类型根据实际情况而定，这里设定为int
typedef struct
{
    SElemType data[MAXSIZE];
    int top;//栈顶指针
}SqStack;

由于栈在使用过程中所需要的最大空间的大小很难估计，因此，一般来说，在初始化空栈是不应限定栈的最大容量；一个合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够大时，再逐渐扩大；因此，我们可以设定俩个变量，STACK_INIT_SIZE(存储空间初始分配量)，STACKINCREMENT(存储空间分配增量)，并可以做为顺序栈的定义：

typedef struct
{
    SElemType * base;//栈底指针
    SElemType * top;//栈顶指针
    int stacksize;//指示栈当前可以使用的最大容量
}SqStack;

这里我们将StackSize设定为5；

进栈操作（Push）：

然后我们来看看具体的代码实现过程：

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

出栈操作（Pop）：

Status Pop(SqStack *S,SElemType *e)//若栈不空，则删除S的栈顶元素，e作为返回值
{
    if(S->top == -1)
        return ERROR;

    *e=S->data[S->top];//将要删除的栈顶元素赋值给e
    S->top--;//栈顶指针减一
    return OK;
}

因为两者的操作（进栈，出栈）都没有涉及任何循环语句，所以时间复杂度为O(1)。