栈的基本操作 |
您所在的位置：网站首页 › 用列表实现栈的操作 › 栈的基本操作 |
栈的基本操作
|
对于栈这一数据结构，我首先写一下它的基本概念。 一.基本概念：栈(stack)是仅限定在表尾进行插入和删除操作的线性表。 栈就是一个线性表，只不过，栈的Insert 和 delete只能在表尾。 普通的线性表，在表中的任意位置都可以进行insert和delete操作。 LIFO: Last In First Out 后进先出，先进后出。 栈顶(Top): 进行插入和删除操作的一端。 栈底(Bottom) 栈其实我们计算机科学中，更多的一种思想，“先进后出的思想”。在很多算法或应用中，需要用到“先进后出的思想”，我们可以考虑用栈来实现。 二.存储结构:顺序结构： 用一组地址连续的空间来存储数据元素。 链式结构: 用地址不连续的空间来存储数据元素，可能需要额外开辟一些空间，来存储“数据元素之间的逻辑关系"。 三.栈的基本操作：（1）初始化一个栈：InitStack （2）销毁一个栈：DestroyStack （3）清空一个栈：ClearStack （4）判断一个栈是否为空：StackIsEmpty （5）返回栈中元素个数，即栈的长度：StackLength （6）入栈，把一个元素加入到栈中：Push （7）出栈，把栈顶元素给干掉：Pop （8）返回栈顶元素，但不出栈：GetTop 接下来我们用代码来试下这些效果 #include #include //顺序栈 typedef int SElemType; //顺序栈的数据类型 结构体 typedef struct SeqStack { //SElemType data[1024] SElemType *data;// data用来存储栈中的元素 //data = malloc(); 动态数组 int maxlen;//栈中最多有多少个元素。 int top;//栈顶元素的下标 -1 代表是一个空栈 }SeqStack; //初始化一个栈 // @maxl: 代表 制定这个栈的最大可以存储多少个元素 //返回值 ： 返回初始化好的顺序栈指针 SeqStack * InitStack(int maxl) { SeqStack *s = malloc(sizeof(*s)); s->data = malloc(sizeof(SElemType)* maxl); s->top = -1; s->maxlen = maxl; return s; } //销毁一个栈 void DestoryStack(SeqStack*s) { if(s==NULL) return ; free(s->data); free(s); } //清空一个栈 void ClearStack(SeqStack*s) { if(s==NULL) return ; s->top=-1; } //判断一个栈是否为空 // 1 表示为空栈或不存在 // 0 表示非空栈 int StackisEmpty(SeqStack*s) { if(s==NULL ||s->top ==-1 ) { return 1; } return 0; } //返回栈中的元素个数咯 int Stacklength(SeqStack *s) { if(s==NULL) { return 0; } return s->top +1; } //入栈操作 //@s : 栈指针，表示那个栈 //@x: 要入栈的元素 //返回值 表示入栈是否成功 // 1 表成功 0 表失败 int Push(SeqStack *s ,SElemType x) { //最大元素个数为1 s->top=0 if(s==NULL ||s->top == s->maxlen -1) { return 0; } s->data[++s->top]=x; if(s->top==s->maxlen -1) return 0; else return 1; } /* */ int Pop(SeqStack *s,SElemType *e) { if(s==NULL || s->top == -1) { return 0; } *e = s->data[s->top--];//3 if(s->top == -1) return 0; else return 1; } //获取栈顶元素的但是不出栈 int GetTop(SeqStack *s,SElemType *e) { if(s==NULL || s->top == -1) { return 0; } *e = s->data[s->top]; return 1; } int main() { int n,m=1; int x; scanf("%d",&n); SeqStack *s= InitStack(n); while(m) { scanf("%d",&x); m=Push(s,x); } m=1; while(m) { int a=0; m=Pop(s,&a); printf("%d ",a); } printf("\n"); ClearStack(s); m=StackisEmpty(s); if(m==1) printf("栈已清空!\n"); return 0; }效果如下：
第一个数字为输入个数，第二行为输入数字的顺序，第三行是存储的数字出栈的顺序，刚好符合栈的规律。 其中相应的代码如下: 栈的定义： typedef struct SeqStack { //SElemType data[1024] SElemType *data;// data用来存储栈中的元素 //data = malloc(); 动态数组 int maxlen;//栈中最多有多少个元素。 int top;//栈顶元素的下标 -1 代表是一个空栈 }SeqStack; SeqStack * InitStack(int maxl) { SeqStack *s = malloc(sizeof(*s)); s->data = malloc(sizeof(SElemType)* maxl); s->top = -1; s->maxlen = maxl; return s; }栈的销毁： void DestoryStack(SeqStack*s) { if(s==NULL) return ; free(s->data); free(s); }栈的清空： void ClearStack(SeqStack*s) { if(s==NULL) return ; s->top=-1; }栈是否为空的判断： int StackisEmpty(SeqStack*s) { if(s==NULL ||s->top ==-1 ) { return 1; } return 0; }栈的元素个数： int Stacklength(SeqStack *s) { if(s==NULL) { return 0; } return s->top +1; }入栈操作： int Push(SeqStack *s ,SElemType x) { //最大元素个数为1 s->top=0 if(s==NULL ||s->top == s->maxlen -1) { return 0; } s->data[++s->top]=x; if(s->top==s->maxlen -1) return 0; else return 1; }出栈操作： int Pop(SeqStack *s,SElemType *e) { if(s==NULL || s->top == -1) { return 0; } *e = s->data[s->top--];//3 if(s->top == -1) return 0; else return 1; }栈头元素的判断： int GetTop(SeqStack *s,SElemType *e) { if(s==NULL || s->top == -1) { return 0; } *e = s->data[s->top]; return 1; }其中对于子函数的调用，在主函数中已写清楚。这里就不再赘述。其实对于栈的理解，可以用数组的思想来理解。上述皆是顺序结果的栈，对于链式栈，这里也不再说了。最后，望各位老铁多多支持。 |
【本文地址】