数据结构——栈（附图文讲解 | 超详细）

一、前言

这篇博客我们来聊聊数据结构——栈

二、栈

2.1 定义

概念：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

1.后进先出

那么是什么是后进先出呢？

先进去的数据后出来，而后进去的数据先出来

如图：

2.压栈和出栈

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2.2 栈的实现

对于栈的实现来说可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。所以我们这里用数组来实现。

1. 创建栈

//栈typedefintSTDataType;//自定义数据元素类型typedefstructStack{STDataType*arr;inttop;//有效数据个数intcapacity;//空间容量}ST;

2. 栈的初始化

//初始化voidStackInit(ST*ps){ps->arr=NULL;ps->top=ps->capacity=0;}

3. 栈的销毁

//栈的销毁voidStackDestroy(ST*ps){if(ps->arr)free(ps->arr);ps->arr=NULL;ps->top=ps->capacity=0;}

4. 入栈

先向内存申请空间，再从栈顶入栈

//入栈——栈顶voidStackPush(ST*ps,STDataType x){assert(ps);if(ps->top==ps->capacity){intnewCapacity=ps->capacity==0?4:2*ps->capacity;STDataType*tmp=(STDataType*)realloc(ps->arr,newCapacity*sizeof(STDataType));if(tmp==NULL){perror("realloc fail!");exit(1);}ps->arr=tmp;ps->capacity=newCapacity;}ps->arr[ps->top++]=x;}

5. 判断栈是否为空

用于之后的功能接口进行断言

//判断栈是否为空boolStackEmpty(ST*ps){assert(ps);returnps->top==0;}

6. 出栈

从栈顶出栈

//出栈voidStackPop(ST*ps){assert(!StackEmpty(ps));--ps->top;}

7. 取栈顶

取栈顶数据

//取栈顶STDataTypeStackTop(ST*ps){assert(!StackEmpty(ps));returnps->arr[ps->top-1];}

8. 有效元素个数

//取有效元素个数intStackSize(ST*ps){returnps->top;}

三、完整代码

Stack.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//栈typedefintSTDataType;typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;//初始化voidStackInit(ST*ps);//销毁voidStackDestroy(ST*ps);//入栈——栈顶voidStackPush(ST*ps,STDataType x);//boolStackEmpty(ST*ps);//出栈voidStackPop(ST*ps);//取栈顶数据STDataTypeStackTop(ST*ps);//有效元素个数intStackSize(ST*ps);

Stack.c

#include"Stack.h"//初始化voidStackInit(ST*ps){ps->arr=NULL;ps->top=ps->capacity=0;}//销毁voidStackDestroy(ST*ps){if(ps->arr)free(ps->arr);ps->arr=NULL;ps->top=ps->capacity=0;}//入栈——栈顶voidStackPush(ST*ps,STDataType x){assert(ps);if(ps->top==ps->capacity){intnewCapacity=ps->capacity==0?4:2*ps->capacity;STDataType*tmp=(STDataType*)realloc(ps->arr,newCapacity*sizeof(STDataType));if(tmp==NULL){perror("realloc fail!");exit(1);}ps->arr=tmp;ps->capacity=newCapacity;}ps->arr[ps->top++]=x;}//判断栈是否为空boolStackEmpty(ST*ps){assert(ps);returnps->top==0;}//出栈voidStackPop(ST*ps){assert(!StackEmpty(ps));--ps->top;}//取栈顶数据STDataTypeStackTop(ST*ps){assert(!StackEmpty(ps));returnps->arr[ps->top-1];}//有效元素个数intStackSize(ST*ps){returnps->top;}

test.c

#include"Stack.h"voidtest01(){ST st;StackInit(&st);StackPush(&st,1);StackPush(&st,2);StackPush(&st,3);StackPush(&st,4);StackPush(&st,5);//StackPop(&st);//StackPop(&st);//StackPop(&st);//StackPop(&st);//StackPop(&st);//while (!StackEmpty(&st))//{// int top = StackTop(&st);// printf("%d ", top);// StackPop(&st);//}intsize=StackSize(&st);printf("size:%d\n",size);StackDestroy(&st);}intmain(){test01();//测试return0;}