[数据结构与算法]P5—＜栈（动态版）＞《数据结构(C语言版)》

栈（动态版）的功能实现（<入栈，出栈>&<顺序，乱序>）测试示例：

完整源码：

Test.c:

#include "Stack.h"
//栈的测试

//按照顺序压栈、出栈
void TestStack1()
{
	ST st;
	StackInit(&st);
	1.一个一个创建数据，可连续也可不连续
	//StackPush(&st, 1);
	//StackPush(&st, 2);
	//StackPush(&st, 3);
	//StackPush(&st, 4);
	//StackPush(&st, 5);
	
	//2.使用循环压栈创建数据
	for (int i = 0; i < 6; ++i)
	{
		StackPush(&st, i);
	}

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");

	StackDestroy(&st);
}
//乱序压栈、出栈
void TestStack2()
{
	ST st;
	StackInit(&st);
	//1.一个一个创建数据，可连续也可不连续
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	//1、2、3压栈，3出栈，再进行4、5压栈，再打印整体出栈
	printf("%d ", StackTop(&st));
	StackPop(&st);
	StackPush(&st, 4);
	StackPush(&st, 5);


	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");

	StackDestroy(&st);
}
int main()
{
	TestStack1();
	TestStack2();

	return 0;
}

Stack.c:

#include "Stack.h"
//栈的接口功能函数
//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;

}

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

//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//需要注意top的位置，取决于如何对top的初始化
	//本程序top的初始化位置为0
	
	//判断是否栈满，栈满即需要扩容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//此处的4是随机合理给定，无特别规定，*2是合理利用空间
		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		//relloc给的是总的新空间的大小
		if (ps->a == NULL)
		{
			printf("relloc fail\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	写法1
	//if (ps->top > 0)
	//{
	//	return false;
	//}
	//else
	//{
	//	return true;
	//}
	
	//写法2
	return ps->top == 0;
}
//栈顶
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	return ps->a[ps->top - 1];
}
//查看栈的数据
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

Stack.h:

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//静态(不常用）
//struct Stack
//{
//	int a[N];
//	int top; //栈顶的位置
//};

//动态
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top; //栈顶的位置
	int capacity; //容量
}ST;

//接口功能函数

//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
//栈顶
STDataType StackTop(ST* ps);
//查看栈的数据
int StackSize(ST* ps);

二、栈的功能实现分析：

1.栈的概念及结构：

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

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

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