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

24.8.5数据结构|栈

news 来源：原创 2024/9/20 12:31:34

栈-弹夹

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]);}
}