一、栈的概念及结构
1、概念
栈：一种特殊的线性表，其只允许在表尾进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2、结构
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。如果用尾作栈顶（尾插、尾删），那么要用双向链表更好。如果要用单链表实现，那么就用头去作栈顶更好（头插、头删），这样入栈和出栈的效率都是 O(1)。因为栈只会在一端进行插入和删除操作，用数组效率还是比较高，数组在尾上插入数据的代价比较小。当然，也会存在一些问题，就是每次空间不够，要重新开辟空间，可能会造成一些内存浪费。
双向链表虽然不需要考虑内存大小的问题，但实际上价值并不高，在这里使用单向链表好于双向链表，能节省空间。但是，从各个角度而言， 栈的实现还是选择数组的结构来实现更好一些，不需要增容和释放，空间上更加节省，且CPU 高速缓存命中更高一些。
1、栈的顺序存储结构
数组的首元素作为栈底，另外一端作为栈顶，同时定义一个变量 top 来记录栈顶元素在数组中的位置。
2、栈的链表存储结构
单链表的尾部作为栈底，头部作为栈顶，方便插入和删除（进栈头插，出栈头删），头指针和栈顶指针 top 合二为一。
三、栈的实现
1、创建文件
- test.c（主函数、测试栈各个接口功能）
- Stack.c（栈接口函数的实现）
- Stack.h（栈的类型定义、接口函数声明、引用的头文件）
2、Stack.h 头文件代码
下面是动态增长的栈的结构，在实际中更常用。
#pragma once #include <stdio.h> #include <assert.h> // assert #include <stdlib.h> // realloc #include <stdbool.h> // bool // 支持动态增长的栈 typedef int STDataType; // 类型重命名 栈中元素类型先假设为int typedef struct Stack { STDataType* a; // 指向动态开辟的数组 int top; // 记录栈顶位置 int capacity; // 栈的容量大小 }Stack; // 初始化栈 void StackInit(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps);
四、Stack.c 中各个接口函数的实现
1、栈的初始化
// 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; //思路一： ps->top = 0; // 意味着top指向栈顶数据的下一个 //思路二： //ps->top = -1; // 意味着top指向栈顶数据 ps->capacity = 0; }
思路二：
2、栈的销毁
// 销毁栈 void StackDestroy(Stack* ps) { assert(ps); if (ps->a) { free(ps->a); } ps->a = NULL; ps->top = 0; ps->capacity = 0; }
3、入栈
// 入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) // 检查栈空间是否满了 { int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); // 扩容至新容量 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; // 更新容量 } ps->a[ps->top] = x; // 将新增元素放入栈顶空间 ps->top++; // 栈顶指针加一 }
4、出栈
// 出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); // 栈不能为空 ps->top--; // 栈顶指针减一 }
5、获取栈顶元素
// 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); // 栈不能为空 return ps->a[ps->top-1]; }
6、获取栈中有效元素个数
// 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; }
7、检测栈是否为空
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps) { assert(ps); //写法一： /*if (ps->top == 0) { return true; } else { return false; }*/ //写法二： return ps->top == 0; }
五、代码整合
// Stack.c #include "Stack.h" // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = 0; // 意味着top指向栈顶数据的下一个 ps->capacity = 0; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); if (ps->a) { free(ps->a); } ps->a = NULL; ps->top = 0; ps->capacity = 0; } // 入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) // 检查栈空间是否满了 { int newCapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); //扩容至新容量 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; // 更新容量 } ps->a[ps->top] = x; // 将新增元素放入栈顶空间 ps->top++; // 栈顶指针加一 } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); // 栈不能为空 ps->top--; // 栈顶指针减一 } // 获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); // 栈不能为空 return ps->a[ps->top-1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; }
六、测试栈的功能
栈的实现不能像顺序表一样，去实现一个打印函数来遍历栈并输出，这样做就不符合栈的特点了（只能在栈顶插入删除，后进先出），所以我们这样来实现出栈：获取并打印栈顶元素，再删除栈顶元素，继续获取新的栈顶元素。
