【数据结构】顺序栈的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++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
50 10
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
344 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
|
7天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等