07.栈(一)栈的存储结构及操作，07存储结构操作

07.栈(一)栈的存储结构及操作，07存储结构操作

一、栈 1.栈(stack)：是限定仅在表尾进行插入和删除操作的线性表。其中，允许插入和删除的一端被称为栈顶(top)，另一端被称为栈底(bottom)，不含任何数据元素的栈被称为空栈。栈又被称为后进先出(Last In First Out)的线性表，简称LIFO结构。     栈的插入操作为进栈，栈的删除操作为出栈。 2.栈的抽象数据类型 ADT 栈(stack) Data     同线性表。元素具有相同类型，相邻元素具有前驱和后继关系。 Operation     InitStack(*S)：初始化操作，建立一个空栈S。     DestoryStack(*S)：若栈存在，则销毁它。     ClearStack(*S)：将栈清空。     StackEmpty(S)：若栈为空，返回true，否则返回false。     GetTop(S,*e)：若栈存在且非空，用e返回S的栈顶元素。     Push(*S,e)：若栈S存在，插入新元素e到栈S中并称为栈顶元素     Pop(*S,*e)：删除栈S中栈顶元素，并用e返回其值     StackLength(S)：返回栈S的元素个数 endADT
二、栈的存储结构 1.栈的顺序存储结构及实现(复杂度均为O(1)) (1)栈顺序结构定义 #define OK 1 #define ERROR 0 typedef int SElemType;    //SElemType类型根据实际情况而定，这里假设为int typedef struct {     SElemType data[MAXSIZE];    //栈存储空间大小MAXSIZE     int top;    //用于栈顶指针 }SqStack; (2)进栈操作(从栈顶插入一个元素) 算法思路： a.判定是否栈满; b.栈顶加1; c.将元素插入到 实现：插入元素e为新的栈顶元素

Status Push(SqStack *S,SElemType e)
{
    if(S->top==MAXSIZE-1)    //栈顶=MAXSIZE-1，即数组的最后一个存储位置，说明栈满
    {
        return ERROR;
    }
    S->top++;    //栈顶加1
    S->data[S->top]=e;    //将元素入栈
    return OK;
}

(3)出栈操作(从栈顶删除一个元素) 算法思路： a.判定栈是否为空; b.将栈顶元素保存到指针变量e所指向的存储位置中; c.栈顶减1. 实现：若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR

Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)    //空栈
    {
        return ERROR;
    }
    *e=S->data[S->top];
    S->top--;
    return OK;
}

(4)两栈共享空间     栈的顺序存储只准栈顶进出元素，所以不存在线性表插入和删除时需要移动大量的元素，但是有个缺陷是必须事先确定数组存储空间大小。当两个栈数据类型一样是，我们可以将两个栈所开辟的空间共享使用。 
A.思想：将栈1的栈底，即为共享空间的栈底(下标为0);另一个栈的栈底为共享栈的末端(下标为数组长度n-1处)，其中top1和top2是栈1和栈2的栈顶指针。对于共享栈，若栈2是空栈(top2=n)，栈1的top1=n-1,说明栈1满了；若栈1是空栈(top=-1),栈2的top2=0，说明栈2满了。即共享栈满条件：top1+1==top2。 B.共享栈空间结构 typedef struct {     SElemType data[MAXSIZE];    //定义一个数组存储空间，大小为MAXSIZE即为栈大小     int top1;    //栈1栈顶指针     int top2;    //栈2栈顶指针 }SqDoubleStack; C.共享栈元素入栈操作 算法思路： a.首先判断共享栈是否栈满; b.通过stackNumber参数判断插入哪个栈     若为栈1，则栈顶top1增1，再将元素e入栈;若为栈2，则栈顶top2减1，在将元素e入栈。 实现：插入元素e为新的栈顶元素

Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
    if(S->top1+1==S->top2)    //判定共享栈是否栈满(top1+1=top2)
    {
        return ERROR;
    }
    if(stackNumber==1)        //栈1有元素进栈,栈顶top1加1
        S->data[++S->top1]=e;
    else if(stackNumber==2)
        S->data[--S->top2]=e;    //栈2有元素进栈，栈顶top2减1
    return OK;
}

D.共享栈元素出栈操作 算法思想： a.判断哪一个栈; b.若为栈1，则先将元素赋值给指针变量e指向的空间位置，再栈顶top1减1;     若为栈2，则先将元素赋值给指针变量e指向的空间位置，再栈顶top2增1; 实现：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR

Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
    if(stackNumber==1)    //若删除元素属于栈1
    {
        if(S->top1==-1)     //空栈
                  return ERROR;
        *e=S->data[S->top1--];    //将元素赋值给e，栈顶再减1
    }
    else if(stackNumber==2)//若删除元素属于栈1
    {
           if(S->top2==MAXSIZE)     //空栈
                  return ERROR;
        *e=S->data[S->top2++];    //将元素赋值给e，栈顶再减1  
    }
    return OK;
}

---

升华笔记1： 1.栈的顺序存储结构是通过数组来实现的，下标为0为栈底，因为首元素都哦存在栈底变化最小。当栈存在一个元素时，栈顶top为0，如果为空栈则top=-1,这也是判断栈是否为空栈的条件。另外，要区别存储栈的长度StackSize(MAXSIZE)和存储位置。 2.两栈共享空间只适用于元素数据类型相同的两个栈，且入栈是先修改栈顶再元素入栈;出栈是先元素出栈再修改栈顶。

---

2.栈的链式存储结构及实现

(1)链栈的结构 //链结点:包含数据域和指针域 typedef struct StackNode {     SElemType data;                //数据域     struct StackNode *next;    //指针域 }StackNode,*LinkStackPtr; //链栈结构 typedef struct LinkStack {     LinkStackPtr top;    //链栈头结点     int count;                 //结点个数 }LinkStack; (2)链栈的进栈操作 算法思想： a.先为新结点s开辟一段空间，空间的大小为结点结构大小; b.将要插入的元素值e赋值给新结点s的数据域; c.将原来的栈顶元素赋值给新结点s的后继 d.使栈顶指针指向新结点e e.链栈元素增1 实现：插入元素e为新的栈顶元素

Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));    //开辟一个新的结点空间，大小为结构体StackNode大小
    s->data=e;        //将元素e赋值给新结点s的数据域
    s->next=S->top;//把当前的栈顶元素赋值给新结点的直接后继
    S->top=s;    //将新的结点s赋值给栈顶指针
    S->count++;//链栈元素数目加1
    return OK;
}

(3)链栈的出栈操作 算法思想： a.首先判定链栈是否为空栈 b.将栈顶指针指向元素数据域数据赋值给e c.将栈顶指针原先指向的元素赋值给p d.再将栈顶指针指向后一个结点，释放p e.链栈元素数目减1 实现：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK

Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(StackEmty(*S))    //若空栈
        return ERROR;
    *e=S->top->data;    //将栈顶元素数据赋值给指针变量e指向空间
    p=S->top;                //将栈顶指针指向的结点(栈顶元素)赋值给p
    S->top=S->top->next;    //使得栈顶指针下移一位，即此时栈顶指针指向后一个结点
    free(p);    //释放结点p
    S->count;    //链栈元素数目减1
    return OK;
}

3.性能分析 (1)时间复杂度:栈的顺序结构和链式结构均为O(1); (2)空间复杂度     栈的顺序结构只有数据域，空间复杂度小，但事先需要确定一个固定的长度，可能会存在内存空间浪费问题；     栈的链式存储结构每个元素具有数据域和指针域，空间复杂度稍复杂，同时也增加了一些内存开销，但对于栈的长度无限制。 (3)如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈；反之，如果它的变化在可控范围内，建议使用顺序栈性能会更高些。