前言

1. 《数据结构系列首页》是数据结构系列文章的首页，其中会逐步更新各种数据结构的实现，有兴趣的选手可以一看。
2. 首页中不仅有各种数据结构的实现，还有学习数据结构必备的基础知识，如果有选手觉得自己的基础不太牢固，可以先将搞定基础知识，之后再攻克数据结构这一部分的内容。
3. 由于我也是刚开始学习数据结构这门课程，所以如果发现文章中存在错误，希望大家可以直接指出，我将第一时间修改。
4. 更多数据结构的实现请见《数据结构系列文章》，我会在学习完新的数据结构后不断更新其中的内容。

开场白

栈是一种特殊的线性表，其限定仅能在表尾进行插入和删除操作，并把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），栈又称为先进后出（Last In First Oout）的线性表，简称LIFO结构。考虑到上一篇文章静态顺序栈的缺陷，即无法动态扩充栈的存储容量，本篇采用动态一维数组实现栈的顺序存储，同时实现了对其的一些操作。

具体实现

头文件

#include <stdio.h>	// printf、scanf函数所在的头文件
#include <stdlib.h> // exit函数所在的头文件
#include <malloc.h>	// malloc、realloc、free函数所在的头文件
#include <math.h>	// 宏OVERFLOW所在的头文件，OVERFLOW的值为3

// 按照严蔚敏老师书中的编程习惯，定义如下4个宏
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

typedef int Status;		// Status是函数返回值的类型，其返回的是函数执行结果的状态
typedef int ElemType;	// ElemType是元素的数据类型，想要整体改变元素的数据类型只需改变ElemType前的数据类型即可

// 定义动态顺序栈的存储结构
#define STACK_INIT_SIZE 10 // 动态顺序栈存储空间的初始容量
#define STACK_INCREMENT 5  // 动态顺序表存储空间的增量
typedef struct MallocStack
{
	ElemType* base; // 存储动态顺序栈的基地址
	int top;		// 存储栈顶元素的下标
	int stacksize;	// 存储当前栈的最大容量
}STACK; // 等同于 struct MallocStack

函数声明

void init_stack(STACK&);
void destroy_stack(STACK&);
void clear_stack(STACK&);
Status is_empty(STACK&);
Status is_full(STACK&);
int get_length(STACK&);
Status get_top_element(STACK&, ElemType&);
void push_stack(STACK&, ElemType);
Status pop_stack(STACK&, ElemType&);
void traverse_stack(STACK&, void(*visit)(ElemType));
void print(ElemType);

操作函数的实现

// 初始化栈S
void init_stack(STACK& S)
{
	S.base = (ElemType*)malloc(sizeof(ElemType) * STACK_INIT_SIZE); // 动态构造一维数组
	if (!S.base) // 如果S.base不存在，则分配失败并退出程序
		exit(OVERFLOW);

	S.top = -1; // 分配成功后，将栈顶指针置为-1
	S.stacksize = STACK_INIT_SIZE; // 将栈的最大容量置为STACK_INIT_SIZE
}

// 销毁栈S
void destroy_stack(STACK& S)
{
	free(S.base); // 释放S.base所指向的动态空间
	S.base = NULL; // 将S.base置为空
	S.top = -1; // 将栈顶指针置为-1
	S.stacksize = 0; // 将栈的最大容量置为0
}

// 清空栈S中的元素
void clear_stack(STACK& S)
{
	S.top = -1; // 将栈顶指针置为-1即可
}

// 判断栈S是否为空
Status is_empty(STACK& S)
{
	if (S.top == -1) // 如果栈顶指针等于-1，则栈为空
		return TRUE;
	else
		return FALSE;
}

// 判断栈S是否已满
Status is_full(STACK& S)
{
	if (S.top + 1 == S.stacksize) // 如果栈顶指针加1等于当前栈的最大容量，则栈已满
		return TRUE;
	else
		return FALSE;
}

// 获取栈S中当前有效元素的个数
int get_length(STACK& S)
{
	return S.top + 1; // 返回栈顶指针加1的值即可
}

// 用e返回栈S的栈顶元素
Status get_top_element(STACK& S, ElemType& e)
{
	if (is_empty(S)) // 如果栈为空，则无法获取栈顶元素
		return ERROR;

	e = S.base[S.top]; // 将当前栈顶元素的值赋给e
	return OK;
}

// 将元素e压入栈S的栈顶
void push_stack(STACK& S, ElemType e)
{
	if (is_full(S)) // 如果栈已满，则需要扩大栈的存储空间
	{
		ElemType* newbase = (ElemType*)realloc(S.base, sizeof(ElemType) * (S.stacksize + STACK_INCREMENT));
		// 使用realloc函数以S.base为起止地址，重新分配S.stacksize + STACK_INCREMENT个元素的空间，后赋给newbase
		if (!newbase) // 如果newbase不存在，则分配失败并退出程序
			exit(OVERFLOW);

		S.base = newbase; // 将newbase赋给S.base
		S.stacksize += STACK_INCREMENT; // 将栈的当前最大容量扩大STACK_INCREMENT个
	}

	S.base[++S.top] = e; // 先将当前栈顶指针加1，再将e的值赋给以栈顶指针为下标的元素
	// 上行代码等同于 S.top++; S.base[S.top]; 这两行代码
}

// 用e返回栈S的栈顶元素，并将该元素出栈
Status pop_stack(STACK& S, ElemType& e)
{
	if (is_empty(S)) // 如果栈为空，则无法出栈
		return ERROR;

	e = S.base[S.top--]; // 将当前栈顶元素的值赋给e，再将栈顶指针减1
	// 上行代码等同于 e = S.base[S.top]; S.top--; 这两行代码
	return OK;
}

// 从栈底到栈顶遍历栈S中的元素
/*
	注意：遍历不一定代表要将整个栈中的内容输出
		  也有可能是将整个栈中的元素翻倍
		  或者对栈中的元素做其它的的操作
		  所以形参使用的是函数指针，用以应对不同的操作情况
		  函数指针的内容见基础内容中的《指向函数的指针》
*/
void traverse_stack(STACK& S, void(*visit)(ElemType))
{
	int i;

	for (i = 0; i <= S.top; i++) // 从栈底元素向栈顶元素遍历
		visit(S.base[i]); // 每次循环都调用传递给指针变量visit的函数

	printf("\n"); // 为了输出结果美观，这里打印一个换行符
}

// 输出元素e
void print(ElemType e)
{
	printf("%d ", e);
}

主函数

int main()
{
	STACK S;
	ElemType e;
	int i;

	init_stack(S);
	printf("初始化栈后，S.base = %p，S.stacksize = %d\n", S.base, S.stacksize);

	for (i = 1; i <= 10; i++)
		push_stack(S, i);

	printf("从栈底到栈顶的元素依次为：");
	traverse_stack(S, print);

	printf("栈是否已满？%d(1:是 0:否)\n", is_full(S));

	push_stack(S, 11);
	printf("入栈第11个元素后，S.base = %p，S.stacksize = %d\n", S.base, S.stacksize);

	printf("栈是否已满？%d(1:是 0:否)\n", is_full(S));

	if (pop_stack(S, e))
		printf("弹出的栈顶元素为%d\n", e);
	else
		printf("出栈失败\n");

	printf("栈是否已满？%d(1:是 0:否)\n", is_full(S));

	if (get_top_element(S, e))
		printf("栈顶元素为%d，栈的长度为%d\n", e, get_length(S));

	clear_stack(S);
	printf("清空栈后，S.base = %p，S.stacksize = %d\n", S.base, S.stacksize);
	printf("清空栈后，栈是否为空？%d(1:是 0:否)\n", is_empty(S));

	destroy_stack(S);
	printf("销毁栈后，S.base = %p，S.stacksize = %d\n", S.base, S.stacksize);

	return 0;
}

结尾语

1. 本篇文章利用动态一维数组实现了顺序栈，故将本篇文章的标题起为动态顺序栈的实现。
2. 顺序栈是线性表中的一种特殊存储结构，其中的特殊之处值得大家细心体会。
3. 对比静态顺序栈，动态顺序栈的功能更加强大，因为动态顺序栈可以在使用过程中随时扩充栈的容量。
4. 大家应重点理解各算法中的细节，而不是仅仅大概明白算法的思路。
5. 更重要的是，一定要通过程序将各算法自行实现一遍，这对数据结构的学习将大有裨益。
6. 如果大家有不明白的地方，或者发现程序中有错误之处，欢迎大家通过评论区与我交流。