数据结构之线性表（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;
}