24.8.5数据结构|栈

devtools/2024/12/23 9:21:16/

栈-弹夹

1、定义:

栈就是特殊的线性表,与之前的线性表的区别就是增加了约束,只允许在一端插入和删除,就这麽简单。

2、基本操作

栈的插入操作叫:入栈{进栈、压栈};栈的删除:出栈{退栈,弹栈}

课本要求:

0、定义结构

//定义结构
#define Maxsize 100;//存储空间的初始分配量 
typedef int Element;
typedef struct{int top;Element *date;int size; 	
}StackList; //#define Maxsize 100
//typedef int Element;
//typedef struct{
//	int top;
//	Element date[Ma];	 	
//}StackList; 

1、初始化initstack:作用是初始化一个空战

2、求栈长getlen(S):返回站的元素个数

3、取栈顶元素gettop(S,x):通过x带回栈S的栈顶元素的值

4、入栈操作push(S,x),将x元素压入到站s中,使x成为新的栈顶元素

5、出栈操作pop(S,x):将非空栈的栈顶元素删除

6、判栈空操作emptystack(S),为空,返回1,否则返回0.

7、输出栈操作showlist(S):以此输出栈S中的所有元素

3、理解

基本概念

1、栈顶指针(top):记录当前栈顶的位置(下标或指针),元素的个数,站的长度

2、课本默认,空栈递减,栈顶指针初始化为0.【使用了0为栈空标记可以理解为赋值再++

3、所以,满递增栈【使用-1作为栈空标志】可以理解为直接top++再赋值

 

1、栈顶指针初始化为0或-1的区别: 
感谢我AI哥:
栈顶指针初始化为0或-1的区别
栈顶指针是用来指示栈中当前顶部元素位置的变量。在不同的编程实践中,栈顶指针的初始化值可以是0或-1,这两种做法反映了不同的设计哲学和操作习惯。栈顶指针初始化为-1
设计哲学:当栈顶指针初始化为-1时,它表示栈是空的,因为在数组中,-1不是一个有效的索引值。这样,当栈为空时,栈顶指针指向的是一个非法的位置,从而直观地表达了“没有元素在栈中”的状态。
操作习惯:在压栈操作(push operation)中,首先将栈顶指针加1,然后将新元素放入栈顶指针所指向的位置。在出栈操作(pop operation)中,首先取得栈顶元素的值,然后将栈顶指针减1。这种做法在逻辑上类似于“先预留空位,再放置元素”。栈顶指针初始化为0
设计哲学:当栈顶指针初始化为0时,它表示栈的底部,因为在数组中,0是第一个有效的索引值。这样,当栈为空时,栈顶指针正好位于栈底,表示栈中没有元素。
操作习惯:在压栈操作中,首先将新元素放入栈顶指针所指向的位置,然后栈顶指针加1。在出栈操作中,首先将栈顶指针减1,然后取得栈顶元素的值。这种做法在逻辑上类似于“先放置元素,再移动指针”。何时使用哪种初始化方式
选择栈顶指针初始化为-1还是0取决于个人偏好和具体应用场景。如果设计者倾向于直观地表达“空栈”的概念,并且喜欢在压栈前预留空位的操作方式,可能会选择初始化为-1。相反,如果设计者认为栈顶指针直接指向栈底更为直观,并且喜欢在压栈时直接放置元素的操作方式,可能会选择初始化为0。
2、realloc和malloc的区别

 

3、堆上提供长效空间,栈上生命周期短(临时使用)

顺序栈:固定大小

堆上维护接口

申请();

释放(Arraystack*stack);

满递增栈

入栈(,);

出栈();

#include<stdio.h>
#include<stdlib.h>//定义结构
#define Maxsize 100//存储空间的初始分配量 
typedef int Element;
typedef struct{int top;Element *date;int size;
}StackList; 
//第二种方法 
//#define Maxsize 100
//typedef int Element;
//typedef struct{
//	int top;
//	Element date[Ma];	 	
//}StackList; 
//都利用了数组 //初始化initstack:作用是初始化一个空战
void initstack(StackList*stack){stack->date=(Element*)malloc(sizeof(Element)*Maxsize);//这里给数据申请的空间 stack->top=0;//2、课本默认,空栈递减,栈顶指针初始化为0.【0为栈空标记】stack->size=Maxsize;}
//StackList*Createstack(StackList*stack) {
//	stack=(StackList*)malloc(sizeof(StackList)*Maxsize);
//	for(int i=0;i<Maxsize;i++){
//		stack->date[i]=0;
//	}
//	stack->top=-1;
//	return stack;
//}//2、求栈长getlen(S):返回站的元素个数
int getlen(StackList*list){return list->top;
}//3、取栈顶元素gettop(S,x):通过x带回栈S的栈顶元素的值
int  gettop(StackList*S,Element *x){//考虑栈空if(S->top==0)return 0;*x=S->date[S->top-1]; //为什么减一?取原来已经有的元素 return 1;
}// 4、入栈操作push(S,x),将x元素压入到站s中,使x成为新的栈顶元素
int  push(StackList*stack,Element x){//考虑栈满 ,栈满扩容 if(stack->top>=Maxsize) {stack->date=(Element*)realloc(stack->date,(Maxsize+1)*sizeof(Element));//ralloc的用法 if(!stack->date)return 0;//考虑空间分配不成功,返回0 stack->size++;} stack-> date[stack->top++]=x;return 1;
}
// 5、出栈操作pop(S,x):将非空栈的栈顶元素删除,存入指针e'所指向的内存单元 
int pop(StackList*stack,Element*x){//if(stack->top==0)return 0;*x=stack->date[--stack->top];return 1;
}//6、判栈空操作emptystack(S),为空,返回1,否则返回0.
int emptystack(StackList*stack){if(stack->top==0)return 1;return 0;
}
//7、输出栈操作showlist(S):以此输出栈S中的所有元素
void showLlist(StackList*stack){while(stack->top!=0){printf("%d",stack->date[--stack->top]);}
}

链式栈


http://www.ppmy.cn/devtools/92443.html

相关文章

【MySQL】内置函数

【MySQL】内置函数 日期函数字符串函数数学函数其他函数 日期函数 获取年月日 mysql> select current_date(); ---------------- | current_date() | ---------------- | 2024-08-12 | ---------------- 1 row in set (0.01 sec)获取时分秒 mysql> select current_…

XXXForm组件

效果展示 代码 XXXForm <template><div class"search-container"><el-form ref"formRef" class"form_is_hidden" :model"form" v-bind"formAttrs"><el-row :gutter"20" class"search…

C++中的智能指针

目录 1.为什么需要智能指针 2.内存泄漏 2.1 什么是内存泄漏&#xff0c;内存泄漏的危害 2.2 内存泄漏分类&#xff08;了解&#xff09; 2.3 如何检测内存泄漏&#xff08;了解&#xff09; 2.4 如何避免内存泄漏 3.智能指针的使用及原理 3.1 RAII 3.2 智能指针的原理…

vscode配置代码片段生成快捷键

一开始还以为是装个插件的事&#xff0c;没想到是自己定义的快捷键。 以vue3代码片段为例 在vscode左下角点击红框处 选择新建全局代码片段文件 输入快捷键名称 vue3&#xff08;可以自定义&#xff09;&#xff0c;以.json结尾&#xff0c;回车 在打开的文件里编写需要的代…

深度学习 —— 个人学习笔记15(图像增广、微调)

声明 本文章为个人学习使用&#xff0c;版面观感若有不适请谅解&#xff0c;文中知识仅代表个人观点&#xff0c;若出现错误&#xff0c;欢迎各位批评指正。 三十、图像增广 import torch import time import torchvision from torch import nn from IPython import display …

node指令记录

查询当前镜像地址 npm config get registry替换镜像地址为阿里云 npm config set registry http://registry.npmmirror.com切换镜像地址为默认 npm config set registry https://registry.npmjs.org创建vue3 npm create vuelatest

k8s 部署RuoYi-Vue-Plus之minio搭建

1.直接部署一个pod 需要挂载存储款, 可参考 之前文章设置 https://blog.csdn.net/weimeibuqieryu/article/details/140183843 2.部署yaml 创建部署文件 minio-deploy.yaml apiVersion: v1 kind: PersistentVolume metadata:name: minio-pvnamespace: ruoyi #使用ns ruoyi s…

【网络安全】IDOR实现ATO(账户接管)

未经许可,不得转载。 文章目录 正文正文 目标站点:target.com,注册A账号和B账号。 A账号查看个人资料(包括用户名、密码)的请求包大致为: GET /api/v1/user/profile? user_id=273948261&auth_token=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJzdWI iOiIxMjM0NTY3O…