《数据结构》（五）线性表之栈和队列的实现及万字详解

今天的重点是栈和队列，以及接口实现和详细解释。字数很多，很详细，大家收藏起来，慢慢回味😉😉😉

---

栈和队列的介绍

栈和队列是两种重要的线性结构， 从数据结构角度来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，这一篇我们将介绍栈和队列的定义，表示方法和实现。

---

栈

栈的定义

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 栈的插入操作被称为压栈/进栈/入栈，栈的删除操作被称为出栈。进行数据插入和删除操作的一端称为栈顶（top），另一端称为栈底。栈中元素按 a1，a2， …, an. 的次序进栈，出栈的第一个元素应为栈顶元素，也就是后进先出， 就像汉诺塔一样（两石柱）。 这里的top都是指向栈顶元素的下一位，一会大家就知道了。😝😝😝看图理解一下就上高速了。

---

栈的实现

栈的结构选择

🎤由之前的博客中介绍的有顺序表和链表，到底如何选择结构也是一个问题，我们理解栈的定义后讨论一下两种不同结构：
1.链表：双链表的话也是一个不错的选择，但是单链表的话尾插和尾删就是O(N)；
2.顺序表：由栈的定义可以清晰了解，栈只涉及尾插和尾删，用数组的话也是一个不错的选择。
综上所述：栈的实现，结构是多样的，各有千秋，喜欢那个就用那个吧，这篇我们就是用顺序表的形式（后面就会体会到数组的好处）。

---

栈的基本接口

🎤栈的基本操作除了在栈顶进行插人或删除外，还有栈的初始化、判空及取栈顶元素等

//栈需要的接口
// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps,STDataType x);
//出栈
void StackPop(ST* ps);
//取栈顶的数据
STDataType StackTop(ST* ps);
//栈的数据个数
int StackSize(ST* ps);
//检测栈是否为空
bool StackEmpty(ST* ps);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

栈结构（顺序结构）的定义

🎤一般来说结构定义的时候，设置空栈时不应该限定栈的最大容量，我们先为栈设置一个基础容量，在后面实际应用的时候，如果空间不够用，我们可以增容，这就是我们这里用到的支持动态增长的栈。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//是一个指针指向这个数组
	int top;//栈顶
	int capacity;//容量
}ST;
1
2
3
4
5
6
7

🎤这里的top指的是栈顶，capacity指的是数组当前可以使用的最大容量；这个a是一个结构体指针，指向的是数组。

---

栈的初始化

🎤初始化这里，也是很容易理解的，重点是这里的top，大家都知道数组中下标是从0开始的，top一般指在栈顶的下一位，如果top给0，指向的就是栈顶的下一位，如果给-1，那么指向的就是栈顶。

void StackInit(ST* ps)
{
	assert(ps);
	ps -> a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)//判空，如果我们malloc的空间是空的话，就直接报错
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;//是我们初始给数组的最大容量
	ps->top = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

栈的销毁

🎤我们用的是数组结构，直接free掉数组，然后让a指向空，在将top和capacity赋为0就ok了。

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
1
2
3
4
5
6
7

---

入栈

🎤入栈，就像是顺序表的尾插一样，首先判断数组是不是满了，如果满了我们就进行二倍的扩容，否则我们将待插入数据放到数组中top指向的位置，再让top++，让它指向待插入元素的下一位。

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//满了怎么办？---增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;//乘等2才会变成它的二倍
		}
	}
	
	ps->a[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

出栈

🎤 出栈时要注意是栈顶出，还要考虑栈中是否为空，如果为空，肯定不能出栈。 数据从栈顶出，让top前一位置为0肯定是不行的，我们让top–，直接覆盖即可。

void StackPop(ST* ps)
{
	assert(ps);
	//栈空了，调用pop，直接中止程序并报错
	assert(ps->top > 0);

	ps->top--;
}
1
2
3
4
5
6
7
8

---

取栈顶元素

🎤上面介绍过，我们top指向的是栈顶元素的下一位，取栈顶元素的时候，取它的前一位，就是栈顶元素。

STDataType StackTop(ST* ps)
{
	assert(ps);
	
	//栈空了，调用top，直接中止程序并报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
1
2
3
4
5
6
7
8
9

---

栈中数据的个数

🎤因为使用的是数组，而且还有top，我们肯定不会去遍历，top所在数组的下标就是栈的长度，我们直接return top即可。

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;//top所在数组的下标就是栈的长度
}
1
2
3
4
5
6

---

判空

🎤这个也简单，但是需要理解，如果为空返回非零结果，如果不为空返回0 。

bool StackEmpty(ST* ps)
{
	assert(ps);
	
	return ps->top == 0;//如果为空返回非零结果，如果不为空返回0
}
1
2
3
4
5
6

---

队列

队列的定义

和栈相反，队列是一种先进先出的线性表，它只允许在队的一端进行插入，在队的另一端进行删除。 这就像我们日常派对做核酸一样，最早排队的做的先出结果。在队列中允许插入的一端叫做队尾，允许删除的一端则称为队头。😲😲😲

---

队列的实现

队列结构的选择

🎤队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。 我们本篇就使用的是链表的结构。

---

队列的基本接口

🎤对于队列来说，能实现的接口几乎是和栈是一样的，但是需要注意的是入队是在队列后面入，出队是在队列头部出。

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队---队尾入
void QueuePush(Queue* pq, QDataType x);
//出队---队头出
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

队列结构（链式结构）的定义

🎤既然用的是单链表的结构，那么就要有一个数据域（data）和指针域（next）（指针域在以往博客，单链表中有详细说明）；而且还要有两个指针，一个指向队头（head），一个指向队尾（tail）。

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode* head;//队头
	QNode* tail;//队尾
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

队列的初始化

🎤先让头指针和尾指针都指向空。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
1
2
3
4
5

---

队列的销毁

🎤因为队列是单链表的形式，所以就只能用遍历释放的方式，用两个指针分别是cur和next，用cur来释放，让next来指向cur的下一个结点，然后将next赋给cur，当cur指向空的时候截止，最后将头指针和尾指针置空

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

入队（队尾入）

🎤入队，就像是单链表的尾插，有一个问题需要注意，要注意队列是否为空
1.申请新结点newnode，并判断是否malloc失败；
2.把新结点的数据域赋值为x，让其指针域指向NULL；
3.判断队列是否为空，如果为空，将头指针和尾指针指向newnode，否则让tail的next指向newnode，并让tail走到newnode上成为新的尾。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点的创建
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//先把新申请的结点的数据域和指针域赋值
	newnode->data = x;
	newnode->next = NULL;
	//如果队列中没有一个结点的时候
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//如果队列中有结点的时候
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;//链接之后让tail成为新的尾
	}
}
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

---

出队（队头出）

🎤==出队类似于单链表的头删，需要注意的是，队列的不能为空，需要判断链表只剩一个结点还是多个结点。==当队列只剩下一个结点时，要防止tail成为野指针，很简单，释放队列中第一个结点后，让head向后走一个，大家看一下就懂了。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//既然是出队列，那么就要判断队列是不为空的，空了还出个毛线

	if (pq->head->next == NULL)//当队列中只剩下一个结点的时候，防止tail成为野指针
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

取队头元素

🎤取元素就更简单了，返回头指针指向结点的数据域的值就行了。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//先判断一下队头数据是不是空，如果为空就不能调用

	return pq->head->data;//很简单，直接返回队头的数据即可
}
1
2
3
4
5
6
7

---

取队尾数据

🎤和取队头数据差不多

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//同上

	return pq->tail->data;//直接返回队尾的数据即可
}
1
2
3
4
5
6
7

---

队列中数据个数

🎤队列中数据个数，没有别的方法只能遍历链表了，定义一个指针cur用来从队列头走到空截止，每走一位，size++

int QueueSize(Queue* pq)
{
	//这次就需要用遍历链表，也是非常简单的
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

判空

🎤 如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//如果等于空就是真，不等于空就是假
}
1
2
3
4
5

---

代码参考

到这里，我相信大家对栈和队列已经拿捏了🎉🎉🎉，有错误大家可以指出哦，有疑问也可以问我，大家共同进步，后续会持续更新《数据结构》的相关内容，大家喜欢的话可以关注一下，😚😚😚
下面是项目代码，大家参考一下。

栈

Stack.c

#include"Stack.h"

void StackInit(ST* ps)
{
	assert(ps);
	ps -> a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//满了怎么办？---增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;//乘等2才会变成它的二倍
		}
	}
	
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	//栈空了，调用pop，直接中止程序并报错
	assert(ps->top > 0);

	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	//栈空了，调用top，直接中止程序并报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;//top所在数组的下标就是栈的长度
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	
	return ps->top == 0;//如果为空返回非零结果，如果不为空返回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
73
74
75
76
77
78

Stack.h

#include 
#include 
#include 
#include 
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//是一个指针指向这个数组
	int top;//栈顶
	int capacity;//容量
}ST;

//栈需要的接口
// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps,STDataType x);
//出栈
void StackPop(ST* ps);
//取栈顶的数据
STDataType StackTop(ST* ps);
//栈的数据个数
int StackSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果非空返回0 
bool StackEmpty(ST* 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

队列

Queue.h

#pragma once

#include
#include
#include
#include

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队---队尾入
void QueuePush(Queue* pq, QDataType x);
//出队---队头出
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
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

Queue.c

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//入队---队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点的创建
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//先把新申请的结点的数据域和指针域赋值
	newnode->data = x;
	newnode->next = NULL;
	//如果队列中没有一个结点的时候
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//如果队列中有结点的时候
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;//链接之后让tail成为新的尾
	}
}
//出队---队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//既然是出队列，那么就要判断队列是不为空的，空了还出个毛线

	if (pq->head->next == NULL)//当队列中只剩下一个结点的时候，防止tail成为野指针
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//先判断一下队头数据是不是空，如果为空就不能调用

	return pq->head->data;//很简单，直接返回队头的数据即可
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//同上

	return pq->tail->data;//直接返回队尾的数据即可
}
//数据个数
int QueueSize(Queue* pq)
{
	//这次就需要遍历链表，也是非常简单的
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == 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
95
96
97
98
99
100
101
102
103
104

Test.c

#include"Stack.h"
#include"Queue.h"
void TestStack()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	printf("\n");

	StackDestory(&st);
}

void TestQueue()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestory(&q);

}
int main()
{
	printf("栈：Last In First Out\n");
	TestStack();

	printf("队列：First In First Out\n");
	TestQueue();
	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
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