首页 > 代码库 > 07.栈(一)栈的存储结构及操作

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

2024-10-28 22:41:02   212人阅读

一、栈
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=http://www.mamicode.com/e;        //将元素e赋值给新结点s的数据域>
(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)如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈；反之，如果它的变化在可控范围内，建议使用顺序栈性能会更高些。

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






























        

            
                
                  
                
                

                    联系

                    我们