🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解用c语言实现:“数据结构之"栈”,分别从"顺序栈"和"链栈"的接口讲解.
金句分享:
✨不是每一场雨后都有彩虹,但是晴天总是会到来!✨

前言

栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

"栈"的常见接口实现

• InitST:初始化栈
• STPush:入栈
• STPop:出栈
• STEmpty:判空(判断是否为空栈)
• PrintSTTop:打印栈顶元素
• STTop:返回栈顶元素(返回值类型:stacktype)

一、顺序栈

"顺序栈"的类型定义

如果友友们学过顺序表,这种类型可以随便拿捏.😄😄

代码:

typedef struct stack
{
stacktype* data;//一个指向连续内存空间的指针
int top;//记录栈顶元素的下标
int capacaity;
}ST;
1
2
3
4
5
6

1.1 初始化栈

top指针:
由于数组的下标是从0开始,所以我们初始化"栈"时,可以将top指针(栈顶指针)初始化为-1,这样即可代表"栈"中无数据.

capacaity :
同顺序表一样,我们可以设置初始最大容量,后续不够可以扩容.

void InitST(ST* ps)
{
assert(ps);
ps->top = -1;//此时栈中无数据
ps->capacaity = 4;//设置初始最大容量
ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}
1
2
3
4
5
6
7
8

此处初始化后:

1.2 入栈(压栈,向"栈"中插入数据)

学到这里(顺序表和链表),对于"栈"的压栈操作很简单.

1. 由于是顺序表实现栈,所以在进行插入操作之前要先进行"判满"操作,如果栈满了,要进行扩容.
2. top是指向栈顶下标,需要将其往后移动一位,使其指向待插入位置.
3. 将新元素插入.此时刚好top为新的栈顶的下标.

图解:

代码:

void STPush(ST* ps, stacktype x)//压栈
{
assert(ps);
if (ps->top+1 == ps->capacaity)//检查"栈"满
{
ps->capacaity *= 2;//扩容
ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
if(tmp == NULL)
{
printf("增容失败\n");
}
ps->data = tmp;
}
//将"栈顶指针"指向待插入位置
ps->top++;
//将元素压栈
ps->data[ps->top] = x;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.3 “出栈”,删除"栈"中的数据

步骤:

1. 删除数据时,需要判断"栈"是否为空.
2. 将top向前(下)移动一位,即表示有效数据位减1.

代码:

void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
1
2
3
4
5
6

1.4 判空(判断"栈"是否为空)

当栈为空时,top为初始状态-1.

bool STEmpty(ST* ps)//判断是否为空栈,是空返回真
{
assert(ps);
if (ps->top == -1)
{
return true;
}
return false;
}
1
2
3
4
5
6
7
8
9

1.5 打印"栈顶"元素

void PrintSTTop(ST* ps)
{
assert(ps);
printf("%d", ps->data[ps->top]);
}
1
2
3
4
5

1.6 返回"栈顶"元素

stacktype STTop(ST* ps)//返回栈顶元素
{
assert(ps);
return ps->data[ps->top];
}
1
2
3
4
5

1.7 "栈"的销毁

栈的销毁操作,因为malloc开辟出来的是连续的空间,所以只需要释放一次即可.

void STDestory(ST* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->top = -1;
ps->capacaity = 0;
}
1
2
3
4
5
6
7
8

二、链栈

"链栈"的类型定义

typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
    stacktype data;
    struct SLStackNode* next;
}SLStackNode;
1
2
3
4
5
6
7

其实我们不难发现,"链栈"的类型与单链表很相似,通过对"栈"的基本知识了解,"栈"只在一端进行"插入"和"删除"操作,为了用单链表实现这一要求.

同时为了提高效率:

综上:我们利用不带头单链表的"头插(入栈)和头删(出栈)"来完成栈的各项基本操作.并且"栈"不需要进行随机访问其中的元素,只能从栈顶访问,链表是可以完成的.

2.1 初始化"链栈"

对于链表实现的栈,如果不带头结点:
我们不需要特意去写一个初始化函数.只需要创建一个栈顶指针,将其初始化指向NULL即可.(下面的代码是采用这种形式)

//创建一个栈顶指针,并完成初始化
SLStackNode* SLStack = NULL;
1
2

如果是带头结点的单链表:
我们可以定义一个初始化函数,申请一个头结点(头结点的数据域不存数据),将头结点返回.

//stack.c
SLStackNode* InitStack()
{
SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
if (newnode == NULL)
{
perror("newnode malloc fail");
}
return newnode;
}

//test.c
SLStackNode* SLStack = InitStack();

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2 入栈(压栈,向"栈"中插入数据)

步骤:(与单链表的头插类似)

1. 创建一个新节点.
2. 将新节点的next指针指向原"栈"的顶点
3. 更新栈顶指针(将栈顶指针指向新节点)

图解:

代码:

//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
assert(pps);
//获取新的结点
SLStackNode* newnode = BuyNode(x);
newnode->next = *pps;//将新节点的next指针指向原"栈"的顶点
*pps = newnode;//更新栈顶
}
1
2
3
4
5
6
7
8
9

2.3 “出栈”,删除"栈"中的数据

步骤:(与链表的头删操作类似)

1. 判空,防止空链栈的删除操作
2. 记录原栈顶元素的地址.
3. 更新栈顶.(将栈顶指针指向原栈顶的下一个结点↓).
4. 释放原栈顶空间

图解:

void STPop(SLStackNode** pps)//出栈
{
assert(pps);//二级指针不可能为空,如果为空就一定是传错了
assert(*pps);//防止空链栈的删除操作
SLStackNode* head = *pps;//记录栈顶元素的地址
*pps = (*pps)->next;//更新栈顶,即原来栈顶的下一个结点
free(head);//释放原栈顶空间
}
1
2
3
4
5
6
7
8

2.4 判空(判断"栈"是否为空)

链栈(不带头版本的)的初始状态是栈顶指针指向NULL.

bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
if (ps == NULL)
{
return true;
}
else
return false;
}
1
2
3
4
5
6
7
8
9

2.5 打印"栈顶"元素

栈顶元素即,栈顶指针指向的结点的数据域.

void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
assert(ps);
printf("%d ", ps->data);
}
1
2
3
4
5

2.6 返回"栈顶"元素

stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
assert(ps);
return ps->data;
}
1
2
3
4
5

2.7 返回"链栈"的长度(有效数据的个数)

遍历这个栈即可求出栈的长度.(但其实一般情况下,栈是不允许遍历的,栈顶元素不出去,我们原则上不能访问栈顶下面的元素).

代码:

int LengthStack(SLStackNode* ps)
{
int count = 0;
if (ps == NULL)//如果栈顶指针指向NULL,表示栈中没有元素
{
return 0;
}
SLStackNode* tail = ps;//代替头指针遍历
while (ps)
{
count++;//如果该结点不为空,则有效数据个数+1
ps = ps->next;
}
return count;//返回有效数据的个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.8 "链栈"的销毁

与"链表"销毁类似.

void STDestory(SLStackNode* ps)//栈的销毁
{
SLStackNode* del = ps;
SLStackNode* next = ps;//用于记录下一个结点
while (next)
{
next = next->next;
free(del);
del = next;

}
//保持习惯置空
next == NULL;
del = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结:

虽然链表和顺序表可以实现"栈",并且效率上,二者差距不大.

但是如果了解过寄存器的小伙伴,应该知道,如果数据在物理上是连续存储的,更加有利于数据的读取.

寄存器:

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。

因为cpu不是直接从硬盘读取数据的(嫌弃硬盘太慢了),而是通过寄存器(访问速度很快).

数据先被加载到缓存,此时如果数据在物理上是连续存储的,则在加载数据到缓存时,刚好将后面要读的数据也读走了,这样再读下一个数据时,就不需要再去硬盘读了.

🌰栗子:

综上,还是稍微建议使用顺序栈有一点点优势.

希望这篇文章对大家有帮助。欢迎小伙伴们私信提意见和提问哦！
最后，小伙伴们的点赞就是给牛牛最大的支持，能不能给牛牛来一个一键三连呢？谢谢支持。

总代码

"顺序栈"总代码

声明区(stack.h)

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef  int stacktype;
typedef struct stack
{
stacktype* data;
int top;
int capacaity;
}ST;
void InitST(ST* ps);
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
void PrintSTTop(ST* ps);//打印栈顶元素

bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

接口实现区( stack.c)

#include "stack.h"
//初始化栈
void InitST(ST* ps)
{
assert(ps);
ps->top = -1;
ps->capacaity = 4;
ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

//压栈
void STPush(ST* ps, stacktype x)
{
assert(ps);
if (ps->top+1 == ps->capacaity)
{
ps->capacaity *= 2;
ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
if(tmp == NULL)
{
printf("增容失败\n");
}
ps->data = tmp;
}
ps->top++;
ps->data[ps->top] = x;

}

//出栈
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}

//打印栈顶元素
void PrintSTTop(ST* ps)
{
assert(ps);
printf("%d", ps->data[ps->top]);
}

//判断是否为空栈,是空返回真
bool STEmpty(ST* ps)
{
assert(ps);
if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1;
{
return true;
}
return false;
}

//返回栈顶元素
stacktype STTop(ST* ps)
{
assert(ps);
return ps->data[ps->top];//反追栈顶元素
}

//栈的销毁
void STDestory(ST* ps)
{
assert(ps);
free(ps->data);//释放栈空间
ps->data = NULL;
ps->top = -1;
ps->capacaity = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

测试区(test.c)

#include "stack.h"
void test1()
{
ST st1;
InitST(&st1);
STPush(&st1, 1);//压栈
STPush(&st1, 2);//压栈
STPush(&st1, 3);//压栈
STPush(&st1, 4);//压栈
int a=STTop(&st1);
printf("栈顶元素为%d\n", a);
while (!STEmpty(&st1))
{
PrintSTTop(&st1);//打印栈顶元素
STPop(&st1);
}

STDestory(&st1);

}
int main()
{
test1();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

"链栈"总代码:

声明区(SLStack.h)

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
    stacktype data;
    struct SLStackNode* next;
}SLStackNode;


//SLStackNode* InitStack();

void STPush(SLStackNode** pps, stacktype x);//压栈
void STPop(SLStackNode** pps);//出栈
void PrintSTTop(SLStackNode* ps);//打印栈顶元素

bool STEmpty(SLStackNode* ps);//判断是否为空栈
stacktype STTop(SLStackNode* ps);//返回栈顶元素

int LengthStack(SLStackNode* ps);//返回栈的长度

void STDestory(SLStackNode* ps);//栈的销毁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

接口实现区(SLStack.c)

#include "SLStack.h"

//SLStackNode* InitStack()
//{
//SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
//if (newnode == NULL)
//{
//perror("newnode malloc fail");
//}
//return newnode;
//}

SLStackNode* BuyNode(stacktype x)//创建新结点
{
SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
assert(newnode);//防止申请结点失败
newnode->data = x;
newnode->next = NULL;
return newnode;
}


//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
assert(pps);
//获取新的结点
SLStackNode* newnode = BuyNode(x);
newnode->next = *pps;
*pps = newnode;
}

void STPop(SLStackNode** pps)//出栈
{
assert(pps);//二级指针不可能为空,如果为空就一定是传错了
assert(*pps);//防止空链栈的删除操作
SLStackNode* head = *pps;//记录栈顶元素的地址
*pps = (*pps)->next;//将栈顶向下移动一位
free(head);//释放栈顶空间
}

void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
assert(ps);
printf("%d ", ps->data);
}

bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
if (ps == NULL)
{
return true;
}
else
return false;
}

stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
assert(ps);
return ps->data;
}

int LengthStack(SLStackNode* ps)
{
int count = 0;
if (ps == NULL)
{
return 0;
}
SLStackNode* tail = ps;
while (ps)
{
count++;
ps = ps->next;
}
return count;
}

void STDestory(SLStackNode* ps)//栈的销毁
{
SLStackNode* del = ps;
SLStackNode* next = ps;//用于记录下一个结点
while (next)
{
next = next->next;
free(del);
del = next;

}
//保持习惯置空
next == NULL;
del = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

测试区(test.c)

#include "SLStack.h"

void test1()
{
SLStackNode* SLStack = NULL;
//SLStackNode* SLStack = InitStack();

STPush(&SLStack, 1);//压栈
STPush(&SLStack, 2);//压栈
STPush(&SLStack, 3);//压栈
STPush(&SLStack, 4);//压栈
STPush(&SLStack, 5);//压栈
STPush(&SLStack, -1);//压栈
STPush(&SLStack, -2);//压栈
int a = STTop(SLStack);
printf("栈顶元素为%d\n", a);

int length = LengthStack(SLStack);
printf("链表的长度为:%d\n", length);

while (!STEmpty(SLStack))
{
PrintSTTop(SLStack);//打印栈顶元素
STPop(&SLStack);
}

STDestory(SLStack);

}
int main()
{
test1();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34