线性结构的应使用-栈

作者 : 开心源码 本文共2085个字,预计阅读时间需要6分钟 发布时间: 2022-05-12 共267人阅读

定义

  • 栈是一种运算受限的线性表
  • 其限制是仅允许在表的一端进行插入和删除运算
  • 允许进行操作的一端被称为栈顶,另一端则称为栈底

主要操作

  • 压栈 / 入栈 / 进栈:插入元素
  • 出栈 / 退栈:删除元素

性质

  • 先进后出:最先进栈的元素,只可以最后出栈

栈的分类

  • 静态栈:使用数组来实现的栈
  • 动态栈:使用链表来实现的栈

动态栈的实现

栈结构

#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <stdbool.h>/**    定义结点数据类型*/typedef struct Node{    int data;    struct Node * pNext;}NODE,*PNODE;/**    定义栈结构*/typedef struct stack{    PNODE pTop;    PNODE pBottom;}STACK,*PSTACK;/**    公告函数*/void init_stack(PSTACK); //初始化一个栈,即构建一个栈结构void push_stack(PSTACK,int); //把一个元素压栈void traverse_stack(PSTACK); //遍历栈bool isEmpty(PSTACK);   //判断栈空bool pop_stack(PSTACK,int *); //出栈void clear_stack(PSTACK);   //清空栈int main(){    STACK s; //定义一个栈    //测试 初始化栈    init_stack(&s);    //测试 压栈    push_stack(&s,2);    push_stack(&s,5);    push_stack(&s,4);    push_stack(&s,8);    //测试 遍历栈    traverse_stack(&s);    //测试清空栈    clear_stack(&s);    //测试 出栈    int element;  //保存删除的元素    if(pop_stack(&s,&element)){        printf("删除成功,你删除的元素是:%d \n",element);    }else{        printf("删除失败!\n");    }    traverse_stack(&s);    printf("Hello world!\n");    return 0;}/**    初始化栈*/void init_stack(PSTACK pStack){    //为栈生成一个不存放任何数据的头结点,并且使用栈栈底指针指向它    pStack->pBottom = (PNODE)malloc(sizeof(NODE));    if(pStack->pBottom == NULL){        printf("内存分配失败,程序结束!");        exit(-1);    }    //内存分配成功,也把栈顶指针指向头结点    pStack->pTop = pStack->pBottom;    //初始化头结点,把头结点的指针域设为NULL    pStack->pTop->pNext=NULL;}/**    把一个元素压栈*/void push_stack(PSTACK pStack,int element){    //为新结点动态分配一个存储空间    PNODE pNew = (PNODE)malloc(sizeof(NODE));    if(pNew == NULL){        printf("内存分配失败,程序结束!");        exit(-1);    }    //把新插入元素的值放入到数据域中    pNew->data = element;    //压栈:把新结点挂到头结点后面    pNew->pNext = pStack->pTop;    //把栈顶指针指向栈顶元素    pStack->pTop = pNew;    return;}/**    遍历栈*/void traverse_stack(PSTACK pStack){    //得到栈顶元素的位置    PNODE p = pStack->pTop;    //遍历栈    while(p != pStack->pBottom){        printf("%d\t",p->data);        p = p->pNext;    }    printf("\n");    return;}/**    判断栈能否为空*/bool isEmpty(PSTACK pStack){    if(pStack->pBottom == pStack->pTop)        return true;    else        return false;}/**    出栈,并保存出栈元素*/bool pop_stack(PSTACK pStack,int *pElement){    if(isEmpty(pStack)){        printf("出栈失败!栈为空!");        return false;    }    //定义一个值保存删除的结点    PNODE p = pStack->pTop;    *pElement = p->data;    pStack->pTop = p->pNext;    free(p);    p=NULL;    return true;}/**    清空栈*/void clear_stack(PSTACK pStack){    if(isEmpty(pStack))        return;    PNODE p = pStack->pTop;    PNODE q = NULL;    while(p != pStack->pBottom){        q = p->pNext;        free(p);        p=q;    }    pStack->pTop = pStack->pBottom;    return;}

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 线性结构的应使用-栈

发表回复