· 数据结构之顺序栈与链式栈

——————————————本文旨在交流计算机技术，欢迎指正————————————— 上一大章，我们深入讲解了链表的内容，这一章，我们详细介绍一种较为简单的数据结构———栈。首先，我们介绍栈是什么：栈是一种单向的结构，其中栈的底部是固定的，不可以进出，我们可操作的部分只有栈顶，来进行出入栈操作。如图：那么，这种结构的优越性在哪里呢？我们可知这种出站入栈的方式可以和好的追踪上一步的痕迹，所以在计算机应用中，我们常用的快捷键“ctrl+z”回溯键就是利用栈的原理实现的。同时，栈还是定义局部变量时操作系统为我们自动分配的一段有限空间。

下面，我们来介绍顺序栈：在书写顺序栈之前，我们先要了解四个概念：满栈递增，满栈递减，空栈递增，空栈递减。下面附上代码：

1
//空栈递增
2
a1.data[a1.pos]=1;//先赋值
3
a1.pos++;//后移动pos位置
4
//每次完成一次后pos指向空的栈位置

空栈递增： ——————————————————————————————————————————

1
//满栈递增
2
pos++;//先更新pos指向位置
3
a1.data[a1.pos]=1;//再赋值
4
//每次完成后pos指向当前赋值的位置

满栈递增： ———————————————————————————————————————————

1
//空栈递减
2
a1.data[a1.pos]=e;//先赋值
3
pos--;//后更新位点
4
//只不过是从栈顶最大值开始，大往小递减，指向赋值下小的那一个空栈点

空栈递减： ———————————————————————————————————————————

1
//满栈递减
2
pos--;//先更新指向
3
a1.data[a1.pos]=e;//后更新栈值
4
//从栈顶大往小递减顺序，pos指向离栈底更近的一个空栈值

满栈递减： —————————————————————————————————————————————————————————————————————————————————————— 好了，现在我们已经介绍完顺序栈的基本结构和入栈方法了，下面，我们来完成一下这个数据结构吧！ 1、首先是.h中的声明及（不懂的可以看我第一章讲的.h文件的作用）：

1
typedef int Element;
2
#define MaxStackSize 5
3

4
typedef struct {
5
STACK_SIZE
6
int top;
7
} ArrayStack;
8

9
/* 递增空栈 */
10
void initArrayStack(ArrayStack *stack);
11

12
void pushArrayStack(ArrayStack *stack, Element e);
13
void popArrayStack(ArrayStack *stack);
14

15
Element getTopArrayStack(const ArrayStack *stack);
16

17
int isEmptyArrayStack(const ArrayStack *stack);
18
int isFullArrayStack(const ArrayStack *stack);

2、然后是初始化：

1
void initArrayStack(ArrayStack* stack) {
2
memset(stack->data, 0, sizeof(stack->data));
3
stack->top = 0;
4
}

3、增删改查操作（这里我们经常使用递增空栈来完成）：

1
void pushArrayStack(ArrayStack* stack, Element e) {
2
stack->data[stack->top] = e;
3
++stack->top;
4
}
5
//增加函数
6

7
void popArrayStack(ArrayStack* stack) {
8
--stack->top;
9
}
10
//删除函数
11

12
Element getTopArrayStack(const ArrayStack* stack) {
13
int pos = stack->top - 1;
14
return stack->data[pos];
15
}
16
//查询函数
17

18
int isEmptyArrayStack(const ArrayStack* stack) {
19
return stack->top == 0;
20
}
21
//判断是否是空栈
22

23
int isFullArrayStack(const ArrayStack* stack) {
24
return stack->top == MaxStackSize;
25
}
26
//判断是否满栈

好了，我们已经讲解完成了顺序栈操作，接下来，我们来讲解链式栈的操作。类比表结构，既然有顺序表，我们就有链式表。与链式表原理，我们也有链式栈（同理，链式栈的逻辑结构也是旨在寻找零散空间插入，不再是顺序栈的那种整块空间但是实际空间分配还是依照操作系统来分配）：关于链式栈的构建，因为我们每次出栈的时候是找前一次的入栈并指向它，所以我们入栈的时候地址域指针指向前一个。下面是一个概念图：由此，模仿链式结构，我们可以实现链式栈： 1、头文件.h文件的编写：

1
typedef int Element;
2
#include "common.h"
3

4
typedef struct _node {
5
Element data;
6
struct _node *next;
7
} StackNode;//节点
8

9
typedef struct {
10
StackNode *top;
11
int count;
12
} LinkStack;//栈底
13

14
LinkStack *createLinkStack();
15
void releaseLinkStack(LinkStack *stack);
16

17
int pushLinkStack(LinkStack *stack, Element e);
18
int popLinkStack(LinkStack *stack, Element *e);

2、实现增删改查

1
#include "linkStack.h"
2
#include
3
#include
4

5
//创建栈
6
LinkStack* createLinkStack() {
7
LinkStack* link_stack = malloc(sizeof(LinkStack));
8
if (link_stack == NULL) {
9
fprintf(stderr, "linkStack malloc failed!\n");
10
return NULL;
11
}
12
link_stack->top = NULL;
13
link_stack->count = 0;
14

15
return link_stack;
16
}
17

18
//销毁栈
19
void releaseLinkStack(LinkStack* stack) {
20
if (stack) {
21
while (stack->top) {
22
StackNode *tmp = stack->top;
23
stack->top = tmp->next;
24
free(tmp);
25
--stack->count;
26
}
27
printf("stack count: %d\n", stack->count);
28
}
29
}
30

31
//入栈
32
int pushLinkStack(LinkStack* stack, Element e) {
33
StackNode *node = malloc(sizeof(StackNode));
34
if (node == NULL) {
35
fprintf(stderr, "Stack Node malloc failed!\n");
36
return -1;
37
}
38
node->data = e;
39

40
node->next = stack->top;
41
stack->top = node;
42
++stack->count;
43
return 0;
44
}
45

46
//出栈
47
int popLinkStack(LinkStack* stack, Element* e) {
48
if (stack->top == NULL) {
49
fprintf(stderr, "stack empty!\n");
50
return -1;
51
}
52
*e = stack->top->data;
53
StackNode *tmp = stack->top;
54
stack->top = tmp->next;
55
free(tmp);
56
--stack->count;
57
return 0;
58
}

好了，我们已经讲解完毕顺序栈和链式栈，下面去练习一下吧~~~ ——————————————希望能对你有所帮助！——————————————————

音乐

文章分享

评论区

音乐

音乐

文章目录