前面我们了解到线性表中的顺序表、链表等结构，今天我们探讨新的一种线性表——栈。
那么我们开始栈的探讨之旅吧。
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;
}
以上就是栈的一些基本操作啦，谢谢大家支持！
