数据结构之线性表（4）

前面我们了解到线性表中的顺序表、链表等结构，今天我们探讨新的一种线性表——栈。
那么我们开始栈的探讨之旅吧。

1.栈的基本概念

1.1栈（Stack）：

是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。
在这里插入图片描述

1.2栈的特点：

因为栈只能在栈顶进行操作，所以栈的特点是先进后出（FILO）

2.栈的实现

对栈的实现，有多种实现的方法
1.顺序栈

静态顺序栈

#define MAX_SIZE 100
typedef struct StackNods
{
	datatype data[MAX_SIZE];
	size_t top;
	size_t capacity;
}ST;

缺点：存储空间有限，多了浪费空间，少了不够用

动态顺序栈

typedef struct StackNods
{
	datatype *array;
	size_t top;
	size_t capacity;
}ST;

2.链栈

typedef struct StackNods
{
	datatype data;
	struct StackNods* next;
}ST;

缺点：需要浪费空间存储下一个结点的指针（地址）

综合三种结构，我们采用顺序中的动态栈来完成栈的相关操作：

2.1 栈的初始化

在对栈的初始化之前，有两种情况
top初始化为0的情况：
在这里插入图片描述

top初始化为-1的情况
在这里插入图片描述
我们从top初始化为0探讨栈的相关操作

//栈的初始化
void Stackinit(ST *pt)
{
	assert(pt);
	pt->array = (datatype*)malloc(sizeof(datatype) * 4);
	if (pt->array == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	pt->capacity = 4;
	pt->top = 0;
}

2.2压栈

//压栈
void StackPush(ST* pt,datatype x)
{
	assert(pt);
	ST* tmp=NULL;
	if (pt->top == pt->capacity)//表示栈满了 -》扩容
	{
		tmp = (datatype*)realloc(pt->array, pt->capacity * sizeof(datatype) * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			pt->array = tmp;
			pt->capacity*=2;//容量变成两倍
		}
	}
	pt->array[pt->top] = x;
	pt->top++;
}

2.3出栈

void StackPop(ST* pt)
{
	assert(pt);//栈空了，调用top，直接种植程序报错
	assert(pt->top > 0);
	pt->top--;
}

2.4取栈顶元素

//取栈顶元素
datatype StackTop(ST* pt)
{
	assert(pt);
	assert(pt->top > 0);
	return pt->array[pt->top - 1];
}

2.5求栈内元素个数

//求栈内元素个数
int StackSize(ST* pt)
{
	assert(pt);
	return pt->top;
}

2.6判栈空

//判栈空
bool StackEmpty(ST* pt)//用布尔类型判断
{
	assert(pt);
	return pt->top == 0;
}

2.7栈打印

//打印
void StackPrintf(ST pt)//打印时不需要对站内元素进行修改，所以不需要传指针
{
	while (pt.top)
	{
		printf("%d ", pt.array[pt.top - 1]);
		StackPop(&pt);
	}		
}

2.8栈销毁

//栈销毁
void StackDestory(ST* pt)
{
	assert(pt);
	free(pt->array);
	pt->array = NULL;
	pt->capacity = pt->top = 0;
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int datatype;
typedef struct StackNods
{
	datatype * array;
	size_t top;
	size_t capacity;
}ST;


//栈的初始化
void Stackinit(ST *pt)
{
	assert(pt);
	pt->array = (datatype*)malloc(sizeof(datatype) * 4);
	if (pt->array == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	pt->capacity = 4;
	pt->top = 0;
}
//压栈
void StackPush(ST* pt,datatype x)
{
	assert(pt);
	ST* tmp=NULL;
	if (pt->top == pt->capacity)//表示栈满了 -》扩容
	{
		tmp = (datatype*)realloc(pt->array, pt->capacity * sizeof(datatype) * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			pt->array = tmp;
			pt->capacity*=2;//容量变成两倍
		}
	}
	pt->array[pt->top] = x;
	pt->top++;
}
//出栈
void StackPop(ST* pt)
{
	assert(pt);
	//栈空了，调用Top，直接种植程序报错
	assert(pt->top > 0);
	pt->top--;
}
//取栈顶元素
datatype StackTop(ST* pt)
{
	assert(pt);
	assert(pt->top > 0);
	return pt->array[pt->top - 1];
}
//求栈内元素个数
int StackSize(ST* pt)
{
	assert(pt);
	return pt->top;
}
//判栈空
bool StackEmpty(ST* pt)
{
	assert(pt);
	return pt->top == 0;
}
//
void StackPrintf(ST pt)
{
	while (pt.top)
	{
		printf("%d ", pt.array[pt.top - 1]);
		StackPop(&pt);
	}	
	printf("\n");
}
//栈销毁
void StackDestory(ST* pt)
{
	assert(pt);
	free(pt->array);
	pt->array = NULL;
	pt->capacity = pt->top = 0;
}
int main()
{
	ST pt;
	Stackinit(&pt);
	StackPush(&pt, 1);
	StackPush(&pt, 1);
	StackPush(&pt, 2);
	StackPush(&pt, 3);
	StackPush(&pt, 4);
	StackPrintf(pt);
	printf("栈内元素个数有%d 个",StackSize(&pt));
	StackDestory(&pt);
	return 0;
}