数据结构入门（C语言版）栈和队列之栈的介绍及实现 |
您所在的位置：网站首页 › 栈的定义及初始化 › 数据结构入门（C语言版）栈和队列之栈的介绍及实现 |
数据结构入门（C语言版）栈和队列之栈的介绍及实现
|
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。 栈可以使用两种主要的数据结构实现：数组和链表。 使用数组实现的栈称为顺序栈（或者静态栈），其基本操作的时间复杂度为 O(1)。在实现时需要预先分配一定大小的数组作为存储空间，当栈的元素个数超过数组的大小时，需要进行扩容操作。 使用链表实现的栈称为链式栈（或者动态栈），其基本操作的时间复杂度同样为 O(1)。相比顺序栈，链式栈没有固定的大小限制，可以动态添加和删除节点，因此实现上更为灵活。 除了以上两种主要的数据结构，还有一些其他的数据结构可以用于实现栈，例如双向链表等。但是在实际应用中，数组和链表是最常见的两种栈实现方式。 栈的结构体与接口的定义 1、静态栈结构定长的静态栈结构 代码如下： typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int _top; // 栈顶 }Stack; 2、动态栈结构静态结构实际中一般不实用，所以我们主要实现下面的支持动态增长的栈 代码如下： typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶 int capacity;//容量 }ST;虽然这里使用的是动态扩容 但还是用顺序结构来实现栈 以便于初学者的理解 3、栈的接口定义代码如下： void StackInit(ST* ps);//初始化栈 void StackPush(ST* ps, STDataType x);//入栈 void StackPop(ST* ps);// 出栈 STDataType StackTop(ST* ps);// 获取栈顶元素 int StackSize(ST* ps);// 获取栈中有效元素个数 bool StackEmpty(ST* ps);// 检测栈是否为空，如果为空返回ture，如果不为空返回false void StackDestroy(ST* ps);// 销毁栈可以看到栈的接口函数比起之前的顺序表和链表都要简单很多 其实实现起来也是非常的简单，接下来我们实现这些接口 栈的接口实现 ①初始化栈(StackInit)代码如下： void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; // ps->top = -1; ps->capacity = 0; }栈的初始化先将元素置空，栈顶指向0，当然你也可以指向-1，后面的接口函数也要做相应调整，可以根据自己习惯来设定，没有固定标准，然后容量初始化为0。 ②入栈(StackPush)代码如下： void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; }入栈的写法有点类似顺序表的尾插，首先是一个经典的三目操作符判断容量，容量不够则进行增容，再向内存申请空间，这里的if是为了防止申请失败而找不到中断原因写的一个提示，类似断言，将元素插入，增容，再将栈顶指向新元素，栈顶++完成入栈操作。 ③出栈(StackPop)代码如下： void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps));//判断是否为空 ps->top--; }这里的出栈就很简单了，先进行断言，这里的StackEmpty函数在后面实现，直接将top–就完成出栈操作了。 ④栈顶(StackTop)代码如下： STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }栈顶值返回只要将a[最高位下标]返回即可，如果你初始化定义的top=-1,那么这里就是 ps->a[ps->top]的值了。 ⑤栈元素个数(StackSize)代码如下： int StackSize(ST* ps) { assert(ps); return ps->top; }栈元素个数直接返回top值即可，如果你初始化定义的top=-1,那么这里就是top++的值了 ⑥检测栈是否为空(StackEmpty)代码如下： bool StackEmpty(ST* ps) { assert(ps); if (ps->top == 0) { return true; } else { return false; } }首先返回类型可以是int，这里我使用bool类型也是一样的，只不过我这返回的是逻辑值true或是false，如果为空返回ture，如果不为空返回false。这段代码还有更简洁的方式， 代码如下： bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }同样返回的是逻辑值，更简洁高效。 ⑦销毁栈(StackDestroy)代码如下： void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }实现销毁栈，先释放元素所占空间，再置空进行初始化即可。 结语其实不管是栈还是队列，实现方式也都很简单，虽然简单，但也是同样重要的知识点，一定要好好理解和掌握，这一节就到这里了，下一节我们再讲讲队列的概念及接口实现。 制作不易，如有不正之处敬请指出，感谢大家的来访，UU们的观看是我坚持下去的动力，在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！ |
【本文地址】