当前位置:   article > 正文

数据结构(3.3)——栈的链式存储结构

数据结构(3.3)——栈的链式存储结构

链栈的定义

采用链式存储的栈成为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况通常采用单链表实现。

  1. typedef struct Linknode {
  2. int data; // 数据域
  3. struct Linknode* next; // 指针域
  4. } LiStack; // 栈类型定义

链栈的初始化

  1. // 初始化链栈的函数
  2. bool InitLiStack(LiStack* top) {
  3. top = (LiStack*)malloc(sizeof(LiStack)); // 分配头结点的内存
  4. if (top == NULL) {
  5. return false; // 分配失败,返回false
  6. }else{
  7. top->data = 0; // 初始化数据域,这里可根据需要设置
  8. top->next = NULL; // 头结点的next指针指向NULL
  9. return true; // 分配成功,返回true
  10. }

链栈的入栈操作

栈的链式存储操作其实和单链表的头插法插入很相似,我们完全可以使用单链表的头插法插入元素来模拟入栈操作

  1. //进栈操作
  2. bool Push(LiStack* top, int value) {
  3. LiStack* newNode = (LiStack*)malloc(sizeof(LiStack));//分配新结点的内存
  4. if (newNode == NULL) {
  5. return false;//分配失败,返回false
  6. }
  7. else {
  8. newNode->data = value;//设置新结点的数据域
  9. newNode->next = top;//新结点的next指针指向当前的栈顶
  10. top = newNode;//更新栈顶指针
  11. return true;//进栈成功,返回true
  12. }
  13. }

链栈的出栈操作

  1. //出栈操作
  2. bool Pop(LiStack* top, int* value) {
  3. if (top == NULL) {
  4. return false;
  5. }
  6. else {
  7. *value = top->data;//获取栈顶结点的数据
  8. LiStack* temp = top;//临时保存栈顶结点
  9. top = top->next;//更新栈顶指针
  10. free(temp);//释放栈顶结点内存
  11. return true;
  12. }
  13. }

在栈操作中,释放 temp 而不是 top 是因为 temp 指向的是即将被弹出的栈顶元素,而 top 指向的是新的栈顶元素。以下是详细解释:

  1. 栈的基本概念:栈是一种后进先出(LIFO)的数据结构。在栈中,最后插入的元素是最先被删除的。

  2. 出栈操作:出栈操作涉及从栈顶删除元素。在链式栈中,这意味着需要删除与 top 指针关联的节点。

  3. temp 的作用:在出栈操作中,temp 被用来临时存储指向当前栈顶节点的指针。这样做的目的是,在删除当前栈顶节点后,top 指针可以安全地移动到下一个节点,而不会丢失对当前栈顶节点的引用。

  4. 释放 temp:一旦 top 指针已经更新为指向下一个节点,temp 指向的节点就不再需要了。此时,释放 temp 指向的内存是安全的,因为它已经不再是栈的一部分。

  5. 不释放 toptop 指针在出栈操作后仍然指向新的栈顶节点。如果释放了 top 指向的节点,那么 top 指针将指向一个已经被释放的内存区域,这将导致未定义行为,可能引发程序崩溃。

  6. 内存管理:在链式栈中,每个节点都是动态分配的内存。当一个节点被弹出栈时,必须释放该节点的内存,以避免内存泄漏。

  7. 代码实现:在您的代码中,free(temp) 正确地释放了即将被弹出的栈顶节点的内存。如果 free(top) 被错误地调用,那么 top 指针将指向一个无效的内存区域,这将破坏栈的结构。

总结来说,释放 temp 是因为 temp 指向的是即将被移除的栈顶节点,而 top 指向的是新的栈顶节点,需要保留以维护栈的结构。

读取栈顶

  1. // 读取栈顶元素的值,不移除它
  2. bool Peek(LiStack* top, int* value) {
  3. if (top == NULL) {
  4. return false; // 栈为空,无法读取栈顶元素
  5. }
  6. else {
  7. *value = top->data; // 将栈顶元素的值赋给value指针指向的变量
  8. return true; // 成功读取栈顶元素
  9. }

在这个示例中,Peek 函数接受一个指向栈顶节点的指针 top,以及一个指向 int 类型的指针 value,用于存储栈顶元素的值。如果栈不为空,函数将栈顶元素的值赋给 value 指针指向的变量,并返回 true。如果栈为空,则返回 false。 

判空判满

在链式栈中,由于它是动态分配内存的,所以它不会像数组那样有固定的容量限制,也就不会出现“满”的情况。因此,我们只需要实现一个判断链栈是否为空的方法。

  1. bool IsEmpty(LiStack* stack) {
  2. return stack->top == NULL; // 如果栈顶指针为NULL,则栈为空
  3. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/792265
推荐阅读
相关标签
  

闽ICP备14008679号