郑州网站建设亻汉狮网络,东莞网站建设(信科分公司),皖icp阜阳网站建设,网站商城注意事项文章目录 引言1.栈的基本概念2.选择数组还是链表#xff1f;3. 定义栈结构4.初始化栈5.压栈操作6.弹栈操作7.查看栈顶和判断栈空9.销毁栈操作10.测试并且打印栈内容栈的实际应用结论 引言
栈是一种基本但强大的数据结构#xff0c;它在许多算法和系统功能中扮演着关键角色。… 文章目录 引言1.栈的基本概念2.选择数组还是链表3. 定义栈结构4.初始化栈5.压栈操作6.弹栈操作7.查看栈顶和判断栈空9.销毁栈操作10.测试并且打印栈内容栈的实际应用结论 引言
栈是一种基本但强大的数据结构它在许多算法和系统功能中扮演着关键角色。在这篇文章中我们将深入探讨如何在实现一个栈从基本概念到具体的代码实现再到实际应用场景的探讨。
1.栈的基本概念
在深入代码之前先简单介绍栈的概念。栈是一个项的有序集合其中添加推入和删除弹出项总发生在同一端称为“栈顶”。他是后进先出的就好像弹夹里面的子弹一样 2.选择数组还是链表
数组的优点在于实现简单访问时间快。但其缺点是大小固定可能会有空间浪费或不足的问题。 链表的优点在于可以动态调整大小内存利用率高。但其缺点是相对于数组访问时间可能会稍慢。 我们用数组来实现 3. 定义栈结构
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDataType;
typedef struct Stack
{STDataType* a;STDataType top; STDataType capacity;
}ST;接口
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);4.初始化栈
初始化是栈实现中的第一步。我们需要将栈顶 top 的初始值设为0以表示栈为空,在这个实现中栈被定义为包含动态数组、栈顶指针和容量的结构体。初始化函数 STInit 负责设置这些属性的初始状态。
// 初始化栈
void STInit(ST* pst)
{assert(pst);pst-a NULL; // 初始时数组指针为空pst-top 0; // 栈顶指针初始为0表示栈为空pst-capacity 0; // 初始容量为0
}5.压栈操作
在实现压栈操作时我们要考虑栈可能满的情况。如果栈已满我们应该阻止进一步的压栈并给出适当的反馈。
// 检查并扩展栈的容量
void SLCheckCapacity(ST* pst)
{assert(pst);if (pst-top pst-capacity){int newCapacity (pst-capacity 0) ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(1); // 如果内存分配失败则退出程序}pst-a tmp;pst-capacity newCapacity;}
}// 向栈中推入一个元素
void STPush(ST* pst, STDataType x)
{assert(pst);SLCheckCapacity(pst); // 检查并扩展容量pst-a[pst-top] x; // 存放元素pst-top; // 栈顶指针增加
}6.弹栈操作
弹栈时我们需要确保栈不为空。如果尝试从空栈中弹出元素应该返回一个错误指示。
// 从栈中弹出一个元素
void STPop(ST* pst)
{assert(pst);assert(pst-top 0); // 确保栈不为空pst-top--; // 栈顶指针减少
}7.查看栈顶和判断栈空
这些操作相对简单但它们对于栈的有效使用至关重要。
// 获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0); // 确保栈不为空return pst-a[pst-top - 1]; // 返回栈顶元素
}// 检查栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0; // 如果栈顶指针为0则栈为空
}
9.销毁栈操作
在这个静态数组实现中destroy 函数不是必须的但是我们使用了动态分配的内存则需要在此释放内存。
// 销毁栈
void STDestroy(ST* pst)
{assert(pst);free(pst-a); // 释放栈内部的数组空间pst-a NULL; // 将数组指针置为空pst-top 0; // 栈顶指针重置为0pst-capacity 0; // 容量重置为0
}10.测试并且打印栈内容
int main()
{ST stack; // 定义栈变量ST* pst stack; // pst 指向 stackSTInit(pst); // 初始化栈// 向栈中添加元素STPush(pst, 1);STPush(pst, 2);STPush(pst, 3);STPush(pst, 4);// 打印并弹出栈中的元素while (!STEmpty(pst)){printf(%d , STTop(pst));STPop(pst);}printf(\n);STDestroy(pst); // 销毁栈return 0;
}运行结果如下 栈的实际应用
栈在计算机科学中有着广泛的应用。从函数调用的内存管理到算法中的临时数据存储栈的应用无处不在。理解栈如何在这些场景中工作对于充分利用其潜力至关重要。 结论
栈不仅是一种基本的数据结构而且是理解更复杂系统和算法的基石。通过在c语言中实现和应用栈我们不仅能够加深对这一结构的理解还能够提高我们的编程技巧和问题解决能力。我希望这篇文章能够帮助你更好地理解和实现栈。如果你有任何问题或想分享你的经验请在评论区留言。
