数据结构与算法(八)-- 栈

2020/4/10 0:15:29 人评论 次浏览 分类:学习教程

                                                                栈

栈的定义:(Stack)只允许在一端进行插入或者删除操作的线性表。

  S = (a1,a2,a3,a4,a5)

                                                                                                         ------------------------->入栈顺序   先进后出

栈的基本操作:InitStack(& S):初始化一个空栈S

                         StackEmpty(S):判断栈空 ;

Push(&S): 进栈(压栈) ,若栈S未满,将x加入成为新栈的栈顶元素top,top需要上移一位

Pop(& S):出栈(弹出),若栈非空,则弹出栈顶元素,用x返回,top需要向下移动一位

GetTop(S, &x):读取栈顶元素,非空则用x返回top指向的元素。

栈的顺序存储结构

#define MaxSize 50
tydef struct{
    ElemType data[MaxSize];    //栈的数据域
    int top;    //栈顶指针
}SqStack;

栈空条件:S.top == -1(栈的初始位置)                   栈满条件:S.top=MaxSize-1                    求栈长:S.top+1

栈的初基本操作

void InitStack(SqStack &s){        //初始化
    S.top == -1;
}

bool StackEmpty(SqStack s){    //判空
    if(s.top == -1)
        return true;
    else
        return false;
}

bool Push(SqStack &s, ElemType x){    //进栈操作
    if(s.top == MaxSize-1)        //栈满溢出
        return false;
    s.data[++top] = x;        //插入到栈顶,同时栈顶指针上移
    return true;
}

bool Pop(SqStack &s, ElemType &x){
    if(s.top == -1)
        return false;
    x = s.data[top--];       //x获取栈顶元素,同时top指针下移
    return true;
}

bool GetTop(SqStack &s, ElemType &x){
    if(s.top == -1)
        return false;
    x=data[s.top];    
    return true;
}

共享栈:将两个栈底设置在共享空间的两端,top0的初始位置设在1号栈的栈顶,top1的初始位置设置在0号栈的栈顶也在1号栈的底部,最大存储空间为原来栈的一半,将top0指针与top1指针相碰时,栈满。

判空:0号栈:top == -1       1号栈:top = MaxSize-1                     栈满:top1-top == 1;

共享栈的优点:存储时间复杂度为O(1),空间利用率高。

栈的链式存储:链栈        通过指针将栈内部元素进行链接

top->next指向栈顶元素

typedef strcut LinkNode{      //定义链栈的结点
    ElemType data;
    struct LinkNode *next;
}LinkedStackNode,*LinkedStack;

typedef struct LStack{
    LinkedStackNode base;    //定义栈底指针
    LinkedStackNode top;     //定义栈顶指针
}LStack;

链栈的所有操作都在表头(栈顶)进行。top -> next

链栈的基本操作:

LinkedStack Init_LinkedStack(){    //初始化链栈,为空栈
     //根据top指针的移动动态分配结点空间
    LinkedStack top = (LinkedStackNode *)malloc(sizeof(Node));   
    if(top ! = NULL)
        top ->next = null;   //开始为栈顶,指向空、
    return top;
}    

bool LinkeStack_Empty(LinkedStack top){    //判空
    if(top->next == null){
        return true;
    }else
        return false;
}

//入栈:将元素x插入链栈栈顶,设置头结点指针域指向新插入位置的,设置为栈顶元素
bool Push_LinkedStack (LinkedStack top ,ElemType x){
    LinkedStackNode *node = (LinkedStackNode)malloc (sizeof(LinkedStackNode));
    if(node == null)
        return false;
    else{
        node->data = x;
        node->next = top->next;   //设置为栈顶
        top ->next = node;    //原栈顶指向新结点 
    return true;
    }
}

//出栈:删除栈顶数据元素,通过x返回被删元素的数据值,设置top指向链栈中的下一个元素
int Pop_LinkedStack(LinkedStack top, ElemType &x){
    LinkedStackNode *node;       //不用分配空间,已存在目标结点
    if(top -> next == null){
        return 0;
    }else{
        node = top->next;    //找到栈顶结点
        *x = node->data;
        top->next = node->next;    //被删元素的指向赋值给top;
        free(node);        //释放结点空间
        return x;
    }
}

//读取栈顶元素
int Get_LinkedStack(LinkedStack top, ElemType &x){
    if(top->next == null)
        return 0;
    else{
        x = top->next->data;    //栈顶元素的数据域赋值给x
        return 1; 
    }
}

 

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->