企业官网建设流程全解析

接下来介绍一下一种数据结构，栈。

一、栈的基本概念

线性表是相同类型的n(n>=0)个数据元素的有限序列，若⽤L命名为线性表，则⼀般表示为L = (a1 , a2 , ..., ai , ai+1 , ..., an )

栈(stack)是限定仅在⼀端进⾏插⼊或删除操作的线性表。因此，对栈来说进⾏插⼊删除数据的这⼀端称为栈顶(top)，另⼀端称为栈底(bottom)，不含元素的空表称为空栈。栈中的数据元素遵循后 进先出(LIFO：LastInFirstOut)的特性。

栈插⼊和删除数据都在栈顶端，插入数据⼀般叫做入栈/进栈，删除数据⼀般叫做出栈。也就是只能在栈顶出数据和入数据。

可以联想到生活中的羽毛球桶。

二、栈的基本操作

栈是⼀种只允许在⼀端进⾏插⼊和删除的线性表，栈插⼊和删除数据都在栈顶端，插⼊数据⼀般叫 做⼊栈，删除数据⼀般叫做出栈，所栈最核⼼的接⼝函数就是入栈和出栈函数。

栈可以用链表和顺序表来实现，我们分为两块。

1、顺序表实现的栈

顺序表实现的栈，和顺序表一样，有两种，一种是静态的，就是我们给数组一个容量，让它去存元素。它不能扩容，比如给你int arr[100]，就存100个元素。和顺序表一样，我们更多使用可扩容的动态栈。下面是动态栈的实现。

这个动态栈，数组右边是栈顶，插入元素从右边插入。出元素也从右边出。

头文件先放上来，这里包含函数的声明还有结构体的定义。

// SeqStack.h #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct { STDataType* arr; // 指向栈数组空间的指针 int top; // 栈顶位置 int capacity; // 容量 }Stack; // 栈的初始化 void StackInit(Stack* s); // 栈的销毁 void StackDestroy(Stack* s); // x元素入栈(进栈) void StackPush(Stack* s, STDataType x); // 将栈顶元素出栈，并用返回栈顶元素 STDataType StackPop(Stack* s); // 获取栈顶元素并返回 STDataType StackTop(Stack* s); // 获取栈中有效元素个数 int StackSize(Stack* s); // 检测栈是否为空，如果是空返回真，否则返回假 bool StackEmpty(Stack* s);

值得注意的是，这里的栈顶top指向的是下一个要放元素的位置，比如现在有2个元素，top=2。因为如果指向的是最后一个元素的位置，那么一开始和有一个元素top就都是0了。或者你一开始初始化把top改为-1也行。

（1）栈的初始化

// 栈的初始化 void StackInit(Stack* s) { assert(s); s->arr=(STDataType*)malloc(4*sizeof(STDataType)); if (s->arr == NULL) { perror("StackInit"); exit(-1); } s->top=0; s->capacity=4; }

因为顺序表实现的栈，开空间要开一块连续空间，所以我们先给它开4个空间，后续有需要再扩容。一开始不给空间后续扩容也行。

（2）栈的销毁

// 栈的销毁 void StackDestroy(Stack* s) { assert(s); free(s->arr); s->arr=NULL; s->capacity=s->top=0; }

释放掉哪个开的空间就行。把指针和内存都置零即可。

（3）x元素进栈

// x元素入栈(进栈) void StackPush(Stack* s, STDataType x) { assert(s); //扩容 if (s->top == s->capacity) { STDataType* s1 = (STDataType*)realloc(s->arr,2*s->capacity * sizeof(STDataType)); if (s1 == NULL) { perror("StackPush"); exit(-1); } s->arr=s1; s->capacity *= 2; } //入栈 s->arr[s->top]=x; s->top++; }

先检查栈能不能放的下，然后扩容，如果初始化空间给零，那就改成：

STDataType* s1 = (STDataType*)realloc(s->arr,s->arr==NULL?4:2*s->capacity * sizeof(STDataType));

（4）将栈顶元素出栈，并用返回栈顶元素

STDataType StackPop(Stack* s) { assert(s); assert(!StackEmpty(s)); STDataType x=s->arr[s->top-1]; s->top--; return x; }

assert断言非空，先保存最后一个，再top--就行了，和顺序表一样，删元素只要改capacity就行，后面入栈的时候元素会覆盖。

（5）获取栈顶元素并返回

STDataType StackTop(Stack* s) { assert(s); assert(!StackEmpty(s)); return s->arr[s->top-1]; }

判断非空，返回即可

（6）获取栈中有效元素个数

int StackSize(Stack* s) { assert(s); return s->top; }

可以观察到top其实就是元素的个数，比如2个元素在数组就占了0,1下标，top就是2。

（7）检测栈是否为空，如果是空返回真，否则返回假

bool StackEmpty(Stack* s) { assert(s); return s->top==0; }

2、链表实现的栈

如果选⽤双向链表，则⽤表头表尾做栈顶都可以，因为双向链表头尾插⼊删除效率都是O（N） 。当然我们完全没必要选择双向链表，因为单链表就可以⾼效实现，还省空间⼀些。双向链表没有优 势，每个结点还要多存储⼀个前驱指针，使⽤它纯粹浪费了。

其次我们选择单链表实现，可以带头结点，也可以不带头结点；但是这⾥⼊栈出栈就是对应头插头 删，单链表带头结点时，头插头删并不会带来什么便利，所以⼀般我们选择不带头结点实现即可。

如果是单向链表来实现栈的话，我们的栈顶应该设置在最左边，因为当我们出栈的时候，如果栈顶在右边，尾删，topHead需要往前移找上一个节点，我们单链表遍历找尾只能往后遍历，不能往前遍历，如果往后遍历时间复杂度就是O（N）了，不太好，所以我们把栈顶设在最左边。这样子，出栈的时候，topHead（栈顶指针）往后移就出栈了。因为有栈顶指针，也可以入栈。

头文件：

// LinkStack.h #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 链式栈中存储的数据元素类型 typedef int STDataType; // 链式栈底层单链表中结点的定义 typedef struct LinkStackNode { struct LinkStackNode* next; STDataType data; }LSNode; typedef struct { LSNode* topHead; int size; }LinkStack; // 初始化链式栈s void LinkStackInit(LinkStack* s); // 销毁链式栈s void LinkStackDestroy(LinkStack* s); // x入栈 void LinkStackPush(LinkStack* s, STDataType x); // 出栈，并返回栈顶元素 STDataType LinkStackPop(LinkStack* s); // 获取栈顶元素 STDataType LinkStackTop(LinkStack* s); // 获取栈中有效元素个数 int LinkStackSize(LinkStack* s); // 检测栈是否为空，如果是空返回真，否则返回假 bool LinkStackEmpty(LinkStack* s);

（1）初始化链式栈s

// 初始化链式栈s void LinkStackInit(LinkStack* s) { assert(s); s->size=0; s->topHead=NULL; }

刚开始，栈元素为空，就没有节点，栈顶指针还有元素都置空。

（2）销毁链式栈s

void LinkStackDestroy(LinkStack* s) { assert(s); LSNode*cur=s->topHead; while (cur) { LSNode*next=cur->next; free(cur); cur=next; } s->size=0; s->topHead=NULL; }

就从栈顶开始往后遍历，每到一个节点就释放，继续往后就行了。和链表一样。

（3）x入栈

void LinkStackPush(LinkStack* s, STDataType x) { assert(s); //创造新节点 LinkStackNode* newNode=(LinkStackNode*)malloc(sizeof(LinkStackNode)); if (newNode == NULL) { perror("LinkStackPush"); exit(-1); } newNode->data=x; newNode->next=NULL; //入栈连接 newNode->next=s->topHead; s->topHead=newNode; s->size++; }

我们就和链表一样，先创造新节点，把新节点连到最前面就行了。所以先新节点next=topHead,再把topHead指向新节点，成为新的栈顶。记得size++。

（4）出栈，并返回栈顶元素

STDataType LinkStackPop(LinkStack* s) { assert(s); assert(!LinkStackEmpty(s)); LSNode*DelNode=s->topHead; STDataType x=DelNode->data; s->topHead=s->topHead->next; free(DelNode); s->size--; return x; }

assert确保非空

我们存一下栈顶地址，就是让指针DelNode指向栈顶，然后让栈顶指针往后走，把原先的栈顶free掉就行了。记得要提前保存一下原先栈顶的值最后返回。

（5）获取栈顶元素

STDataType LinkStackTop(LinkStack* s) { assert(s); assert(!LinkStackEmpty(s)); return s->topHead->data; }

assert确保非空，直接返回就行。

（6）获取栈中有效元素个数

int LinkStackSize(LinkStack* s) { assert(s); return s->size; }

返回即可。

（7）检测栈是否为空，如果是空返回真，否则返回假

bool LinkStackEmpty(LinkStack* s) { assert(s); return (s->size==0); }

3、栈的顺序存储和链式存储对比

栈的顺序存储和链式存储都可以做到⼊栈和出栈时间复杂度为O(1) ，效率都很高。

栈的顺序存储的唯⼀问题是⼊栈时空间不够，扩容有⼀定的消耗，但是这个消耗几乎可以忽略不 计，因为插⼊⼀定量数据才会扩容。而且我们现在的存储空间还是很大的，可以包容一些消耗。

栈的顺序存储相⽐链式存储CPU⾼速缓存命中率较高，且没有内存碎片。所以栈的实现⼀般我们使 用顺序存储。