📒博客主页：要早起的杨同学的博客
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文所属专栏：【数据结构】
✉️坚持和努力从早起开始！
💬参考在线编程网站：🌐牛客网🌐力扣
🙏作者水平有限，如果发现错误，敬请指正！感谢感谢！

First. 栈

一. 栈的概念

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

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

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

二. 进栈出栈的形式

栈对线性表的插入和删除的位置做了限制，并没有对元素进出的时间进行限制，所以，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

所以栈是：一种入栈顺序，多种出栈顺序。

比如：现在有元素1、2、3依次进栈，出栈顺序有哪些？

• 第一种：1、2、3（1进、1出、2进、2出、3进、3出）
• 第二种：3、2、1（1、2、3进，3、2、1出）
• 第三种：2、1、3（1、2进，2、1出，3进、3出）
• 第四种：1、3、2（1进、1出，2、3进，3、2出）
• 第五种：2、3、1（1、2进，2出，3进，3出，1出）

三. 栈的存储结构

• 栈的顺序存储结构

数组的首元素作为栈底，另外一端作为栈顶，同时定义一个变量 top 来记录栈顶元素在数组中的位置。

• 栈的链式存储结构

单链表的尾部作为栈底，头部作为栈顶，方便插入和删除（进栈头插，出栈头删），头指针和栈顶指针 top 合二为一。

---

四. 栈的实现（顺序栈）

• 顺序表的结构相比链表简单，不影响效率的情况下会优先使用顺序表。
• 这次我们用的可动态增长的数组来实现的，因为栈只会在一端进行插入和删除操作，用数组效率还是比较高，当然，也会存在一些问题，就是每次空间不够，要重新开辟空间，可能会造成一些内存浪费。

首先新建一个工程（ 博主使用的是 VS2022 ）

• Stack.h（栈的类型定义、接口函数声明、引用的头文件）
• Stack.c（栈接口函数的实现）
• Test.c（主函数、测试栈各个接口功能）

Stack.h 头文件代码如下：

#pragma once

#include   /*printf, perror*/
#include  /*assert*/
#include  /*realloc*/
#include /*bool*/

typedef int STDataType;  //类型重命名，栈中元素类型先假设为int

typedef struct Stack
{
	STDataType* a;  //指向动态开辟的数组
	int top;        //记录栈顶位置
	int capacity;   //栈的容量大小
}Stack;

//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//检测栈是否为空，如果为空返回true，否则返回NULL
bool StackEmpty(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* 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
29
30

---

这里重点讲解 Stack.c 中各个接口函数的实现。

4.1 栈的定义

• 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈

typedef int STDataType;  //类型重命名，栈中元素类型先假设为int
#define N 20

struct Stack
{
	STDataType a[N];  //定长数组
	int top;          //记录栈顶位置
}SqStack;
1
2
3
4
5
6
7
8

• 支持动态增长的栈

假设栈的容量 capacity 为 5，定义空栈时 top = -1，当栈存在一个元素时 top = 0

typedef int STDataType;  //类型重命名，栈中元素类型先假设为int

typedef struct Stack
{
	STDataType* a;  //指向动态开辟的数组
	int top;        //记录栈顶位置
	int capacity;   //栈的容量大小
}Stack;
1
2
3
4
5
6
7
8

---

4.2 栈的初始化

//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = -1;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8
9

---

4.3 栈的销毁

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

	if (ps->a)
	{
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = -1;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

4.4 入栈

//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity - 1)  //检查栈空间是否满了
	{
		//如果栈原始容量为0，新容量设为4，否则设为原始容量的2倍
		int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2;
		//扩容至新容量
		STDataType* newS = realloc(ps->a, newcapacity * sizeof(STDataType));
		if (newS == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = newS;
		//更新容量
		ps->capacity = newcapacity;
	}
	ps->top++;           //栈顶指针加一
	ps->a[ps->top] = x;  //将新增元素放入栈顶空间
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

4.5 出栈

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top != -1);  //栈不能为空

	ps->top--;  //栈顶指针减一
}
1
2
3
4
5
6
7
8

---

4.6 检测栈是否为空

//检测栈是否为空，如果为空返回true，否则返回NULL
bool StackEmpty(Stack* ps)
{
	assert(ps);
	
	return ps->top == -1;
}
1
2
3
4
5
6
7

---

4.7 获取栈中有效元素个数

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);

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

---

4.8 获取栈顶元素

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
    assert(!StackEmpty(ps));  //栈不能为空

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

---

五. 测试栈的功能

• 栈的实现，不能像顺序表一样，去实现一个打印函数来遍历栈并输出，这样就不符合栈的特点了（只能在栈顶插入删除，后进先出），所以我们这样来实现出栈：获取并打印栈顶元素，再删除栈顶元素，继续获取新的栈顶元素。

void TestStack()  //测试函数
{
	Stack s;
    //初始化栈
	StackInit(&s);
	//入栈
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	//出栈
	while (!StackEmpty(&s))
	{
		printf("%d ", StackTop(&s));  //获取栈顶元素
		StackPop(&s);
	}
	printf("\n");
	//销毁栈
	StackDestroy(&s);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 运行结果

Second. 队列

一. 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 的特点。

入队列：进行插入操作的一端称为队尾 。

出队列：进行删除操作的一端称为队头。

入队出队形式：一种入队顺序，只有一种出队顺序。

队列的应用：比如生活中排队买东西，先排队的先购买，平时我们用微信聊天，用键盘进行各种数字的输入，到聊天框中输出，也是队列的应用。

二. 队列的结构

• 队列的顺序结构

入队，不需要移动任何元素，时间复杂度为O(1)

出队，所有元素需要往前移动，时间复杂度为O(N)

• 队列的链式结构

首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点

入队（尾插），时间复杂度为O(1)

出队（头删），时间复杂度为O(1)

---

三. 队列的实现（链式结构）

首先新建一个工程（ 博主使用的是 VS2022）

• Queue.h（队列的类型定义、接口函数声明、引用的头文件）
• Queue.c（队列接口函数的实现）
• Test.c（主函数、测试队列各个接口功能）

Queue.h 头文件代码如下：

#pragma once
#include
#include
#include
typedef int bool;
#define false 0
#define true 1

typedef int QDatatype;

typedef struct QNode
{
	struct QNode* next;
	QDatatype val;
}QNode;


/*
我们实现无头链表的头插头删接口时，因为需要改变头指针的指向
有以下这样方法：
1、传二级指针
2、改变返回值，返回新的头
3、给链表增加一个哨兵位的头节点
4、结构体包起来
*/

typedef struct Queue//队列的链式结构
{
	QNode* front;//队头指针
	QNode* tail;//队尾指针
}Queue;

//初始化
void queue_init(Queue* qst);
//销毁
void queue_destory(Queue* qst);
//入列
void queue_push(Queue* qst,QDatatype x);
//出列
void queue_pop(Queue* qst);
//队头数据
QDatatype queue_front(Queue* qst);
//队尾数据
QDatatype queue_back(Queue* qst);
//判空
bool queue_empty(Queue* qst);
//大小
int queue_size(Queue* qst);
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

---

这里重点讲解 Queue.c 中各个接口函数的实现。

3.1 队列的定义

typedef int QDatatype;

typedef struct QNode//队列节点结构
{
	struct QNode* next;//节点指针
	QDatatype val;//节点数据
}QNode;

typedef struct Queue//队列的链式结构
{
	QNode* front;//队头指针
	QNode* tail;//队尾指针
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13

---

3.2 队列的初始化

//初始化
void queue_init(Queue* qst)
{
	assert(qst);
	qst->front = qst->tail = NULL;
}
1
2
3
4
5
6

---

3.3 队列的销毁

//销毁
void queue_destory(Queue* qst)
{
	assert(qst);
	QNode* cur = qst->front;
	while (cur)
	{
		QNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	qst->front = qst->tail = NULL;

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

---

3.4 入队（尾插）

要分为两种情况讨论，队列为空和队列不为空

//入列
void queue_push(Queue* qst, QDatatype x)
{
	assert(qst);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->next = NULL;
	newNode->val = x;
    
	if (queue_empty(qst))
	{
		qst->front = qst->tail = newNode;
	}
	else
	{
		qst->tail->next = newNode;
		qst->tail = newNode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

3.5 出队（头删）

队列不能为空哦，记得在最开头检查一下

//出队
void queue_pop(Queue* qst)
{
	assert(qst);
	assert(!queue_empty(qst));
    //如果只剩下一个节点，要注意给tail置空
    //防止出现野指针
	if (qst->front->next == NULL)
	{
		free(qst->front);
		qst->front = qst->tail = NULL;
	}
	else
	{
		QNode* del = qst->front;
		qst->front = qst->front->next;

		free(del);
		del = NULL;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

3.6 获取队列元素个数

//获取队列元素个数
//如果会频繁调用这个接口函数，可以在QueuePtr中加一个size记录数据个数
int queue_size(Queue* qst)
{
	assert(qst);
	QNode* cur = qst->front;
	int count = 0;
	while (cur)
	{
		cur = cur->next;
		++count;
	}
	return count;
}

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

---

3.7 获取队头元素

队列为空是获取不了元素的哦，记得检查一下

//获取队头元素
QDatatype queue_front(Queue* qst)
{
	assert(qst);
	assert(!queue_empty(qst));
	return qst->front->val;
}
1
2
3
4
5
6
7

---

3.8 获取队尾元素

队列为空是获取不了元素的哦，记得检查一下

//获取队尾元素
QDatatype queue_back(Queue* qst)
{
	assert(qst);
	assert(!queue_empty(qst));
	return qst->tail->val;
}
1
2
3
4
5
6
7

---

3.9 检查队列是否为空

//检查队列是否为空，若为空返回true，否则返回false
bool queue_empty(Queue* qst)
{
	assert(qst);
	return qst->front == NULL && qst->tail == NULL;
}
1
2
3
4
5
6

---

四. 测试队列的功能

void Test(Queue* qst)
{
	queue_init(qst);
	queue_push(qst, 1);
	queue_push(qst, 2);
	queue_push(qst, 3);
	queue_push(qst, 4);
	queue_push(qst, 6);

	printf("%d\n", queue_front(qst));
	printf("%d\n", queue_back(qst));
	printf("%d\n", queue_size(qst));

	while (!queue_empty(qst))
	{
		printf("%d ", queue_front(qst));
		queue_pop(qst);
	}

	queue_destory(qst);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 运行结果

---

大家快去动手实现一下吧！