数据结构之线性表中的栈和队列【详解】_线性表 图解

引言：

北京时间2022/11/29 凌晨1点06分，今天我们来讲一下什么是栈和队列，写完这个博客，明天复习自我实现一下栈和队列，我们看一下能不能找到有关二叉树的教学视屏，假如找到了，我们就朝二叉树进发，找不到，我们就进行链表这部分的题目练习

栈和队列的讲解

（一、）什么是栈

1.栈的概念、结构和图解：

首先在这边我们学习什么是栈和队列的前提之下，我们先把双循环链表给收尾一下

（1.）顺序表和链表的对比（严格来说这两个结构是相辅相成的）

(1.1)首先是顺序表的优点：1.支持随机访问，需要随机访问结构的算法可以很好的适用 2.CPU告诉缓存的命中率更高
(1.2.)顺序表的缺点： 1.头部中部插入删除时间效率低 时间复杂度O（N） 2.连续的物理空间，空间不够了以后需要增容（增容有一定的消耗）3.按倍数增容，用不完就有一定的空间的浪费
(1.3.)（双向带头循环链表）链表的优点：1.任意位置插入删除效率高 时间复杂度 O（1） 2.按需申请释放空间
(1.4.)链表的缺点：1.不支持随机访问（用下标访问），意为着：一些排序在这种结构上不适用 2.链表存储一个值，同时也要储存链接指针，也有一点的消耗 3.CPU告诉缓存的命中率更低

（2.）栈的概念和结构

（2.1）.栈的概念和结构：
栈：一种特殊的线性表，其只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除的操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出（就像是电梯）的原则
压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据也在栈顶（因为要遵守原则：先进后出，后进先出）
这边讲完了我么就来讲一下为什么要用数组来实现我的栈

（2.2）我们可以通过数组的形式来把栈给实现（也可以使用链表，但是链表没有数组好，所以我们就用数组实现就行）

（2.3）使用链表实现栈的方式：
如果用尾做栈顶，尾插尾删，要设计双向链表，否则删除数据效率低
如果用头做栈顶，头插头删，就可以设计成单链表
所以这些都有一些的不好，所以我们使用数组来实现我的栈就是最好的

（3.）栈的图解

2.使用数组的形式实现栈：

（4.1）具体的功能如下：（包括与栈相关的结构体形式的创建）

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
![在这里插入图片描述](https://img-blog.csdnimg.cn/8b77a23d14294724b263f8b3d5865b26.png#pic_center)

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的意思（位置）
	int capacity;

}ST;

void StackInist(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps,STDataType x);//此时的插入是在栈顶位置（栈的特点：先出后进，先进后出一定要理解透彻了）
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//这个就是表明此时我要取我的栈顶的数据，在top位置（栈顶位置）获取我的数据
int StackSize(ST* ps);//这个是意思就是表示我的栈中有几个数据
bool StackEmpty(ST* ps);//此时这个函数的作用就是判断我的栈是否为空（bool这个返回值的意思就是返回真和假的意思，用int也是一样）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（4.2）具体各种接口函数的实现

（4.2.1）初始化

（4.2.2）销毁

（4.2.3）放数据

（4.2.4）删除

（4.2.5）找top位置

（4.2.6）计算栈的大小

（4.2.7）判断栈是否为空

（4.2.8）遍历栈

（4.3）以上就是栈的数组实现

（二、）什么是队列

1.队列的概念、结构和图解：

（1.）队列的概念和结构

（1.1）.队列的概念及其结构：
队列:只允许在一端进行插入数据的操作，在另一端进行删除数据的操作，队列具有先进先出的原则
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
就是区别于栈就对了（一个是同一端进同一端出，一个是一端进，另一端出）
此时可以明显的看出用数组和单链表都不适合实现我们的队列，所以这边最好就是使用双向循环链表是最合适的
（1.2）假如使用链表的结构：
在进行出数据（在链表的头上进行）的时候就是把一个数据出完之后（然后把它删除掉，然后把phead头指针指向下一个，然后再出另一个数据）
在入数据（在链表的尾部进行）的时候就是找尾，然后一直更新这个尾

（2.）队列的图解

2.使用链表的形式实现队列

（3.1）具体功能如下：

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

//定义各种结构（不管是顺序表还是链表都是在模仿老师的定义结构的方法），以后在定义结构的时候一定要学会自己去定义结构

//此时这个结构体的定义就很像是单量表实现的定义
typedef int QDataType;
typedef struct QueueNode //这个就是队列中的单链表的结构的定义（用单链表实现队列就一定要有单链表结构的定义）
{
	struct QueueNode* next;
	QDataType data;

}QueueNode;

typedef struct Queue //此时的这个结构体应该才是我（队列）的主结构体，上面那个结构体应该只是一个单量表的结构体（因为此时我是想要用单链表来实现我的队列），上面那个结构体也就是我的单链表中的一个一个的结点而已（就是用上面的这个结构体来设计我的队列中的每一个结点而已，这样就有点像是我的单链表）
{
	QueueNode* head;
	QueueNode* tail;//虽然这个结构体是队列的关键，但是这个结构体中的成员，还是要根据我的需求来定义的
}Queue;

//typedef struct Queue //此时的这个结构体应该才是我（队列）的主结构体，上面那个结构体应该只是一个单量表的结构体（因为此时我是想要用单链表来实现我的队列），上面那个结构体也就是我的单链表中的一个一个的结点而已（就是用上面的这个结构体来设计我的队列中的每一个结点而已，这样就有点像是我的单链表）
//{
//	QueueNode* head;
//	QueueNode* tail;//虽然这个结构体是队列的关键，但是这个结构体中的成员，还是要根据我的需求来定义的
//}Queue;


//并且此时的这个双指针可以不使用结构体定义（但是如果不使用结构体的话，此时的传参就要进行一定的改变了）
//例如：void QueueInit(Queue* pq); 不使用结构体此时就要写成 void QueueInit(QueueNode** pphead,QueueNode** pptail);
//void QueueInit(QueueNode** pphead, QueueNode** pptail);不仅要传二级指针（因为我会改变函数外部的值），而且要进行两个指针参数的传递，可谓是非常的复杂


//此时以上的这些代码的意思（就是创建了两个结构体（也就是两种类型），有了这两种类型，我就可以实现我的队列了），所以这个也就是我的队列的基本的结构体定义

//为什么一定是以下的接口：这个就是性质决定的
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); //这个就是表示取队尾数据的意思
size_t 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
40
41
42
43
44
45

（3.2）具体函数接口的是实现

#include"Stack.h"

//初始化
void QueueInit(Queue* pq)
{
	//此时为什么传参接收参数的时候不需要二级指针呢？
	//原因就是：我使用了两个结构体类型
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;

}

//销毁(此时销毁的就是一个一个动态内存开辟出来的结点，这个结点就是从另一个结构体的定义之中来的)
void QueueDestory(Queue* pq)
{
	assert(pq);

	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;//保存下一个（因为我是一个链表）
		free(cur);
		cur = next;

	}
    
	pq->head = pq->tail = NULL;
}
//插入
void QueuePush(Queue* pq, QDataType x)
{
	//因为此时已经把结构体的地址传过来了，所以此时就可以对结构体进行改变了
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;//这个就是结点是初始化
	//此时先进行队列有无数据的判断
	if (pq->head == NULL)//这个表示无
	{
		//这个就是此时的把我的结构体进行改变，但是要注意进行结构体的改变一定要进行结构体地址的传递，然后要用一级指针接收
		pq->head = pq->tail = newnode;//这个就是表示此时的这个队列一个值都还没有，所以此时就可以把这个newnode给我的head和tail
	}
	else//这个就是有（然后有数据，此时因为是一个队列，所以此时我们就需要在这个队列的后面插入一个新的结点，因为队列的特点（一头进一头出）），然后此时就需要在tail这个表示尾的指针后面进行一个尾插，这样就可以完成队列的插入功能
	{
		pq->tail->next = newnode;
		pq->tail = newnode;//上面那个是主要的完成插入的步骤，下面这个没什么主要的功能（其实就只是想让我的tail继续保持在最后一个结点的位置而已）


	}

}
//删除
void QueuePop(Queue* pq)
{
	//因为队列的特性（队尾入，队头出）
	//所以删除数据是已经规定死了的，只能在队头删
	assert(pq);
	//还是那两种写法：1.温柔的写法  2.暴力的写法
	//if (pq->head == NULL)
	//{
	//	return;
	//}
	//assert(pq->head != NULL);
	//并且下面这个函数 QueueEmpty(pq) 为真就是表示此时的pq->head为空，为假就表示此时的pq->head不为空
	assert(!QueueEmpty(pq));//这个在报错（就是说明此时的这个QueueEmpty(pq)函数为真，然后(!QueueEmpty(pq))加了一个感叹号就表示此时整个为假），所以此时这个断言的意思就是判断这个pq->head不为空，为空就报错

	Queue* next = pq->head->next;
	free(pq->head);
	pq->head = NULL;
	pq->head = next;//完成这些基本的操作，我们一定还要注意几个注意点
	//因为此时可能会把整个队列都给删空，所以此时当删到只有一个数据的时候，此时就要进行tail的置空，不然就有野指针问题
	if (pq->head == NULL)//此时这个为空，就是表示已经删完了（但是此时只是把head给处理完了，这边还剩了一个tail指针（此时如果把最后一个数据也删掉，那么此时的tail就会变成一个野指针），所以我们在删除最后一个数据的时候，一定要注意tail的置空，不然就是野指针）
	{
		pq->tail = NULL;
	}

}

//取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//此时就是表示我的头已经为空了，所以我已经不能再去取头数据了

	return pq->head->data;//这个就是表示队列头的数据

}
//取队尾的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列不为空

	return pq->tail->data;//此时为了寻找我队列的尾（也就是入口），并且此时的tail就是指向我队列的尾数据，所以想要找尾中的数据，只需要把tail->data给返回去就行了
    
}

//计算队列中的数据个数
size_t QueueSize(Queue* pq)
{
	assert(pq);

	int n = 0;
	QueueNode* cur = pq->head;
	while (cur != NULL)//想要计算数据个数，自然要遍历我的队列
	{
		n++;
		cur = cur->next;//有了这步上面那步就不需要写成cur->next != NULL;了
	}

	return n;
}

//判断队列是否为空（在删除的时候会用到，因为删除的时候队列是不可以为空的，所以要进行一定的判断）
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

（3.3）以上就是队列的链表基本实现

（三、）总结：

                            就是要多写，多练，多画图，睡觉啦！
1