目录

前言

堆栈

后缀表达式

堆栈的抽象数据类型描述

栈的顺序存储实现

（1）入栈

（2）出栈

用一个数组实现两个堆栈

堆栈的链式存储实现

（1）插入

  (2)删除

中缀表达式如何转换为后缀表达式

堆栈的其它应用:

前言

本篇总结了数据结构里有关堆栈的知识点。

堆栈

堆栈是一种线性结构，也是一个特殊的线性表。堆栈在计算机学科领域里面有广泛的用途，比如函数调用,递归,表达式求值，不要用到堆栈。那么到底什么是堆栈呢?下面让我们来看一个例子。

计算机如何进行表达式求值？

【例】算术表达式 5+6/2-3*4。

  • 由两类对象构成的:

运算数，如5、6、2、3、4;  运算符号，如：+、-、*、/。

  • 不同运算符号优先级不一样

表达式到底为什么复杂呢?因为我们的运算符号往往是放在两个运算数当中，我们往往看到运算符号的时候就开始做计算，这个时候只知道一个运算数，另一个运算数在运算符号的后面，但是紧挨在运算符号后面的那个运算数也不一定是参与这个运算的运算数。

如5+6，6不是用来与5做加法的，6要先参与后面的除法运算。正是由于表达式把运算符号放在两个运算数当中，所以求值就变得比较困难了。反过来，碰到运算符号的时候，我们已经知道两个运算数了，那么这样计算就会比较简单了。

后缀表达式

中缀表达式：运算符号位于两个运算数之间。如：a+b*c-d/e

后缀表达式:运算符号位于两个运算数之后。如:abc*+de/-

明显可以看到，计算机用 后缀表达式 求表达式的值相对来说比较容易。

后缀表达式求值策略:从左向右"扫描"，逐个处理运算数和运算符号。

1.当遇到运算数的时候，"记住"这个运算数。

2.当遇到运算符号的时候，把最近记住的两个运算数做对应的运算。

所以按照这样的策略，需要有种储存方法，能顺序储存运算数，并在需要时"倒序"输出。

因此这样的数据结构就有一种特点:先放进去的后拿出来，放进去的先拿出来做运算。这就是堆栈。

可以把堆栈形象化为：

81162917b7b64f42880b0dfdf3ebab65.png

堆栈的抽象数据类型描述

堆栈(Stack):具有一定操作约束的线性表。

                 只在一端(栈顶，Top)做插入，删除

  • 插入数据:入栈(Push)
  • 删除数据:出栈(Pop)
  • 后入先出:Last In First Out(LIFO)

类型名称:堆栈(Stack)

数据对象集:一个有零个或多个元素的有穷线性表。

操作集:长度为MaxSize的堆栈S∈Stack，堆栈元素item∈ElementType

1.Stack CreateStack(int MaxSize): 生成空堆栈，其最大长度为MaxSize;

2.int IsFull(Stack S,int MaxSize) : 判断对栈S是否已满;

3.void Puch(Stack S,ElementType item): 将元素item压入堆栈;

4.int IsEmpty (Stack S ): 判断堆栈S是否为空;

5.ElementType Pop(Stack S):删除并返回栈顶元素;

注意:做插入和删除时，往往要伴随判别堆栈插入时有没有满，删除时有没有空，空的话就不能删除了。

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

可以用下列结构表示堆栈:

#define MaxSize  <储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[MaxSize];  //这个结构包含两个分量。一个叫Data的数组
    int Top;     //Top代表了栈顶的位置的数组下标
};

（1）入栈

void Puch(Stack PtrS,ElementType item)
{
    if(PreS->Top==MaxSize-1){
        printf("栈已满")； 
        return;
    }else{
        PtrS->Data[++PtrS->Top]=item;  //做了两件事情，一个是把item放到Top+1
        return;                   //的位置，同时把Top值加1
    }
}

（2）出栈

ElementType Pop(Stack PtrS)
{
    if(PtrS->Top==-1){
        printf("堆栈空")；
        return ERROR;   //ERROR是ElementType的特殊值，标志错误
    }else
        return(PtrS->Data[(PtrS->Top)--]);
        
}

用一个数组实现两个堆栈

【例】请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。

【分析】一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长;当两个栈的栈顶指针相遇时，表示两个栈都满了。

f8b272aa944c43bf870a59e1c8a46356.png

可以定义如下数据结构：

#define MaxSize <存储数据元素的最大个数>
struct DStack{
    ElementType Data[MaxSize];
    int Top1;   //堆栈1的栈顶指针
    int Top2;   //堆栈2的栈顶指针
}S；
S.Top1=-1;       //当第一个栈顶指针为-1时（此时指针跑到数组外面），第一个堆栈为空
S.Top2=MaxSize;  //当第二个栈顶指针为MaxSize时（此时指针跑到数组外面），第二个堆栈 
                 //    为空
void Push(struct DStack *PtrS,ElementType item,int Tag)
{  //Tag作为区分两个堆栈的标志，取值为1和2
    if(PtrS->Top2-PtrS->Top1==1){
        printf("堆栈满");
        return;
    }
    if(Tog==1)  //对第一个堆栈操作
        PtrS->Data[++(PtrS->Top1)]=item; //第一个Top值增加
    else        //对第二个堆栈操作
        PreS->Data[--(PreS->Top2)]=item; //第二个Top值减少
}
Element Pop(struct DStack *PtrS,int Tag)
{  //Tag作为区分两个堆栈的标志，取值为1和2
    if(Tag==1){  //对第一个堆栈操作
        if(PtrS->Top1==-1){  
            printf("堆栈1空")；
            return NULL;
        }else return PtrS->Data[(PtrS->Top1)--];
    }else{  //对第二个堆栈操作
        if(PtrS->Top2==MaxSize){  
            printf("堆栈2空")；
            return NULL;
        }else return PtrS->Data[(PtrS->Top2)++];
    }
}

堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈，插入和删除操作只能在链栈的栈顶进行。

问题是对于一个单项链表来讲，它是有两头的，栈顶指针Top应该在链表的哪一头？

如果我们用左边，即单项链表的头作为Top，那么要在这一头做插入操作和删除操作是方便的。因为头结点知道下一个元素的位置，所以在做删除操作时，可以把Top指向下一个元素;在做插入操作时，只要把插入的结点指向头节点，然后把Top指向刚刚插入的结点就可以了。

反过来，如果我们把链的尾巴作为Top。在做插入操作时，只需要把链表的尾巴指向要插入的结点即可;但删除就有问题了，因为是单项链表，所以删除后找不到前一个结点的位置。所以Top不能指向链表的尾部。

注意:栈顶指针Top一定指向链表的头部。

647c2ec27fff470d8d9b8dde37c059dd.png

 定义结构：

typedef struct SNode *Stack;
struct SNode{
    ElementType Data;  //结构里包含两个域，一个叫Data域
    struct SNode *Next;//一个叫Next域
};

为了方便操作，可以给链式存储的这种堆栈取一个栈头结点，这样的话，在里面插入、删除都处理起来比较方便。

（1）堆栈初始化（建立空栈）

（2）判断堆栈S是否为空

Stack CreateStack()
{//构建一个堆栈的头结点，不代表任何元素，只是通过头结点可以方便的找到堆栈里具体的元素
    Stack S;
    S=(Stack)malloc(sizeof(struct SNode));  //首先申请一个结点，用S指向它
    S->Next = NULL;
    retur S;  //返回指针
}

int IsEmpty(Stack S)
{  //判断堆栈S是否为空，若为空函数返回整数1，否则返回0
    return (S->Next == NULL);
}

形成了这样一个结构：（S是一个指针，指向堆栈的头结点）

30ed83c67d4446688480a91b57930d22.png将来有结点要插入的时候，就插在它后面。

 如果采用这样一个结构，要判别堆栈是不是空的，只需判别S->Next是否等于NULL，若等于NULL，就是后面没有结点，此堆栈就为空的。

（1）插入

void push(ElementType item,Stack S)
{  //将元素item压入堆栈S
    struct SNode *TmpCell;
    TmpCell=(struct SNode *)malloc(sizeof(struct SNode));//先申请一个结点
    TmpCell->Element=item; //把item的值填入要插入的结点
    TmpCell->Next=S->Next; //后面的两行完成插入操作
    S->Next = TmpCell;
}

(2)删除

ElementType Pop(Stack S)
{  //删除并返回堆栈S的栈顶元素
    struct SNode *FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)){  //先判别一下是否为空
        printf("堆栈空");  return NULL;
    }else{
        FirstCell = S->Next; //为了释放空间，要先把结点值赋值给一个变量
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Element;
        free(FirstCell);  //必须释放删除结点的空间
        return TopElem;
    }
}

中缀表达式如何转换为后缀表达式

从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。

1.运算数:直接输出;

2.左括号:压入堆栈;

3.右括号:将栈顶的运算符弹出并输出，直到遇到左括号(出栈，不输出);

4.运算符:

  • 若优先级大于栈顶运算符时，则把它压栈
  • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出;再比较新的栈顶运算符，直到该运算符大于站定运算符优先级为止，然后将该运算符压栈

5.若各对象处理完毕，则把堆栈中存留的运算符一并输出。

堆栈的其它应用:

  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

【收藏向】大模型应用开发秋招面经全解析！覆盖30+公司，小白/程序员必看

avatar 2048 AI社区
cover

大模型面试通关指南：从八股到项目，五维度准备助你拿下offer，建议收藏

avatar 2048 AI社区

Browser-Use：一个智能浏览器自动化框架

Browser-Use是一款创新的AI驱动浏览器自动化框架，将大型语言模型与传统自动化工具深度融合。该开源项目通过自然语言交互实现智能网页操作，显著降低技术门槛。其模块化架构包含用户接口、智能决策、浏览器控制等层次，支持多标签页视频录制、自定义工具开发等高级功能。应用场景涵盖电商自动化、数据采集、业务流程优化等领域，并提供本地/云多种部署方案。Browser-Use代表了浏览器自动化技术的未来方向

avatar 2048 AI社区