数据结构:详细讲解栈的定义、栈的操作

举报
高彬滔 发表于 2023/04/02 22:12:22 2023/04/02
【摘要】 1.栈的定义栈(stack):是只允许在一端进行插入或者删除操作的线性表(即后进先出,大概可以理解为吃饱了吐出来)空栈:不含元素的空标配栈顶:表尾端栈底:表头端进栈顺序:a1->a2->a3->a4->a5出栈顺序:a5->a4-a3->a2->a12.对比线性表和栈基本操作2.1 线性表的基本操作InitList(&L):初始化表。构造一个空的线性表L,分配内存空间DestoryList(...

1.栈的定义

栈(stack):是只允许在一端进行插入或者删除操作的线性表(即后进先出,大概可以理解为吃饱了吐出来)

  • 空栈:不含元素的空标配
  • 栈顶:表尾端
  • 栈底:表头端

image.png

  • 进栈顺序:a1->a2->a3->a4->a5
  • 出栈顺序:a5->a4-a3->a2->a1

2.对比线性表和栈基本操作

2.1 线性表的基本操作

  • InitList(&L):初始化表。构造一个空的线性表L,分配内存空间
  • DestoryList(&L):销毁操作。销毁线性表,并且释放线性表L所占用的空间
  • ListInsert(&L,i,e):插入操作,在表L中的第i个位置上插入指定元素e
  • ListDelete(&L,i,e):删除操作,删除表L中的第i个位置的元素,并且用e返回删除元素的值
  • LocateElem(L,e):按值查找操作,在表L中查找具有给定关键字值的元素
  • GetElem(L,i):按位查找操作,获取表L中第i个位置的元素的值

2.2 栈的基本操作

  • InitStack(&S):初始化栈,构造一个空栈S,分配内存空间
  • DestoryStack(&S):销毁栈,销毁并释放栈S所占用的内存空间
  • Push(&S,x):进栈,若栈S未满,则将x加入使之成为新的栈顶
  • Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回
  • GetTop(S,&x):读栈顶元素,若栈S非空,则用x返回栈顶元素

其他常见操作: StackEmpty(S):判断一个栈S是否为空,若S为空,则返回true,否则返回false

3.顺序栈

image.png

3.1顺序栈的定义

#define MaxSize 10           //定义栈中元素的最大个数          
typedef struct{
    ElemType data[MaxSize];   //静态数组存放栈中的元素
    int top;      //栈顶指针
}SqStack;         //结构体重命名

声明一个顺序栈后就会在内存中分配一整片连续的空间,其中内存大小为:MaxSize*sizeof(ELemType)

void testStack(){
    SqStack S;   //声明一个顺序栈
}

3.2栈的初始化操作

由于栈顶指针top需要指向此时栈顶元素,所以让top指向0是不合理的,可以初始化让top指向-1;判断一个栈是否为空,即判断S.top是否等于-1

初始化栈

void Inittack(SqStack){
    SqStack S;   //声明一个顺序栈
    S.top=-1;
}

判断栈空

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

3.3进栈操作

分析:

  1. 判断栈是否为空
  2. 栈顶指针+1
  3. 新元素入栈
bool Push(SqStack &S,ElemType x){
    if(S.top==NaxSize-1)
        return false;
    S.top+=1;
    S.data[S.top]=x;
        return true;
}

3.4出栈操作

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

3.5读栈顶元素操作

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

4.共享栈

两个栈共享同一片空间

#define MaxSize 10           //定义栈中元素的最大个数          
typedef struct{
    ElemType data[MaxSize];   //静态数组存放栈中的元素
    int top0;     //0号栈栈顶指针
    int top1;     //1号栈栈顶指针
}SqStack;         //结构体重命名

初始化栈:

void InitStack(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}

5.链栈的定义

  • 进栈/出栈都只能在栈顶一段进行
  • 链头作为栈顶
typedef struct Linknode{
    ElemType data;           //数据域
    struct Linknode *next;   //指针域
}*LiStack                    //栈类型定义
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。