企业官网建设流程全解析

一、栈

1.1 栈的基本概念

回顾：线性表：第一，相同类型；第二，n个有限序列。在逻辑上是连续的，除了第一个和最后一个都有前驱和后继
栈也是一种线性表，栈只能在它的一端进行插入和删除，这一端叫做栈顶，而另外一段叫做栈底。不包含任何元素的空表就叫做空栈。栈中的数据遵循后进先出(LIFO)。栈区的地址是从高地址到低地址的

出栈和压栈

示例一 答案为4

解析：

• 第一种情况，e等d出栈再入栈，最后依次出栈，顺序为d ecba

• 第二种情况，d出栈后，c出栈，然后e出栈，依次类推，有三种，顺序分别为：
  dc eba，dcb ea，dcba e

示例二 答案为n-1

因此可能取到除3以外的任何一个数字。

1.2 栈的储存方式

顺序表和链表的区别

一般频繁使用尾插和尾删这种就可以考虑顺序表，如果是中间插入或者删除考虑用链表

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->arr==NULL){perror("StackInit::malloc");return;}// 初始化时，top = 0，表⽰top指向的是栈顶元素的下⼀个位置// 初始化时，top = -1，表⽰top指向的是栈顶元素s->top=0;s->capacity=4;}//或者不开辟空间voidStackInit(Stack*s){assert(s);s->arr=NULL;s->top=s->capacity=0;}

入栈

voidStackPush(Stack*s,STDataType x){assert(s);//扩容if(s->top==s->capacity){intnewcapacity=s->capacity=0:4?2*s->capacity;STDataType temp=(STDataType*)realloc(s->arr,sizeof(STDataType)*newcapacity);if(temp==NULL){perror("StackPush::realloc");return;}s->arr=temp;s->capacity=newcapacity;//入栈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];//top=0,指向的是栈顶下一个位置}

获取栈中有效元素个数

intStackSize(Stack*s){assert(s);returns->top;}

检测栈是否为空

boolStackEmpty(Stack*s){assert(s);returnps->top==0;}

栈的销毁

voidStackDestory(Stack*s){assert(s);if(s->arr){free(s->arr);s->arr=NULL;s->top=0;s->capacity=0;}}

打印栈

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