• 王道3.1 顺序栈以及链式栈


    一、的基本概念

    1.栈只允许在一段进行删除或插入操作的线性表
    2.三个术语
    ①栈顶top :线性表允许进行插入删除的那一端
    ②栈底bottom:固定的,不允许进行插入和删除的另一端
    ③空栈:不含任何元素的空表
    3.栈只能对栈顶进行操作
    4.后进先出LIFO
    5.n个不同元素进栈,出栈元素不同排列个数为,例如,五个元素就有=42种
    6.栈的基本操作:初始化、判空、出栈、进栈、读栈、销毁栈

    二、栈的储存

    1. 栈的存储方式有两种:顺序栈和链栈,即栈的顺序存储和链式存储
    2. 采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的元素,同时附设一个指针(top)指示当前栈顶的位置。
    3. 栈的顺序存储类型描述:
    #define MaxSize 100 //定义栈中元素的最大个数
    typedef struct SqStack{
        int data[MaxSize]; //存放栈中的元素
        int top; //栈顶指针
    }SqStack;
    
    • 1
    • 2
    • 3
    • 4
    • 5

    4.采用链式存储的栈称为链栈,链栈便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并且所有操作都是在单链表的表头进行的。在本文中主要是介绍了顺序栈下的一些基本操作,关于链栈的实现与单链表类似,
    5.链式存储描述:

    typedef struct LinkNode{
        int data; //数据域
        struct LinkNode *next; //指针域
    }*LiStack; //栈类型定义
    
    • 1
    • 2
    • 3
    • 4

    三、顺序栈的基本操作

    1.初始化

    //初始化
    void InitStack(SqStack &S){
        S.top = -1;
    }
    
    • 1
    • 2
    • 3
    • 4

    也可以设置成top=0,表示指向下一个要存储的位置
    2.判空操作
    栈空条件:S.top == -1; 栈满条件:S.top ==MaxSize-1。

    //判栈空
    bool Empty(SqStack S){
        if(S.top == -1){
            return true;
        }else{
            return false }}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.进栈操作
    由于初始设置S.top=-1,故栈顶指针先加一,再入栈。

    //入栈
    void Push(SqStack &S, int x){
        if(S.top == MaxSize-1){
            cout<<"栈满"<<endl;
            return;
        }
        S.data[++S.top] = x; //指针先加一,再入栈
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    4.出栈操作

    //出栈
    void Pop(SqStack &S, int &x){
        if(S.top == -1){
            cout<<"栈空"<<endl;
            return;
        }
        x = S.data[S.top--]; //先出栈,指针再减一
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5.读取栈顶操作

    //读栈顶元素
    int GetTop(SqStack S){
        if(S.top == -1){
            cout<<"栈空"<<endl;
            return -1;
        }else{
            return S.data[S.top];
        }}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    6.遍历栈

    //遍历栈
    void PrintStack(SqStack S){
        while(S.top != -1){
            cout<<S.data[S.top--]<<" ";
        }
        cout<<endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    四、共享栈
    1.图例
    在这里插入图片描述

    2.描述

    typedef struct {
    	ElemType data[MaxSize];		//静态数组存放栈中元素
    	int top1;					//1号栈栈顶指针
    	int top2;					//2号栈栈顶指针
    }ShStack;
    
    • 1
    • 2
    • 3
    • 4
    • 5

    3.初始化

    //1.初始化共享栈
    void InitShStack(ShStack& S) {
    	S.top1 = -1;		//初始化1号栈栈顶指针
    	S.top2 = MaxSize;	//初始化2号栈栈顶指针
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5

    4.判空

    //2. 1号栈判空
    bool Stack1Empty(ShStack S) {
    	return (S.top1 == -1);
    //2. 2号栈判空
    bool Stack2Empty(ShStack S) {
    	return (S.top2 == MaxSize);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    5.判断栈满

    Top1-top2==1
    
    • 1

    6.入栈

    //4. 1号栈入栈操作:新元素入栈(先存再加)
    bool Push1(ShStack& S, ElemType x) {
    	if (S.top1+1 == S.top2)		//栈满,报错
    		return false;
    	S.data[++S.top1] = x;
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    //5. 2号栈入栈操作:新元素入栈(先存再加)
    bool Push2(ShStack& S, ElemType x) {
    	if (S.top1 + 1 == S.top2)		//栈满,报错
    		return false;
    	S.data[--S.top2] = x;
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    7.出栈

    //6. 1号栈出栈操作:栈顶元素出栈
    bool Pop1(ShStack& S, ElemType& x) {
    	if (S.top1 == -1)	//1号栈栈空,报错
    		return false;
    	x = S.data[S.top1--];	
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    //7. 2号栈出栈操作:栈顶元素出栈
    bool Pop2(ShStack& S, ElemType& x) {
    	if (S.top2 == MaxSize)	//2号栈栈空,报错
    		return false;	
    	x = S.data[S.top2++];
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    8.栈顶读栈

    //8. 1号栈读取栈顶元素操作
    bool GetTop1(ShStack S, ElemType& x) {
    	if (S.top1 == -1)	//1号栈栈空,报错
    		return false;
    	x = S.data[S.top1];
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    //9. 2号栈读取栈顶元素操作
    bool GetTop2(ShStack S, ElemType& x) {
    if (S.top2 == MaxSize)	//2号栈栈空,报错
    		return false;
    	x = S.data[S.top2];
    	return true;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    四、链式栈的基本操作

    #include 
    #include 
    #include 
    
    using namespace std;
    //2.定义链栈结构体
    typedef struct LinkStackNode
    {
        ElemType data;//存数据
        struct LinkStackNode *next;//存下个节点的地址
    } LinkStack;
    //3.初始化链栈
    int initLinkStack(LinkStack *L)
    {
        L = (LinkStack *) malloc(sizeof(LinkStack));//申请内存
        if(!L->data) return 0;//申请失败
        L->data = 0;//初始化链栈头结点数据域
        L->next = NULL;//初始化链栈头结点指针域
        return 1;
    }
    //4.入栈
    int push(LinkStack *L, ElemType e)
    {
        LinkStack *n;//新节点
        n = (LinkStack *) malloc(sizeof(LinkStack));
        if(!n->data) return 0;
        n->data = e;//存入数据
        n->next = L->next;//链栈栈顶元素链入新节点,新节点变成栈顶
        L->next = n;//新节点链入链栈头结点末尾
        return 1;
    }
    //5.出栈
    int pop(LinkStack *L, ElemType *e)
    {
        if(!L->next) return 0;//栈空,返回0
        LinkStack *d = L->next;//出栈指针指向栈顶
        *e = d->data;//赋值
        L->next = d->next;//头结点跳过出栈节点,链入出栈节点的下一节点
        free(d);//释放内存
        return 1;
    }
    //6.取栈顶
    int getTop(LinkStack *L, ElemType *e)
    {
        if(!L->next) return 0;
        *e = L->next->data;
        return 1;
    }
    void printStack(LinkStack *L)
    {
        LinkStack *p = L;//遍历指针
        while (p)
        {
            p = p->next;
            printf("%d ", p->data);
        }
        printf("\n");
    }
    //7.演示
    int main()
    {
        LinkStack L;
        initLinkStack(&L);
        ElemType e;
        printf("入栈元素:");
        scanf("%d", &e);
        push(&L, e);
        getTop(&L, &e);
        printf("栈顶元素:%d\n",e);
        pop(&L, &e);
        printf("出栈元素:%d", e);
        printf("\n入栈元素(Ctrl + C结束):");
        while (scanf("%d", &e) != EOF)
        {
            push(&L, e);
            printf("入栈元素(Ctrl + C结束):");
        }
        printf("\n遍历元素:");
        printStack(&L);
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
  • 相关阅读:
    和外国bi相比,国产bi软件更适合中国企业
    我开源了团队内部基于SpringBoot Web快速开发的API脚手架stater
    BUUCTF:8月做题记录
    【离散数学】第二章 测试
    实验笔记之——可见光通信调制驱动芯片模组
    java.sql.SQLException: Cannot set billDate: incompatible types.
    访问控制1
    实战指南:使用 xUnit.DependencyInjection 在单元测试中实现依赖注入【完整教程】
    服务端Skynet(二)——消息调度机制
    python+Vue在线投稿网站系统pycharm源码
  • 原文地址:https://blog.csdn.net/qq_46126118/article/details/126056954