当前位置: 首页 > news >正文

数据结构--栈和队列3.1(栈-顺序结构)

目录

栈(Stack)栈顶(top)栈底(bottom)空栈(不含任何元素)

创建栈 

入栈操作

出栈操作

销毁一个栈

计算栈的当前容量

实例分析


栈的插入操作叫做进栈(Push),或者称为压栈、入栈。

栈的删除操作叫做出栈(Pop),或者称为弹栈。

栈又称为先进后出(last in first out)的后进先出原则,称为后进先出的线性表(LIFO)。 

栈的本质上也是一个线性表,线性表有两种存储形式,那么栈也有分为栈的顺序存储结构和栈的链式存储结构

最开始栈中不含有任何数据,叫做空栈,此时栈定就是栈底。然后数据从栈顶进入,栈顶栈底分离,整个栈的当前容量变大。数据出栈时,从栈顶移出,栈顶下一,整个栈的当前容量变小。

栈的顺序存储结构:

typedef struct 
{ElemType *base;ElemType *top;int stacksize;}sqStack;

 这里定义了一个顺序存储的栈,它包含了三个元素:base,top,stacksize。其中base是指向栈底的指针变量,top是指向栈顶的指针变量,stacksize指示栈的当前可使用的最大容量。

创建栈 

#define STACK_INIT_SIZE 100 initStack(sqStack *s)//创建栈 
{s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if(!s->base)exit(0);s->top=s->base;		//最开始,栈顶就是栈底。 s->stacksize = STACK_INIT_SIZE;} 

入栈操作

#include <stdlib.h>
#define STACKINCREMENT 10Push(sqStack *s,ElemType e)		//入栈操作 
{if(s->top - s->base >= s->stacksize){//如果漫展,追加空间 s->base = (ElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(ElemType));if(!s->base)exit(0);s->top=s->base + s->stacksize;s->stacksize = s->stacksize + STACKINCREMENT;}*(s-top)=e;s->top++; } 

出栈操作

出栈操作就是在栈顶取出数据,栈顶指针随之下移的操作。

每当从栈内弹出一个数据,栈的当前容量就-1.

Pop(sqStack *s,ElemType *e)
{if(s->top==s->base)//栈已空return;*e=*--(s->top); 
}

销毁一个栈

DestrogStack(sqStack *s)
{int i,len;len = s->stackSize;for(i=0;i<len;i++){free(s->base);s->base++;}s->base = s->top =NULL;s->stacksize = 0;
}

计算栈的当前容量

计算栈的当前容量也就是计算栈中元素的个数,因此只要返回s.top-s.base 即可。

栈的最大容量是指该栈占据内存空间的大小,其值是s.stackSzie,它与栈的当前容量不是一个概念。

int StackLen(sqStack s)
{return (s.top-s.base+1);
}

实例分析

利用栈的数据结构特点,将二进制转换为十进制数。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10typedef char ElemType;
typedef struct
{ElemType *base;ElemType *top;int stackSize; }sqStack;void InitStack(sqStack *s)
{s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if(!s->base)exit(0);s->top = s->base;s->stackSize=STACK_INIT_SIZE;
}void Push(sqStack *s,ElemType e)
{if(s->top - s->base>= s->stackSize){s->base=(ElemType *)realloc(s->base,(s->stackSize+STACKINCREMENT) * sizeof(ElemType));if(!s->base){exit(0);}}*(s->top)=e;s->top++;} void Pop(sqStack *s,ElemType *e)
{if(s->top==s->base){return;}*e = *--(s->top);
}int StackLen(sqStack s)
{return (s.top- s.base);
}int main(void)
{ElemType c;sqStack s;int len ,i,sum=0;InitStack(&s);printf("请输入二进制数,输入#符号表示结束!");scanf("%c",&c);while(c!='#'){Push(&s,c);scanf("%c",&c);}getchar();len = StackLen(s);printf("栈的当前容量是:%d\n",len);for(i=0;i<len;i++){Pop(&s,&c);sum=sum+(c-48)*pow(2,i);}printf("%d",sum);return 0;
}

http://www.lryc.cn/news/118710.html

相关文章:

  • pdf怎么压缩到1m?这样做压缩率高!
  • AttentionFreeTransformer 源码解析(一):AFTFull、AFTSimple、AFTLocal
  • C++ 计算 拟合优度R^2
  • Springboot-Retrofit HTTP工具框架快速使用
  • 微信小程序实现人脸识别(从一个没有开通人脸核身的小程序跳转到要给开通人脸核身的小程序,进行人脸识别后再跳转回来)
  • CSS-grid布局
  • 【JavaEE进阶】Bean 作用域和生命周期
  • 3分钟自建查分系统?现在每个人都可以实现了
  • 关于APP备案、小程序备案的问题,如何备案?
  • git上传代码后,如何清空历史日志以及文件操作,重新上传?以及上传代码
  • 超导热催生meme,换汤不换药的投机轮回
  • 【HashMap】 73. 矩阵置零
  • Vue-2.nodejs的介绍和安装
  • 分别用Vue和Java来实现的风靡一时的2048 游戏
  • echarts甘特图 一个值多条线
  • 多态性说明
  • 2023-08-04 LeetCode每日一题(不同路径 III)
  • 腾讯云服务器地域怎么选?可用区是什么?
  • 第一百二十三天学习记录:C++提高:STL-vector容器(下)(黑马教学视频)
  • 谈谈Spring与字节码生成技术
  • Java数组详解 -- 基础知识与常用操作
  • (统计学习方法|李航)第五章 决策树——一二三节:决策树模型与学习,特征选择,决策树的生成,
  • qt lamda表达式及捕获变量列表符号说明及示例
  • 第十六章、【Linux】程序管理与SELinux初探
  • ElasticSearch索引生命周期管理--DELETE
  • sentinel简单使用
  • C#小轮子:自动连续Ping网络地址
  • react入门笔记
  • 记录--前端重新部署如何通知用户
  • WPS的excel表格单元格拖动数字日期等 不自增原因