【C】初阶数据结构5 -- 栈
前面学习了两种最基本的数据结构 -- 顺序表和链表，接下来就可以基于这两种数据结构来实现其他数据结构了。其实，其他的数据结构的物理结构要么是数组，要么就是链表，所以学好顺序表和链表是学好其他数据结构的基础。接下里，我们就来看一个新的数据结构 -- 栈。
目录
1 栈的概念与特点
2 栈的结构
1） 逻辑结构
2） 物理结构
3 栈的基本操作的实现
1） 初始化和销毁
2） 入栈与出栈、
（1） 入栈
（2） 出栈
3） 取栈顶元素、判空、获取有效元素个数
4 代码
重点一 栈的特点1 栈的概念与特点
栈：一种特殊的线性表，其只允许在一端进行插入和删除数据。插入和删除数据的一端叫做栈顶，另一端叫做栈底。
入栈（压栈）：往栈中插入数据的操作叫做入栈。
出栈：栈中删除数据的操作叫做出栈。
特点：栈中的数据遵循LIFO原则(last in first out)，也就是后进先出原则。
栈的特点特别重要，一般使用栈都是因为其后进先出的特点，下面来做一个题来理解一下其后进先出的特点：
假设有一个栈，数据入栈的先后顺序为 a b c d e ，请在以下选项中选出错误的出栈顺序（）
A. a b c d e B. c b d a e
C. d b c a e D. e d c b a该题的正确答案为 C，因为如果 d 先出栈的话，说明 a，b，c 均以入栈，如何要接着出栈的话，应是 c 先出栈，而不是 b 先出栈。
需要注意的一点就是，出栈顺序并不是等数据全部入栈之后才能出栈。比如 A 选项，就是入栈一个数据，然后出栈一个数据。
重点二 栈的结构2 栈的结构
1） 逻辑结构
我们可以把栈想象成以下的一个结构：
2） 物理结构
栈的物理结构既可以选择用链式结构来实现，也可以选择用数组，也就是顺序表来实现。这里选择使用数组来实现，因为栈后进先出的特性，规定了其只能在尾部进行插入和删除数据，而对于顺序表来说，在尾部插入和删除数据又十分方便，所以这里选择使用顺序表来实现栈。
既然是使用顺序表来实现栈，所以栈的结构和顺序表十分相似，只不过就是把 size 变为了 top，用来表示栈的顶部元素的位置：
//将int定义为栈里面的数据类型
typedef int STDataType;
//栈的结构
typedef struct Stack
{
STDataType* arr;//栈中的存放数据的数组
int capacity;//栈的容量大小
int top;//栈顶
}ST;
重点三 实现栈3 栈的基本操作的实现
对于一个栈来说，其主要操作只有入栈、出栈、取栈顶元素、初始化、销毁、判空、获取有效元素个数。
1） 初始化和销毁
栈的初始化和销毁与顺序表可以说是一模一样，这里就不做多余讲解，可以去回顾一下顺序表（也可以看下面代码理解一下）。
2） 入栈与出栈、
（1） 入栈
入栈的操作就相当于顺序表中的尾差，其基本过程如图所示：
可以看到，就是顺序表的尾插操作，只不过就是把 size 变成了 capacity 而已。
（2） 出栈
出栈就是顺序表的尾删，所以只需要让 --top 就可以了。
3） 取栈顶元素、判空、获取有效元素个数
这3个操作的实现都很简单。取栈顶元素就是返回 arr 数组中 top - 1 下标的数据，但要注意栈要非空，才能返回栈顶元素，所以要先对栈是否为空断言；判空就是判断 top 是否等于0；获取有效元素个数就是返回 top 。
4 代码
Stack.h文件：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int capacity;
int top;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//栈是否为空
bool STEmpty(ST* ps);Stack.c文件：
#include"Stack.h"
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{
//相当于顺序表的尾插
assert(ps);
//如果数组满了。需要增容
if (ps->capacity == ps->top)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail！\n");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//不要忘记让top++
ps->arr[ps->top++] = x;
}
//栈是否为空
bool STEmpty(ST* ps)
{
assert(ps);
//判断top是否为0就可以了
return ps->top == 0;
}
//出栈
void STPop(ST* ps)
{
//相当于顺序表的尾删
assert(!STEmpty(ps));
--ps->top;
}
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(ps);
//栈不能为空
assert(!STEmpty(ps));
//只取栈顶元素，不删除数据
int pos = ps->top - 1;
return ps->arr[pos];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}test.c文件：
#include"Stack.h"
void Test4()
{
ST st;
STInit(&st);
//测试入栈
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
for (int i = 0; i < st.top; i++)
{
printf("%d ", st.arr[i]);
}
printf("\n");
//测试出栈与取栈顶元素
STPop(&st);
STPop(&st);
STPop(&st);
STPop(&st);
//STPop(&st);
/*int ret = STTop(&st);
printf("%d ", ret);
printf("\n");
for (int i = 0; i < st.top; i++)
{
printf("%d ", st.arr[i]);
}
printf("\n");*/
bool ret1 = STEmpty(&st);
if (ret1)
{
printf("栈为空！\n");
}
else
{
printf("栈不为空！\n");
}
int ret = STSize(&st);
printf("%d ", ret);
STDestroy(&st);
}
int main()
{
Test4();
return 0;
}可以看到实现栈，其实就是实现顺序表的部分接口，学好顺序表和链表是实现其他数据结构的基础。所以一定要把基础学扎实，才能越学越好。