初阶数据结构之栈的实现

前言：实现栈之前，先来了解一下什么是栈。

1. 栈的概念

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

压栈：栈的插入操作叫做进栈（压栈，入栈），入数据在栈顶。

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

2. 栈的底层结构如何选择

现在我们已经了解了栈的结构特性了。那么我们该如何实现栈呢？先来看一个问题，顺序表和链表我们已经学习过了，那么栈的底层结构应该选择哪一个呢？

如果底层结构采用数组实现，在插入元素时只需要在指定的位置插入元素即可，删除元素时，- -top就可以了。唯一的缺点就是会存在空间浪费。

如果采用链表来实现栈，每一次插入数据元素都要开辟空间并且需要遍历链表，使新节点成为链表的尾节点；删除数据元素时也需要遍历链表，将尾节点的空间还给操作系统，还要保证尾节点的前驱节点的next保存NULL，避免成为野指针。优点是按需申请和释放空间，不存在空间浪费。缺点是时间复杂度为O(N)，空间复杂度也为O(N)。

综合下来，采用数组的结构来实现栈更合适。解决了这个问题，接下来就该实现栈了。

3. 栈的实现

3.1 栈的定义

typedef int SDataType;typedef struct Stack{SDataType* a;int capacity;//栈的容量大小int top;//栈实际存储数据的个数}Stack;

3.2 栈的接口

//初始化栈void StackInit(Stack* ps);//栈顶入数据void StackPush(Stack* ps, SDataType x);//栈顶出数据SDataType StackTop(Stack* ps);//删除栈顶数据void StackPop(Stack* ps);//栈是否为空bool StackEmpty(Stack* ps);//栈的大小int StackSize(Stack* ps);//销毁栈void StackDestroy(Stack* ps);

3.2.1 初始化栈

//初始化栈void StackInit(Stack* ps){assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;}

3.2.2 栈顶入数据

//栈顶入数据void StackPush(Stack* ps, SDataType x){assert(ps);//增容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * newcapacity);if (NULL == tmp){printf(\"StackPush():realloc fail\\n\");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;}

首先判断栈空间是否足够，不够就需要扩容。空间足够直接在top的位置插入数据，更新栈中数据元素的个数。刚开始栈的容量为0，因此需要特殊处理，如果栈的容量为0，就将栈的容量设置为4，否则，就开2倍的空间。

3.2.3 栈是否为空

//栈是否为空bool StackEmpty(Stack* ps){assert(ps);//选择一种即可if (ps->top == 0){return true;}else{return false;}//return ps->top == 0;}

top是记录栈中数据元素的个数的，top为0，栈为空，否则，栈不为空。

3.2.4 栈顶出数据

//栈顶出数据SDataType StackTop(Stack* ps){assert(ps);//ps->top>0，说明栈顶有数据可以出去//assert(ps->top > 0);assert(!StackEmpty(ps));return ps->a[ps->top - 1];}

首先应该保证栈不能为空，其次数组中最后一个元素就是栈顶的元素，数组支持随机访问，直接返回数组中最后一个元素即可。

3.2.5 删除栈顶元素

//删除栈顶数据void StackPop(Stack* ps){assert(ps);//说明有数据可以删除，同时避免越界问题//assert(ps->top > 0);assert(!StackEmpty(ps));ps->top--;}

栈不为空才能删除数据，直接--top就可以了。

3.2.6 栈的大小

//栈的大小int StackSize(Stack* ps){assert(ps);return ps->top;}

top是记录栈的数据个数的，直接返回top就可以了。

3.2.7 销毁栈

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

数组空间是动态申请的，因此要还给操作系统。其次把capacity和top置为0。

4. 栈的完整代码实现

Stack.h

#pragma once#include#include#include#includetypedef int SDataType;typedef struct Stack{SDataType* a;int capacity;//栈的容量大小int top;//栈实际存储数据的个数}Stack;//初始化栈void StackInit(Stack* ps);//栈顶入数据void StackPush(Stack* ps, SDataType x);//栈顶出数据SDataType StackTop(Stack* ps);//删除栈顶数据void StackPop(Stack* ps);//栈是否为空bool StackEmpty(Stack* ps);//栈的大小int StackSize(Stack* ps);//销毁栈void StackDestroy(Stack* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS#include\"Stack.h\"//初始化栈void StackInit(Stack* ps){assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;}//栈顶入数据void StackPush(Stack* ps, SDataType x){assert(ps);//增容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SDataType* tmp = (SDataType*)realloc(ps->a, sizeof(SDataType) * newcapacity);if (NULL == tmp){printf(\"StackPush():realloc fail\\n\");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;}//栈顶出数据SDataType StackTop(Stack* ps){assert(ps);//ps->top>0，说明栈顶有数据可以出去//assert(ps->top > 0);assert(!StackEmpty(ps));return ps->a[ps->top - 1];}//删除栈顶数据void StackPop(Stack* ps){assert(ps);//说明有数据可以删除，同时避免越界问题//assert(ps->top > 0);assert(!StackEmpty(ps));ps->top--;}//栈是否为空bool StackEmpty(Stack* ps){assert(ps);/*if (ps->top == 0){return true;}else{return false;}*/return ps->top == 0;}//栈的大小int StackSize(Stack* ps){assert(ps);return ps->top;}//销毁栈void StackDestroy(Stack* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}

test.c

#define _CRT_SECURE_NO_WARNINGS#include\"Stack.h\"void TestStack1(){Stack st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);SDataType ret = StackTop(&st);printf(\"%d \", ret);StackPop(&st);StackPop(&st);int size = StackSize(&st);printf(\"%d \", size);StackDestroy(&st);}int main(){TestStack1();return 0;}