数据结构：栈

文章目录一、栈1.1 栈的基本概念1.2 栈的储存方式1.2.1 顺序储存一、栈1.1 栈的基本概念回顾线性表第一相同类型第二n个有限序列。在逻辑上是连续的除了第一个和最后一个都有前驱和后继栈也是一种线性表栈只能在它的一端进行插入和删除这一端叫做栈顶而另外一段叫做栈底。不包含任何元素的空表就叫做空栈。栈中的数据遵循后进先出(LIFO)。栈区的地址是从高地址到低地址的出栈和压栈示例一 答案为4解析第一种情况e等d出栈再入栈最后依次出栈顺序为d ecba第二种情况d出栈后c出栈然后e出栈依次类推有三种顺序分别为dc ebadcb eadcba e示例二 答案为n-1栈中的p1p2p3可能的取值2132,4,5,…,n1231,4,5,…,n1,2431,2,5,…,n因此可能取到除3以外的任何一个数字。1.2 栈的储存方式顺序表和链表的区别不同点顺序表链表存储空间上在物理结构上一定连续逻辑结构一定连续物理结构不一定连续随机访问(用下标)支持不支持任意位置插入或者删除元素可能需要搬移元素效率低只需要修改指针插入动态顺序表空间不够需要扩容没有容量的概念按需申请释放应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率(CPU高速缓存)高低一般频繁使用尾插和尾删这种就可以考虑顺序表如果是中间插入或者删除考虑用链表CPU高速缓存内存和硬盘是常用的两个存储它们的区别是1、内存的速度是比硬盘快的2、内存是带电存储硬盘是不带电存储。对于一张图片电脑会将这张图片存在内存中如果没有电了内存就不能存储这张图片就保存不了如果我们想将这张图片存在硬盘中就需要保存这个图片。如上图所示首先我们要清楚的是i这个变量是存在内存中的当我们要实现i这句代码时我们是通过CPU来进行对i进行的我们可以看出它不是对内存i的位置而是将i的位置给一个eax的寄存器然后对这个寄存器后再将寄存器放到i这个位置去。为什么是这样呢因为它们不同频CPU太快了当它想访问内存时如果内存数据比较小(4字节或者8字节)它就加载到寄存器。如果内存数据比较大就加载到3级缓存(L1、L2、L3)中去。上图左边是一个顺序表和链表它们的数据都是1234都存在内存中现在CPU要去访问内存首先CPU会去访问缓存这时缓存中什么都没有因此不命中。然后对于顺序表当我的CPU去访问时这时1为不命中就会将顺序表中的数据拿到缓存中去拿多少数据是取决于CPU的字长的。然后拿2时就会命中。同理后面的数据都会命中因此这就是缓存利用率高。对于链表首先访问1时不命中然后将链表拿到缓存中去但是链表的地址是很大可能不连续的后面的也是很大可能不命中的而且会造成缓存污染缓存的大小是有限的如果将没有用的拿进去之前没有使用的数据就会被寄出去。栈是只允许在一端进行元素插入和删除操作的特殊线性表。而线性表有顺序和链式两种存储结构故栈也有顺序和链式两种存储结构。那是顺序储存好还是链式储存好呢顺序存储好1.2.1 顺序储存跟顺序表类似栈的顺序存储实现可以使用静态数组我们称为静态顺序栈也可以使用堆上动态申请数组实现我们称为动态顺序栈。静态顺序栈的缺陷跟静态顺序表类似只适用于确定知道最多需要多少空间的场景因此主要介绍动态顺序栈。静态顺序栈的定义#define10MAX_SIZEtypedefintSTDataType;typedefstruct{STDataType arr[MAX_SIZE];inttop;//标记栈顶}Stack;动态顺序栈的定义typedefintSTDataType;typedefstruct{STDataType*arr;inttop;//标记栈顶intcapacity;//容量}Stack;栈的初始化voidStackInit(Stack*s){assert(s);s-arr(STDataType*)malloc(4*sizzeof(STDataType));//开辟四个元素的空间if(s-arrNULL){perror(StackInit::malloc);return;}// 初始化时top 0表⽰top指向的是栈顶元素的下⼀个位置// 初始化时top -1表⽰top指向的是栈顶元素s-top0;s-capacity4;}//或者不开辟空间voidStackInit(Stack*s){assert(s);s-arrNULL;s-tops-capacity0;}入栈voidStackPush(Stack*s,STDataType x){assert(s);//扩容if(s-tops-capacity){intnewcapacitys-capacity0:4?2*s-capacity;STDataType temp(STDataType*)realloc(s-arr,sizeof(STDataType)*newcapacity);if(tempNULL){perror(StackPush::realloc);return;}s-arrtemp;s-capacitynewcapacity;//入栈s-arr[s-top]x;}出栈voidStackPop(Stack*s){assert(s);//判断是否为空如为空就没有出栈的必要if(!StackEmpty(s))s-top--;}获取栈顶元素STDataTypeStackTop(Stack*ps){assert(ps);if(!StackEmpty(s))returns-arr[s-top-1];//top0,指向的是栈顶下一个位置}获取栈中有效元素个数intStackSize(Stack*s){assert(s);returns-top;}检测栈是否为空boolStackEmpty(Stack*s){assert(s);returnps-top0;}栈的销毁voidStackDestory(Stack*s){assert(s);if(s-arr){free(s-arr);s-arrNULL;s-top0;s-capacity0;}}打印栈intmain(){Stack s;StackInit(s);StackPush(s,1);StackPush(s,2);StackPush(s,3);StackPush(s,4);//在打印栈顶元素之时也需要出栈while(!StackEmpty(s)){printf(%d ,StackTop(s));StackPop(s);}