栈的链式存储C实现

基本概念

  首先看一下线性表定义:线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,其中n为表长,当n==0时线性表时一个空表。

栈(Stack)只允许在一端进行插入或删除操作的线性表。也就是说这种数据结构是一种有限制的线性表,其逻辑结构与普通的线性表相同,但只允许在表头或表尾进行插入删除操作。

示意图:

 栈顶、栈底、空栈、入栈、出栈

image-20210305231804132

 空栈:当这个栈里没有任何元素的时候为空栈。

 栈底:数据元素在栈的最底部不允许插入和删除的一端,比如图中a0元素就是在栈底的位置。

 栈顶:允许插入和删除的一端。

 入栈出栈:入栈和出栈只发生在同一端。

出入顺序

 后进后出(Last In First Out)LIFO

与顺序存储区别

 在栈的顺序存储结构中,由于在定义栈的时候,通过数组的方式开辟连续的存储空间,这样开辟的存储空间大小也就固定了,存储的数据最大数量也就确定了。

 而栈的链式存储结构中,其存储空间无需连续的存储空间,可以在可用内存中任意位置开辟空间,所以只要内存组后,其数据存储数量是不固定的。

栈的链式存储本质上和单链表误差表,只有在操作上有所限制,建议先浏览 《 C语言实现单链表 》 这篇文章。

定义结构体

 结构体的定义和单链表一样,知识名字有所变化而已。

1
2
3
4
5
typedef struct LinkNode
{
int data;
struct LinkNode* next;
}*LiStack;

栈的初始化

 上文说到,栈是一种有限制的单链表,是单链表就可以分为带头结点不带头节点。本片文章选择的是带头节点的单链表。所以在初始化的过程中需要创建一个头节点并把单链表指针指向头节点

1
2
3
4
5
6
7
8
9
10
// 初始化单链表(带头节点)
bool initLinkList(LiStack& L)
{
// 创建头节点
L = (LinkNode*)malloc(sizeof(LinkNode));
if (L == NULL)// 创建失败,内存不足
return false;
L->next = NULL;
return true;
}

入栈

 同单链表中在头节点后插入元素操作。因为这种数据结构就是在单链表上加以限制,只允许在一端进行操作。

1
2
3
4
5
6
7
8
9
10
11
// 进栈
bool push(LiStack& L, int e)
{
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
if (s == NULL)// 创建失败,内存不足
return false;
s->data = e;
s->next = L->next;
L->next = s;
return true;
}

出栈

 删除头节点后的第一个元素,等同于单链表的后删操作。

1
2
3
4
5
6
7
8
9
// 出栈
bool pop(LiStack& L, int &e)
{
LinkNode* p = L->next; // p以指向第一个结点
e = p->data;
L->next = p->next;
free(p);
return true;
}

获取栈顶元素

 获取第一个元素,也就是头节点指向的元素。

1
2
3
4
5
6
7
8
// 获取栈顶元素
bool getTop(LiStack L,int &e)
{
if (L->next == NULL)
return false;
e = L->next->data;
return true;
}

完整代码

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
#include<stdio.h>
#include<stdlib.h>


typedef struct LinkNode
{
int data;
struct LinkNode* next;
}*LiStack;



// 初始化单链表(带头节点)
bool initLinkList(LiStack& L)
{
// 创建头节点
L = (LinkNode*)malloc(sizeof(LinkNode));
if (L == NULL)// 创建失败,内存不足
return false;
L->next = NULL;
return true;
}

// 进栈
bool push(LiStack& L, int e)
{
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
if (s == NULL)// 创建失败,内存不足
return false;
s->data = e;
s->next = L->next;
L->next = s;
return true;
}

// 出栈
bool pop(LiStack& L, int &e)
{
LinkNode* p = L->next; // p以指向第一个结点
e = p->data;
L->next = p->next;
free(p);
return true;
}


// 打印栈(单链表)数据
void showLinkList(LiStack L)
{
LinkNode* p = L;
while (p->next != NULL)
{
printf("%d ", p->next->data);
p = p->next;
}
printf("\n");
}

// 获取栈顶元素
bool getTop(LiStack L,int &e)
{
if (L->next == NULL)
return false;
e = L->next->data;
return true;
}



void main()
{
LiStack L;
initLinkList(L);

push(L,10);
push(L, 20);
showLinkList(L);
int e;
pop(L, e);
showLinkList(L);
printf("%d\n", e);
getTop(L, e);
printf("%d", e);
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!