数据结构—数组栈的实现

前言：各位小伙伴们我们前面已经学习了带头双向循环链表，数据结构中还有一些特殊的线性表，如栈和队列，那么我们今天就来实现数组栈。

目录：

一、
栈的概念
二、
栈的实现
三、
代码测试

栈的概念：

栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则，压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶，出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈的实现：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

接口：

// 初始化栈
void STInit(ST* pst);
// 销毁栈
void STDestroy(ST* pst);// 入栈
void STPush(ST* pst, STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶元素
STDataType STTop(ST* pst);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* pst);
// 获取栈中有效元素个数
int STSize(ST* pst);

这里我们需要三个文件，一个头文件，一个文件用来实现我们的各种接口，一个文件用来测试我们的代码。

头文件（Stack.h）：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack
{int* a;int top;		// 标识栈顶位置的int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);bool STEmpty(ST* pst);
int STSize(ST* pst);

我们的top是栈顶，如果我们的top=0时，我们指向的就是栈顶元素，如果我们的top=1，那么我们的top指向的就是栈顶元素的下一个位置。

函数实现（Stack.c）

#include"Stack.h"void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}void STDestroy(ST* pst)
{}// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);// 不为空assert(pst->top > 0);pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STEmpty(ST* pst);
int STSize(ST* pst);

测试代码（test.c）

int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}printf("\n");return 0;
}

我们这里入栈五个数据，当我们的栈里面不为空时，我们就访问栈顶元素，在让栈顶元素出栈。直到我们的栈为空时，就退出循环。

int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);printf("%d ", STTop(&s));STPop(&s);printf("%d ", STTop(&s));STPop(&s);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}printf("\n");return 0;
}

这里我们可以同时入栈和出栈，我们先入栈1,2，3，在出栈，我们的栈是后入先出，也就是说我们后面入栈的元素在出栈的时候先出栈，我们出栈一个也就是3，再出栈就是2，最后入栈就是4,5。