数据结构数组栈的实现

Hello，今天我们来实现一下数组栈，学完这个我们又更进一步了。

一、栈

栈的概念

栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。
进行数据的插入和删除只在栈顶实现，另一端就是栈底。
栈的元素是后进先出。

压栈：栈的数据进入就是压栈
出栈：栈的数据删除就叫出栈

我们画一个原理图让大家比较好理解一下。

这一过程叫做pop出栈

我们上述的过程都是在栈顶实现出栈入栈，并不能像顺序表和单链表那样从任意位置删除和增加，但这就是栈的性质，我们后面会讲它的作用。

实现栈我们可以用链表产生节点的方式链接他们，但是也可以用数组下标访问的方式，类似顺序表这样的方法
那这两个方法哪个好呢，我们来比较一下。

因为栈的性质我们不得从栈顶出栈和入栈，如果我们实现的时候是链表的方式，那必然会存在一个问题，就是我们的时间复杂度是O（N）我们需要遍历一遍数组，这样的话栈好像变得“土”，所以用数组的方式更快的提高效率，

二、栈的定义

typedef int StackDataType;
#define N 100
struct Stack
{StackDataType arry[N];StackDataType top;
};

这是静态栈，在顺序表的时候我们就讲过静态栈存在缺点，最大的缺点就是不能开辟空间，100个最多只能存100个数据，如果我只使用10个int空间就存在浪费了，如果我要存储1000个数据，我们的空间又不够了，这就会造成一系列问题，所以我们改一下，变成动态栈，我们来实现一下吧。

typedef int StackDataType;
typedef struct Stack
{StackDataType* arry;int top;int capacity;
}Stack;

有了结构体还是老样子，我们来实现一下接口函数，开整！
初始化栈

void StackInit(Stack* pst)
{assert(pst);pst->arry = NULL;pst->capacity = pst->top = 0;
}

初始化栈这个大家肯定会了。

销毁

void StackDestory(Stack* pst)
{assert(pst);free(pst->arry);pst->capacity = pst->top = 0;}

判断栈是否为空

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

现在我们要实现一个入栈的方法，入栈的时候我们需要检查一下我们的内存空间是不是满了，和顺序表一样的道理，如果满了我们就需要扩容。所以在入栈的时候需要判断一下它空间有没有满。

void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;StackDataType* tmp = (StackDataType*)realloc(pst->arry, sizeof(int) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}pst->arry = tmp;pst->capacity = newcapacity;}pst->arry[pst->top - 1] = x;pst->top++;}

这和我们顺序表的尾插一摸一样，现在看大家肯定觉得简单很多了。
有了入栈，那就有出栈。

void StackPop(Stack* pst)
{assert(pst);if (pst->top > 0){pst->top--;}
}

因为我们上面写了一个判断该数是不是为空我们也可以写成

void StackPop(Stack* pst)
{assert(pst);if (!StackEmpty(pst)){pst->top--;}
}

返回栈顶数据

StackDataType StackTop(Stack* pst)
{assert(pst);return pst->arry[pst->top - 1];
}

统计栈里有多少数

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

完整代码

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//typedef int StackDataType;
//#define N 100
//struct Stack
//{
//	StackDataType arry[N];
//	StackDataType top;
//};typedef int StackDataType;
typedef struct Stack
{StackDataType* arry;int top;int capacity;
}Stack;void StackInit(Stack* pst);void StackDestory(Stack* pst);bool StackEmpty(Stack* pst);void StackPush(Stack* pst, StackDataType x);void StackPop(Stack* pst);StackDataType StackTop(Stack* pst);int StackSize(Stack* pst);

#include"Stack.h"void StackInit(Stack* pst)
{assert(pst);pst->arry = NULL;pst->capacity = pst->top = 0;
}void StackDestory(Stack* pst)
{assert(pst);free(pst->arry);pst->capacity = pst->top = 0;}bool StackEmpty(Stack* pst)
{assert(pst);return pst->top == 0;
}void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;StackDataType* tmp = (StackDataType*)realloc(pst->arry, sizeof(int) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}pst->arry = tmp;pst->capacity = newcapacity;}pst->arry[pst->top - 1] = x;pst->top++;}void StackPop(Stack* pst)
{assert(pst);if (pst->top > 0){pst->top--;}
}void StackPop(Stack* pst)
{assert(pst);if (!StackEmpty(pst)){pst->top--;}
}StackDataType StackTop(Stack* pst)
{assert(pst);return pst->arry[pst->top - 1];
}int StackSize(Stack* pst)
{assert(pst);return pst->top;
}

栈的应用也有很多，后面会分享给大家，我们下次再见