做网站建设的目的,深圳百度推广网站建设,烟花代码html,网站企业备案代理文章目录 一、引言二、栈的基本概念1、栈是什么2、栈的实现方式对比3、函数栈帧 三、栈的实现1、结构体定义2、初始化3、销毁4、显示5、数据操作 四、分析栈1、优点2、缺点 五、总结1、练习题2、源代码 一、引言
栈#xff0c;作为一种基础且重要的数据结构#xff0c;在计算… 文章目录 一、引言二、栈的基本概念1、栈是什么2、栈的实现方式对比3、函数栈帧 三、栈的实现1、结构体定义2、初始化3、销毁4、显示5、数据操作 四、分析栈1、优点2、缺点 五、总结1、练习题2、源代码 一、引言
栈作为一种基础且重要的数据结构在计算机科学领域中有着广泛的应用。它不仅为函数调用提供了必要的支持还在算法设计和问题解决中发挥着关键作用。本文将对栈的基本概念、实现方式以及函数栈帧进行详细的介绍和分析。 二、栈的基本概念
1、栈是什么
栈是一种特殊的线性数据结构其只允许在固定的一端进行插入和删除操作。插入和删除的这一端被称为栈顶而另一端则被称为栈底。栈遵循后进先出的原则即最后插入的元素会最先被删除。这种特性使得栈在算法设计和问题解决中具有独特的优势。 2、栈的实现方式对比
数组实现将数组的尾部充当栈顶数据的插入与删除操作变得非常高效。同时数组的结构使得其CPU高速缓存的命中率较高。唯一的缺陷就是扩容或缩容会有一定的性能开销。链表实现采用单链表结构将链表头部设为栈顶数据的插入与删除操作同样能高效完成。但链表需要额外的存储空间来保存指针信息且由于链表的结构CPU高速缓存的命中率相对较低。此外链表实现的复杂度相较于数组实现也更高一些。
3、函数栈帧
在函数调用过程中系统会为每个函数分配一个栈帧。栈帧中存储了函数的局部变量、参数以及返回地址等信息。当函数执行完毕后其栈帧会被销毁从而释放占用的栈空间。函数栈帧的分配和销毁过程体现了栈的后进先出原则。
函数栈帧的存在使得函数调用具有嵌套性即一个函数可以调用另一个函数而被调用的函数又可以继续调用其他函数。这种嵌套调用关系通过栈来维护确保了函数调用的正确性和稳定性。 三、栈的实现
1、结构体定义
首先定义了栈的数据结构。栈使用动态数组来存储元素同时记录了栈顶索引和栈的容量。
typedef int DataType;
typedef struct Stack {DataType* array;int top;int capacity;
}S;2、初始化
接下来实现了栈的初始化函数。该函数为栈分配内存并初始化栈顶索引和容量。
void Init(S* ps, int capacity)
{assert(ps ! NULL capacity 0);DataType* pos (DataType*)malloc(sizeof(DataType) * capacity);if (pos NULL){fprintf(stderr, 内存分配失败);exit(EXIT_FAILURE);}ps-array pos;ps-capacity capacity;ps-top -1;
}3、销毁
实现了栈的销毁函数。该函数释放栈所占用的内存并将栈的指针、容量和栈顶索引重置为初始状态。
void Destroy(S* ps)
{if (ps NULL)return;free(ps-array);ps-array NULL;ps-capacity 0;ps-top -1;
}4、显示
实现了栈的显示函数。该函数遍历栈中的元素并调用用户定义的打印函数来打印每个元素。
void Print(S* ps, void (*Prin)(DataType))
{assert(ps ! NULL);for (int i ps-top; i 0; i--){Prin(ps-array[i]);}printf(\n);
}5、数据操作
void Push(S* ps, DataType data)
{assert(ps ! NULL);if (ps-top ps-capacity - 1){int capacity ps-capacity 0 ? 2 : ps-capacity * 2;DataType* pos (DataType*)realloc(ps-array, sizeof(DataType) * capacity * 2);if (pos NULL){fprintf(stderr, 内存分配失败);exit(EXIT_FAILURE);}ps-array pos;ps-capacity capacity;}ps-array[(ps-top)] data;
}void Pop(S* ps)
{assert(ps ! NULL ps-top ! -1);if (ps-capacity 64 ps-top ps-capacity / 3){int capacity ps-capacity / 3;DataType* pos (DataType*)realloc(ps-array, sizeof(DataType) * capacity);if (pos NULL){fprintf(stderr, 内存分配失败);exit(EXIT_FAILURE);}ps-array pos;ps-capacity capacity;}ps-top--;
}DataType Top(S* ps)
{assert(ps ! NULL);return ps-array[ps-top];
}四、分析栈
1、优点
操作简便栈提供了简洁的接口如push入栈和pop出栈使得元素的操作非常直观和方便。高效性对于大多数栈实现push和pop操作的时间复杂度均为O(1)保证了高效的元素访问速度。应用场景广泛栈在多种算法和数据结构中都有重要应用如深度优先搜索DFS、表达式求值、括号匹配等。
2、缺点
访问限制栈只允许在栈顶进行元素的插入和删除操作无法直接访问栈内的其他元素限制了其灵活性。 五、总结
1、练习题
有效的括号最小栈用栈操作构建数组堆盘子
2、源代码
对于栈的源代码我已经开源在GItee传送门。
