【数据结构】顺序栈的C语言实现(通过顺序表实现栈的顺序存储)

简介: 【数据结构】顺序栈的C语言实现(通过顺序表实现栈的顺序存储)

顺序表实现顺序栈的原理

栈是一种特殊的线性表,它只能在线性表的一端进行插入删除操作,允许插入删除的一端称为栈顶,另一端称为栈底。栈的顺序存储即顺序栈是指,用一块连续的内存来存放一个栈,类似于数组,各元素在内存中是一个挨一个的。既然栈也是线性表,那么栈就可以通过线性表来实现,实现顺序栈只需在顺序表的插入删除操作时,只限定在一端操作即可。线性表的顺序存储文章链接如下

image.png

线性表可以在头部和尾部进行插入删除,而栈只能在栈顶进行插入删除,那么应该选择顺序表的哪一端作为栈顶呢?

假如线性表头部作为栈顶,如上图所示,也就是说线性表的0号位置处作为栈顶,那么每次插入删除,都需要后面的元素都后移或前移(在0号位置插入时,需要原来的0号变为1号,原来的1号变为2号,以此类推,每个元素都要往后移动一位;删除0号元素时,0号位置空出,应把1号前移变为0号,2号前移变为1号,每个元素都要前移一位),会造成大量的数据移动。所以,应选择线性表的尾部作为栈顶,这样插入删除都不要其他元素移动。

顺序栈的API

1. typedef void SequenceStack;
2. typedef void SequenceStackNode;
3. 
4. SequenceStack* SequenceStack_Create(int capacity);
5. 
6. void SequenceStack_Destroy(SequenceStack* stack);
7. 
8. void SequenceStack_Clear(SequenceStack* stack);
9. 
10. int SequenceStack_Push(SequenceStack* stack, SequenceStackNode* node);
11. 
12. SequenceStackNode* SequenceStack_Top(SequenceStack* stack);
13. 
14. SequenceStackNode* SequenceStack_Pop(SequenceStack* stack);
15. 
16. int SequenceStack_Size(SequenceStack* stack);

顺序栈的API实现

1. SequenceStack* SequenceStack_Create(int capacity)
2. {
3.  SequenceStack* pTemp = NULL;
4.  pTemp = (SequenceStack*)LinearList_Create(capacity);
5.  if (pTemp == NULL)
6.  {
7.    printf("LinearList_Create() err\n");
8.    return NULL;
9.  }
10.   return pTemp;
11. }
12. 
13. void SequenceStack_Destroy(SequenceStack* stack)
14. {
15.   LinearList_Destroy((LinearList*)stack);
16. }
17. 
18. void SequenceStack_Clear(SequenceStack* stack)
19. {
20.   LinearList_Clear((LinearList*)stack);
21. }
22. 
23. int SequenceStack_Push(SequenceStack* stack, SequenceStackNode* node)
24. {
25.   return LinearList_Insert((LinearList*)stack, node, LinearList_Length((LinearList*)stack));
26. }
27. 
28. SequenceStackNode* SequenceStack_Top(SequenceStack* stack)
29. {
30.   return (SequenceStackNode*)LinearList_Get((LinearList*)stack, LinearList_Length((LinearList*)stack) - 1);
31. }
32. 
33. SequenceStackNode* SequenceStack_Pop(SequenceStack* stack)
34. {
35.   return (SequenceStackNode*)LinearList_Delete((LinearList*)stack, LinearList_Length((LinearList*)stack) - 1);
36. }
37. 
38. int SequenceStack_Size(SequenceStack* stack)
39. {
40.   return LinearList_Length((LinearList*)stack);
41. }

代码资源已经上传

image.png

相关文章
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
98 1
|
7天前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
25天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
44 5
|
2月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
|
存储 程序员 C语言
程序员之路:C语言中存储类别
程序员之路:C语言中存储类别
146 0
|
1月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
66 23
|
1月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
71 15
|
1月前
|
C语言
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
61 24

热门文章

最新文章