目录摘要一概念二栈的实现框架三函数实现1初始化2入栈3出栈4返回栈顶元素5获取元素个数6判空7销毁栈四代码1Stack.h2Stack.c五测试功能摘要本文从零实现一个栈拥有入栈出栈等功能详细解释每个函数怎么编写最后测试函数功能...一概念栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则二栈的实现框架1文件分配本文采用三个文件进行实现1Stack.h对实现函数以及栈的声明2Stack.c相关函数的实现3text.c对程序的使用检测2assert所有的函数都要对接受到的结构体指针进行assert确保程序的严谨性。而且部分还会assert是否存在元素比如pop函数删除函数。3底层结构数组和链表都可以实现栈但数组更好须知单链表肯定选择头作为栈顶进行头插头删这样复杂度恒为O(1)数组栈顶为数组尾部直接下标插入即可①优势一(元素大小)单链表元素为一个个的节点节点内部有值有指针并且不能逆序查找元素而数组仅需有值索引和--就可以随意查找元素②优势二(栈顶移动)单链表则需要用两个指针表示栈顶和栈底入栈需要改变栈顶指针的指向而数组栈底就是0栈顶就是size入栈则size即可不仅方便还不用额外创建指针注size就是元素个数所以size就可以作为下一个待插入位置的索引在栈中我们常常把size改为top来表示栈顶并且在不同的设计实现中栈顶的意义不同栈顶可以是指最上面的元素也可以指待插入元素的位置本博客栈顶指待插入元素的位置可以直接使用top表示但不管是哪种设计入栈和出栈所表现出的效果是一致的只是代码的实现方式不同罢了三函数实现前提栈的声明解释①a是一个指针用来指向一个数组。②top就是栈顶表示数组中下一个可插入元素的位置的下标top是数组的下标所以top为0不仅代表数组是空的也代表下一个可插入元素的位置的下标③capacity代表栈的容量。④将类型进行一个typedef方便之后的类型改变带来的修改只需要修改int即可。⑤将结构体重命名为LTNode方便之后使用。1初始化解释初始化就是得到一个空栈①对指针的初始化一般是置空。②其他变量top和capacity的赋值0。2入栈解释①入栈第一步应该判断容量是否允许插入若top和capacity相等则只有两种情况第一种第一次入栈。第二种容量满了此处用了三目操作符pc-capacity是否为0是的话就让容量变成4否则让容量翻倍.②不管是哪种情况都会去开辟空间给a所以我们采用realloc。此处两个重点Q1为什么第一次开辟不用mallocA1我们后面会在a的空间基础上进行再次开辟所以realloc才对其次我们初始化的时候a NULL了在realloc函数中接收的指针为NULLrealloc就等同于malloc了也就相当于第一次开辟用的是malloc。Q2为什么不直接用a来接收开辟的空间而是用了一个tmp中间变量最后在赋值给aA2如果用a接收如果realloc开辟失败但是a如果之前不是空栈那之前的栈元素也会丢失而用一个tmp去接受再去判断是否开辟成功会更好保护a之前的数据。③将x赋给a[top]因为top表示数组中下一个可插入元素的位置的下标它的值同时也等同于元素的个数。3出栈解释①对ps进行assert确保结构体指针不可能为空对ps-top0进行assert确保栈中有元素能够进行出栈②让top--即可达到出栈效果下次入栈直接覆盖掉3这个元素即可4返回栈顶元素解释①assert 是否存在元素没有元素何来栈顶②因为top表示数组中下一个可插入元素的位置的下标所以下标为top-1即可返回栈顶元素。5获取元素个数解释①因为top的值和元素的个数一致所以直接返回top即可。6判空解释①bool值要么为true要么为falsetop为0则true反之false。7销毁栈解释①释放a置空a其余变量赋值0即可。四代码1Stack.h#pragma once #pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h // 定义栈中存储的数据类型别名 typedef int STDataType; // 定义栈结构体 typedef struct Stack { STDataType* a; // 指向动态分配数组的指针用于存储栈元素 int top; // 栈顶索引top表示下一个待插入元素的位置 (即栈的大小) int capacity; // 栈当前的容量 (数组的大小) }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);2Stack.c#define _CRT_SECURE_NO_WARNINGS 1 #include Stack.h // 初始化栈 void STInit(ST* ps) { assert(ps); ps-a NULL; ps-capacity 0; ps-top 0; } // 销毁栈 void STDestroy(ST* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top ps-capacity 0; } // 入栈 void STPush(ST* ps, STDataType x) { assert(ps); // 11:40 if (ps-top ps-capacity) { int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity); if (tmp NULL) { perror(realloc fail); exit(-1); } ps-a tmp; ps-capacity newCapacity; } ps-a[ps-top] x; ps-top; } // 出栈 void STPop(ST* ps) { assert(ps); // assert(ps-top 0); --ps-top; } // 获取栈顶元素 STDataType STTop(ST* ps) { assert(ps); // assert(ps-top 0); return ps-a[ps-top - 1]; } // 获取栈中元素个数 int STSize(ST* ps) { assert(ps); return ps-top; } // 判断栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps-top 0; }五测试功能test.c#define _CRT_SECURE_NO_WARNINGS 1 #include stdio.h #include Stack.h int main() { ST st; // 创建一个栈对象 // 1. 初始化栈 printf(--- 测试初始化 ---\n); STInit(st); printf(栈是否为空? %s\n, STEmpty(st) ? 是 : 否); // 应输出 是 printf(栈的大小: %d\n, STSize(st)); // 应输出 0 // 2. 入栈操作 printf(\n--- 测试入栈 (Push) ---\n); STPush(st, 10); STPush(st, 20); STPush(st, 30); printf(压入 10, 20, 30 后\n); printf(栈顶元素: %d\n, STTop(st)); // 应输出 30 printf(栈的大小: %d\n, STSize(st)); // 应输出 3 printf(栈是否为空? %s\n, STEmpty(st) ? 是 : 否); // 应输出 否 // 3. 出栈操作 printf(\n--- 测试出栈 (Pop) ---\n); printf(弹出栈顶元素: %d\n, STTop(st)); // 应输出 30 STPop(st); // 弹出 30 printf(弹出后新的栈顶元素: %d\n, STTop(st)); // 应输出 20 printf(栈的大小: %d\n, STSize(st)); // 应输出 2 // 4. 再次入栈 printf(\n--- 再次入栈 ---\n); STPush(st, 40); printf(压入 40 后\n); printf(栈顶元素: %d\n, STTop(st)); // 应输出 40 printf(栈的大小: %d\n, STSize(st)); // 应输出 3 // 5. 清空栈 printf(\n--- 测试清空栈 ---\n); while (!STEmpty(st)) { printf(弹出: %d , STTop(st)); STPop(st); } printf(\n清空后栈的大小: %d\n, STSize(st)); // 应输出 0 printf(栈是否为空? %s\n, STEmpty(st) ? 是 : 否); // 应输出 是 // 6. 销毁栈 printf(\n--- 测试销毁 ---\n); STDestroy(st); printf(栈已销毁。\n); return 0; } [ 作者 ] shylyly [ 首次发布 ] 2024.5.22❌ [ 最新修改 ] 2026.5.25 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
栈的实现
目录摘要一概念二栈的实现框架三函数实现1初始化2入栈3出栈4返回栈顶元素5获取元素个数6判空7销毁栈四代码1Stack.h2Stack.c五测试功能摘要本文从零实现一个栈拥有入栈出栈等功能详细解释每个函数怎么编写最后测试函数功能...一概念栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则二栈的实现框架1文件分配本文采用三个文件进行实现1Stack.h对实现函数以及栈的声明2Stack.c相关函数的实现3text.c对程序的使用检测2assert所有的函数都要对接受到的结构体指针进行assert确保程序的严谨性。而且部分还会assert是否存在元素比如pop函数删除函数。3底层结构数组和链表都可以实现栈但数组更好须知单链表肯定选择头作为栈顶进行头插头删这样复杂度恒为O(1)数组栈顶为数组尾部直接下标插入即可①优势一(元素大小)单链表元素为一个个的节点节点内部有值有指针并且不能逆序查找元素而数组仅需有值索引和--就可以随意查找元素②优势二(栈顶移动)单链表则需要用两个指针表示栈顶和栈底入栈需要改变栈顶指针的指向而数组栈底就是0栈顶就是size入栈则size即可不仅方便还不用额外创建指针注size就是元素个数所以size就可以作为下一个待插入位置的索引在栈中我们常常把size改为top来表示栈顶并且在不同的设计实现中栈顶的意义不同栈顶可以是指最上面的元素也可以指待插入元素的位置本博客栈顶指待插入元素的位置可以直接使用top表示但不管是哪种设计入栈和出栈所表现出的效果是一致的只是代码的实现方式不同罢了三函数实现前提栈的声明解释①a是一个指针用来指向一个数组。②top就是栈顶表示数组中下一个可插入元素的位置的下标top是数组的下标所以top为0不仅代表数组是空的也代表下一个可插入元素的位置的下标③capacity代表栈的容量。④将类型进行一个typedef方便之后的类型改变带来的修改只需要修改int即可。⑤将结构体重命名为LTNode方便之后使用。1初始化解释初始化就是得到一个空栈①对指针的初始化一般是置空。②其他变量top和capacity的赋值0。2入栈解释①入栈第一步应该判断容量是否允许插入若top和capacity相等则只有两种情况第一种第一次入栈。第二种容量满了此处用了三目操作符pc-capacity是否为0是的话就让容量变成4否则让容量翻倍.②不管是哪种情况都会去开辟空间给a所以我们采用realloc。此处两个重点Q1为什么第一次开辟不用mallocA1我们后面会在a的空间基础上进行再次开辟所以realloc才对其次我们初始化的时候a NULL了在realloc函数中接收的指针为NULLrealloc就等同于malloc了也就相当于第一次开辟用的是malloc。Q2为什么不直接用a来接收开辟的空间而是用了一个tmp中间变量最后在赋值给aA2如果用a接收如果realloc开辟失败但是a如果之前不是空栈那之前的栈元素也会丢失而用一个tmp去接受再去判断是否开辟成功会更好保护a之前的数据。③将x赋给a[top]因为top表示数组中下一个可插入元素的位置的下标它的值同时也等同于元素的个数。3出栈解释①对ps进行assert确保结构体指针不可能为空对ps-top0进行assert确保栈中有元素能够进行出栈②让top--即可达到出栈效果下次入栈直接覆盖掉3这个元素即可4返回栈顶元素解释①assert 是否存在元素没有元素何来栈顶②因为top表示数组中下一个可插入元素的位置的下标所以下标为top-1即可返回栈顶元素。5获取元素个数解释①因为top的值和元素的个数一致所以直接返回top即可。6判空解释①bool值要么为true要么为falsetop为0则true反之false。7销毁栈解释①释放a置空a其余变量赋值0即可。四代码1Stack.h#pragma once #pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h // 定义栈中存储的数据类型别名 typedef int STDataType; // 定义栈结构体 typedef struct Stack { STDataType* a; // 指向动态分配数组的指针用于存储栈元素 int top; // 栈顶索引top表示下一个待插入元素的位置 (即栈的大小) int capacity; // 栈当前的容量 (数组的大小) }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);2Stack.c#define _CRT_SECURE_NO_WARNINGS 1 #include Stack.h // 初始化栈 void STInit(ST* ps) { assert(ps); ps-a NULL; ps-capacity 0; ps-top 0; } // 销毁栈 void STDestroy(ST* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top ps-capacity 0; } // 入栈 void STPush(ST* ps, STDataType x) { assert(ps); // 11:40 if (ps-top ps-capacity) { int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2; STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity); if (tmp NULL) { perror(realloc fail); exit(-1); } ps-a tmp; ps-capacity newCapacity; } ps-a[ps-top] x; ps-top; } // 出栈 void STPop(ST* ps) { assert(ps); // assert(ps-top 0); --ps-top; } // 获取栈顶元素 STDataType STTop(ST* ps) { assert(ps); // assert(ps-top 0); return ps-a[ps-top - 1]; } // 获取栈中元素个数 int STSize(ST* ps) { assert(ps); return ps-top; } // 判断栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps-top 0; }五测试功能test.c#define _CRT_SECURE_NO_WARNINGS 1 #include stdio.h #include Stack.h int main() { ST st; // 创建一个栈对象 // 1. 初始化栈 printf(--- 测试初始化 ---\n); STInit(st); printf(栈是否为空? %s\n, STEmpty(st) ? 是 : 否); // 应输出 是 printf(栈的大小: %d\n, STSize(st)); // 应输出 0 // 2. 入栈操作 printf(\n--- 测试入栈 (Push) ---\n); STPush(st, 10); STPush(st, 20); STPush(st, 30); printf(压入 10, 20, 30 后\n); printf(栈顶元素: %d\n, STTop(st)); // 应输出 30 printf(栈的大小: %d\n, STSize(st)); // 应输出 3 printf(栈是否为空? %s\n, STEmpty(st) ? 是 : 否); // 应输出 否 // 3. 出栈操作 printf(\n--- 测试出栈 (Pop) ---\n); printf(弹出栈顶元素: %d\n, STTop(st)); // 应输出 30 STPop(st); // 弹出 30 printf(弹出后新的栈顶元素: %d\n, STTop(st)); // 应输出 20 printf(栈的大小: %d\n, STSize(st)); // 应输出 2 // 4. 再次入栈 printf(\n--- 再次入栈 ---\n); STPush(st, 40); printf(压入 40 后\n); printf(栈顶元素: %d\n, STTop(st)); // 应输出 40 printf(栈的大小: %d\n, STSize(st)); // 应输出 3 // 5. 清空栈 printf(\n--- 测试清空栈 ---\n); while (!STEmpty(st)) { printf(弹出: %d , STTop(st)); STPop(st); } printf(\n清空后栈的大小: %d\n, STSize(st)); // 应输出 0 printf(栈是否为空? %s\n, STEmpty(st) ? 是 : 否); // 应输出 是 // 6. 销毁栈 printf(\n--- 测试销毁 ---\n); STDestroy(st); printf(栈已销毁。\n); return 0; } [ 作者 ] shylyly [ 首次发布 ] 2024.5.22❌ [ 最新修改 ] 2026.5.25 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
