admin管理员组

文章数量:1794759

2024重生之回溯数据结构与算法系列学习（6）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

上章回顾

​​​​​​​ ​​​​​​​ ​​​​​​​ ​​​​​​​ ​​​​​​​

1.栈的基本概念

1.1栈的定义：

  • 栈（Stack）是只允许在一端进行插入或删除操作的线性表
  • 逻辑结构：与普通线性表相同
  • 数据的运算：插入、删除操作有区别
  • 栈顶：允许插入和删除的一端，对应元素被称为栈顶元素
  • 栈底：不允许插入和删除的一端，对应元素被称为栈底元素
  • 特点：后进先出Last In First Out（LIFO）

1.2栈的基本操作：

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

1.3出栈顺序数量：

  • n个不同元素进栈，出栈元素不同排列的个数为
  • ​

​

  • 上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明

2.栈的顺序存储结构

2.1顺序栈的定义和初始化：

​

2.2顺序栈的定义代码实现：
代码语言：javascript代码运行次数：0运行复制
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
                     //连续的存储空间大小为 MaxSize*sizeof(ElemType)
}
2.3顺序栈的基本操作代码实现：
代码语言：javascript代码运行次数：0运行复制
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top = -1;                   //初始化栈顶指针
}

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



//出栈
bool Pop(SqStack &x, ElemType &x){
    if(S.top == -1)          //栈空
        return false;
    
    x = S.data[S.top];       //先出栈
    S.top = S.top - 1;       //栈顶指针减1
    return true;

    /*
    x = S.data[S.top--];
    */

    //只是逻辑上的删除，数据依然残留在内存里

}

//读栈顶元素
bool GetTop(SqStack S, ElemType &x){
    if(S.top == -1)
        return false;
    
    x = S.data[S.top];      //x记录栈顶元素
    return true; 
}


void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
    InitStack(S);
    //...
}
2.3.1进栈操作：

​

2.3.2进栈操作代码实现：
代码语言：javascript代码运行次数：0运行复制
bool Push(SqStack &S, ElemType x){
    if(S.top == MaxSize - 1)        //栈满
        return false;
    
    S.top = S.top + 1;    //指针先加1
    S.data[S.top] = x;    //新元素入栈

    /*
    S.data[++S.top] = x;
    */
    return true;
}
​
2.3.3出栈操作：

​

2.3.4进栈操作代码实现：
代码语言：javascript代码运行次数：0运行复制
bool Pop(SqStack &x, ElemType &x){
    if(S.top == -1)          //栈空
        return false;
    
    x = S.data[S.top];       //先出栈
    S.top = S.top - 1;       //栈顶指针减1
    return true;

    /*
    x = S.data[S.top--];
    */

    //只是逻辑上的删除，数据依然残留在内存里

}
2.3.5读取栈顶元素：

​

2.3.6读取栈顶元素代码实现：
代码语言：javascript代码运行次数：0运行复制
bool GetTop(SqStack S, ElemType &x){
    if(S.top == -1)
        return false;
    
    x = S.data[S.top];      //x记录栈顶元素
    return true; 
}


void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
    InitStack(S);
    //...
}

注意：也可以让栈顶指针top先指向0，每次进栈S.top++，出栈--S.top

​

3.共享栈：

  • 使用静态数组要求提前规定好栈的大小，容易造成内存资源的浪费因此共享栈应运而生
  • 两个栈共享同一片空间，0、1号栈朝着同一方向进栈
  • 栈满的条件：top0 + 1 == top1

​

3.1共享栈的定义和初始化代码实现：
代码语言：javascript代码运行次数：0运行复制
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top0;                     //0号栈栈顶指针
    int top1;                     //1号栈栈顶指针
}ShStack;

//初始化栈
void InitSqStack(ShStack &S){
    S.top0 = -1;        //初始化栈顶指针
    S.top1 = MaxSize;   
}
栈满条件：top1-top0=1

4.栈的链式存储结构

4.1栈的链式存储实质：

进栈：头插法建立单链表，也就是对头结点的后插操作

出栈：单链表的删除操作，对头结点的“后删”操作

推荐使用不带头结点的链栈

创销增删查的操作参考链表

4.2链栈的定义：

​

4.3链栈的定义代码实现：

代码语言：javascript代码运行次数：0运行复制
#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode *next;       //指针域
}Linknode,*LiStack;   

typedef Linknode *Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

4.4带头结点的链栈基代码实现如下：

1. 初始化
代码语言：javascript代码运行次数：0运行复制
void InitStack(LiStack &L){   //L为头指针
    L = new Linknode; 
    L->next = NULL;
}
2.判栈空
代码语言：javascript代码运行次数：0运行复制
bool isEmpty(LiStack &L){
    if(L->next == NULL){
        return true;
    }
    else
        return false;
}
3. 进栈
代码语言：javascript代码运行次数：0运行复制
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;
    s->data = x;

    //头插法
    s->next = L->next;
    L->next = s;
}
4.出栈
代码语言：javascript代码运行次数：0运行复制
bool popStack(LiStack &L, int &x){
    Linknode s;
    if(L->next == NULL) //栈空不能出栈
        return false;
    
    s = L->next;
    x = s->data;
    L->next = L->next->next;
    delete(s);

    return true;
}

4.5不带头结点的链栈代码实现基本操作如下：

1.初始化
代码语言：javascript代码运行次数：0运行复制
void initStack(LiStack &L){
    L=NULL;
}
2.判栈空
代码语言：javascript代码运行次数：0运行复制
bool isEmpty(LiStack &L){
    if(L == NULL)
        return true;
    else
        teturn false;
}
3.进栈
代码语言：javascript代码运行次数：0运行复制
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;

    s->next = L;
    L = s;
}
4.出栈
代码语言：javascript代码运行次数：0运行复制
bool popStack(LiStack &L, int &x){
    Linknode s; 
    if(L = NULL)     //栈空不出栈
        return false;

    s = L;
    x = s->data;
    L = L->next;
    delete(s);
    
    return true;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent 删除指针存储数据数据结构与算法数组

本文标签： 2024重生之回溯数据结构与算法系列学习（6）无论是王道考研人还是IKUN都能包会的不然别给我家鸽鸽丢脸好嘛

版权声明：本文标题：2024重生之回溯数据结构与算法系列学习（6）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754674820a1705055.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。