数据结构之顺序栈与链式栈
——————————————本文旨在交流计算机技术，欢迎指正—————————————
上一大章，我们深入讲解了链表的内容，这一章，我们详细介绍一种较为简单的数据结构———栈。
首先，我们介绍栈是什么：栈是一种单向的结构，其中栈的底部是固定的，不可以进出，我们可操作的部分只有栈顶，来进行出入栈操作。如图：
那么，这种结构的优越性在哪里呢？我们可知这种出站入栈的方式可以和好的追踪上一步的痕迹，所以在计算机应用中，我们常用的快捷键“ctrl+z”回溯键就是利用栈的原理实现的。同时，栈还是定义局部变量时操作系统为我们自动分配的一段有限空间。
下面，我们 来介绍顺序栈：
在书写顺序栈之前，我们先要了解四个概念：满栈递增，满栈递减，空栈递增，空栈递减。
下面附上代码：
//空栈递增a1.data[a1.pos]=1;//先赋值a1.pos++;//后移动pos位置//每次完成一次后pos指向空的栈位置空栈递增：
——————————————————————————————————————————
//满栈递增pos++;//先更新pos指向位置a1.data[a1.pos]=1;//再赋值//每次完成后pos指向当前赋值的位置满栈递增：
———————————————————————————————————————————
//空栈递减a1.data[a1.pos]=e;//先赋值pos--;//后更新位点//只不过是从栈顶最大值开始，大往小递减，指向赋值下小的那一个空栈点空栈递减：
———————————————————————————————————————————
//满栈递减pos--;//先更新指向a1.data[a1.pos]=e;//后更新栈值//从栈顶大往小递减顺序，pos指向离栈底更近的一个空栈值满栈递减：
—————————————————————————————————————————————————————————————————————————————————————— 好了，现在我们已经介绍完顺序栈的基本结构和入栈方法了，下面，我们来完成一下这个数据结构吧！
1、首先是.h中的声明及（不懂的可以看我第一章讲的.h文件的作用）：
typedef int Element;#define MaxStackSize 5
typedef struct {STACK_SIZEint top;} ArrayStack;
/* 递增空栈 */void initArrayStack(ArrayStack *stack);
void pushArrayStack(ArrayStack *stack, Element e);void popArrayStack(ArrayStack *stack);
Element getTopArrayStack(const ArrayStack *stack);
int isEmptyArrayStack(const ArrayStack *stack);int isFullArrayStack(const ArrayStack *stack);2、然后是初始化：
void initArrayStack(ArrayStack* stack) {memset(stack->data, 0, sizeof(stack->data));stack->top = 0;}3、增删改查操作（这里我们经常使用递增空栈来完成）：
void pushArrayStack(ArrayStack* stack, Element e) {stack->data[stack->top] = e;++stack->top;}//增加函数
void popArrayStack(ArrayStack* stack) {--stack->top;}//删除函数
Element getTopArrayStack(const ArrayStack* stack) {int pos = stack->top - 1;return stack->data[pos];}//查询函数
int isEmptyArrayStack(const ArrayStack* stack) {return stack->top == 0;}//判断是否是空栈
int isFullArrayStack(const ArrayStack* stack) {return stack->top == MaxStackSize;}//判断是否满栈好了，我们已经讲解完成了顺序栈操作，接下来，我们来讲解链式栈的操作。类比表结构，既然有顺序表，我们就有链式表。与链式表原理，我们也有链式栈（同理，链式栈的逻辑结构也是旨在寻找零散空间插入，不再是顺序栈的那种整块空间但是实际空间分配还是依照操作系统来分配）：
关于链式栈的构建，因为我们每次出栈的时候是找前一次的入栈并指向它，所以我们入栈的时候地址域指针指向前一个。
下面是一个概念图：
由此，模仿链式结构，我们可以实现链式栈：
1、头文件.h文件的编写：
typedef int Element;#include "common.h"
typedef struct _node {Element data;struct _node *next;} StackNode;//节点
typedef struct {StackNode *top;int count;} LinkStack;//栈底
LinkStack *createLinkStack();void releaseLinkStack(LinkStack *stack);
int pushLinkStack(LinkStack *stack, Element e);int popLinkStack(LinkStack *stack, Element *e);2、 实现增删改查
#include "linkStack.h"#include#include
//创建栈LinkStack* createLinkStack() {LinkStack* link_stack = malloc(sizeof(LinkStack));if (link_stack == NULL) {fprintf(stderr, "linkStack malloc failed!\n");return NULL;}link_stack->top = NULL;link_stack->count = 0;
return link_stack;}
//销毁栈void releaseLinkStack(LinkStack* stack) {if (stack) {while (stack->top) {StackNode *tmp = stack->top;stack->top = tmp->next;free(tmp);--stack->count;}printf("stack count: %d\n", stack->count);}}
//入栈int pushLinkStack(LinkStack* stack, Element e) {StackNode *node = malloc(sizeof(StackNode));if (node == NULL) {fprintf(stderr, "Stack Node malloc failed!\n");return -1;}node->data = e;
node->next = stack->top;stack->top = node;++stack->count;return 0;}
//出栈int popLinkStack(LinkStack* stack, Element* e) {if (stack->top == NULL) {fprintf(stderr, "stack empty!\n");return -1;}*e = stack->top->data;StackNode *tmp = stack->top;stack->top = tmp->next;free(tmp);--stack->count;return 0;}好了，我们已经讲解完毕顺序栈和链式栈，下面去练习一下吧~~~ ——————————————希望能对你有所帮助！——————————————————
支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或打赏支持！
音乐
暂未播放