• 【C语言】数据结构——栈和队列实例探究

    💗个人主页💗
    ⭐个人专栏——数据结构学习⭐
    💫点击关注🤩一起学习C语言💯💫

    目录

    导读：

    我们在前面学习了单链表和顺序表，今天我们来学习栈和队列。
    栈和队列相对于单链表和顺序表来说是较为简单的，之后我们再深入学习双链表。关注博主或是订阅专栏，掌握第一消息。

    一、 栈

    1. 栈的概念及结构

    栈(Stack)是一种只能在一端进行插入和删除操作的线性数据结构，该端被称为栈顶(Top)，另一端被称为栈底(Bottom)。
    栈的特点是后进先出(Last In First Out, LIFO)，即最后放入栈中的元素最先被弹出。栈中的元素可以是任意类型，但栈顶永远只能是一个元素。

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

    在这里插入图片描述
    在这里插入图片描述

    2. 栈的实现

    栈可以用数组或链表来实现，常见应用场景包括函数调用、表达式求值、括号匹配、逆序输出等。

    相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
    在这里插入图片描述

    其基本操作包括：

    push(x): 将元素x压入栈顶。
    pop(): 弹出栈顶元素并返回其值。
    top(): 返回栈顶元素的值，但不弹出。
    empty():判断栈是否为空。

    3. 实现代码

    我们需要创建两个 C文件: study.c 和 Stack.c，以及一个 头文件： Stack.h。

    头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

    3.1 定义结构体

    typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

    若struct Stack {}这样来定义结构体的话。在申请Stack 的变量时，需要这样写，struct Stack n;
    若用typedef，可以这样写，typedef struct Stack{}ST; 。在申请变量时就可以这样写，ST n;
    区别就在于使用时，是否可以省去struct这个关键字。

    Stack.h

    typedef struct Stack
{
	STDataType* a;
	int top;		//标识栈顶的位置
	int capacity;
}ST;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.2 初始化栈

    Stack.h 声明函数

    // 初始化栈 
void STInit(ST* pst);

    • 1
    • 2

    Stack.c 定义函数

    void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.3 销毁栈

    动态内存空间开辟，使用完之后需要进行销毁。
    Stack.h 声明函数

    // 销毁
void STDestroy(ST* pst);

    • 1
    • 2

    Stack.c 定义函数

    void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.4 入栈

    我们在顺序表和单向链表里，都另定义一个函数来进行空间的开辟，这样我们在其它的函数中有开辟空间的需要只用调用即可，而无需再去写一次开辟空间的代码。但是在栈中我们只有在入栈的函数中需要进行空间的开辟，所有不用再单独写一个函数。
    Stack.h 声明函数

    // 入栈 
void STPush(ST* pst, STDataType x);

    • 1
    • 2

    Stack.c 定义函数

    
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	// 检查空间，如果满了，进行增容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//如果开辟成功则重新赋给原来的数组指针
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//栈顶从0开始，可以作为数组的下标来进行插入数据
	pst->a[pst->top] = x;
	pst->top++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    3.5 出栈

    后进先出原则，最后进来的数据先出。
    Stack.h 声明函数

    // 出栈 
void STPop(ST* pst);

    • 1
    • 2

    Stack.c 定义函数

    // 出栈 
void STPop(ST* pst)
{
	assert(pst);
	//top大于0，栈里面有数据才能删除数据
	assert(pst->top > 0);
	//直接让top--，不让访问即可
	pst->top--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述

    3.6 获取栈顶元素

    栈并不能像打印数组那样把数据全部打印出来，只能获取到栈顶的元素，想要获取其它数据就只能先把其它的数据给删除，也就是出栈。
    Stack.h 声明函数

    // 获取栈顶元素 
STDataType STTop(ST* pst);

    • 1
    • 2

    Stack.c 定义函数

    // 获取栈顶元素 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	//top-1即是栈顶元素
	return pst->a[pst->top - 1];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3.7 检测栈是否为空

    Stack.h 声明函数

    // 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst);

    • 1
    • 2

    Stack.c 定义函数

    // 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst)
{
	assert(pst);
	//如果表达式成立则为真
	return pst->top == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    3.8 获取栈中有效元素个数

    Stack.h 声明函数

    // 获取栈中有效元素个数 
int STSize(ST* pst);

    • 1
    • 2

    Stack.c 定义函数

    //获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    4. 代码整理

    4.1 Stack.h

    #pragma once
#include 
#include 
#include 
#include 
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;		//标识栈顶的位置
	int capacity;
}ST;

// 初始化栈 
void STInit(ST* pst);

// 销毁
void STDestroy(ST* pst);

// 入栈 
void STPush(ST* pst, STDataType x);

// 出栈 
void STPop(ST* pst);

// 获取栈顶元素 
STDataType STTop(ST* pst);

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst);

// 获取栈中有效元素个数 
int STSize(ST* pst);

    • 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

    4.2 Stack.c

    #include "Stack.h"

//初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

// 销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
}

// 入栈 
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	// 检查空间，如果满了，进行增容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//如果开辟成功则重新赋给原来的数组指针
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//栈顶从0开始，可以作为数组的下标来进行插入数据
	pst->a[pst->top] = x;
	pst->top++;
}

// 出栈 
void STPop(ST* pst)
{
	assert(pst);
	//top大于0，栈里面有数据才能删除数据
	assert(pst->top > 0);
	//直接让top--，有效数据减一即可
	pst->top--;
}

// 获取栈顶元素 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	//top-1即是栈顶元素
	return pst->a[pst->top - 1];
}

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst)
{
	assert(pst);
	//如果表达式成立则为真
	return pst->top == 0;
}

//获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

    • 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

    4.3 study.c

    #include "Stack.h"

void TestST1()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	printf("%d\n", STTop(&s));

	//一     对   多
	//入栈顺序 -- 出栈顺序
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
	STDestroy(&s);
}
int main()
{
	TestST1();
	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

    二、队列

    1. 队列的概念及结构

    队列是一种线性的数据结构，它可以存储一系列数据，其中第一个添加的数据会被第一个删除，也就是先进先出（FIFO）的原则。

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

    2. 队列的实现

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

    队列通常有两个指针，一个是front指针，指向队列的第一个元素，另一个是rear指针，指向队列的最后一个元素。当一个新元素进入队列时，它被插入到rear指针所指向的位置，当一个元素从队列中删除时，它会从front指针所指向的位置被删除。

    在这里插入图片描述

    3. 实现代码

    我们需要创建两个 C文件: study.c 和 Queue.c，以及一个 头文件： Queue.h。

    头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

    3.1 定义结构体

    定义了一个链式队列的数据结构。
    包含了两个结构体：

    1. QNode结构体表示队列中的一个节点，包含一个整数数据成员val和指向下一个节点的指针next。

    2. Queue结构体表示一个队列，包含指向队头和队尾节点的指针phead和ptail，以及队列的大小size。

    这个队列是通过链式结构实现的，即每个节点都包含一个指向下一个节点的指针。队列的头指针phead指向队列的第一个节点，而队列的尾指针ptail指向队列的最后一个节点。
    链式队列的优点是可以动态地增加和减少队列的大小，而不需要像顺序队列那样预留一定的空间。缺点是每个节点都需要额外的指针空间来指向下一个节点，因此相对于顺序队列会占用更多的存储空间。

    Queue.h

    // 链式结构：表示队列 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

    3.2 初始化队列

    Queue.h

    // 初始化队列 
void QueueInit(Queue* pq);

    • 1
    • 2

    Queue.c

    void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.3 销毁队列

    Queue.h

    // 销毁队列 
void QueueDestroy(Queue* pq);

    • 1
    • 2

    Queue.c

    void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead->next;
	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	cur = NULL;
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

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

    3.4 队尾入队列

    Queue.h

    // 队尾入队列 
void QueuePush(Queue* pq, QDataType x);

    • 1
    • 2

    Queue.c

    void QueuePush(Queue* pq, QDataType x)
{
	//开辟新空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    3.5 队头出队列

    Queue.h

    // 队头出队列
void QueuePop(Queue* pq);

    • 1
    • 2

    Queue.c

    void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* tmp = pq->phead;
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

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

    3. 6 获取队列头部元素

    Queue.h

    // 获取队列头部元素 
QDataType QueueFront(Queue* pq);

    • 1
    • 2

    Queue.c

    QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.7 获取队列队尾元素

    Queue.h

    // 获取队列队尾元素
QDataType QueueBack(Queue* pq);

    • 1
    • 2

    Queue.c

    QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.8 检测队列是否为空

    Queue.h

    // 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq);

    • 1
    • 2

    Queue.c

    bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.9 获取队列中有效元素个数

    Queue.h

    // 获取队列中有效元素个数 
int QueueSize(Queue* pq);

    • 1
    • 2

    Queue.c

    int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    4. 代码整理

    4.1 Queue.h

    #pragma once
#include 
#include 
#include 
#include 

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* pq);

// 销毁队列 
void QueueDestroy(Queue* pq);

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x);

// 队头出队列
void QueuePop(Queue* pq);

// 获取队列头部元素 
QDataType QueueFront(Queue* pq);

// 获取队列队尾元素
QDataType QueueBack(Queue* pq);

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq);

// 获取队列中有效元素个数 
int QueueSize(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

    4.2 Queue.c

    #include "Queue.h"

// 初始化队列 
void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead->next;
	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	cur = NULL;
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

// 队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* tmp = pq->phead;
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

    • 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

    4.3 study.c

    #include "Queue.h"

void TestQ1()
{
	Queue s;
	QueueInit(&s);
	QueuePush(&s, 1);
	QueuePush(&s, 2);
	QueuePush(&s, 3);
	QueuePush(&s, 4);
	QueuePush(&s, 5);
	printf("%d ", QueueFront(&s));
	printf("%d ", QueueBack(&s));
	printf("%d\n", QueueSize(&s));
	QueuePop(&s);
	QueuePop(&s);
	printf("%d ", QueueFront(&s));
	printf("%d\n", QueueSize(&s));
	if (!QueueEmpty(&s))
	{
		QueuePop(&s);
		printf("%d ", QueueFront(&s));
		printf("%d\n", QueueSize(&s));
	}
	QueueDestroy(&s);
	printf("%d\n", QueueSize(&s));

}
int main()
{
	TestQ1();
	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
  • 相关阅读:
    在Springboot HandlerInterceptor中获取GET和POST请求参数
    实现IP地址归属地显示功能、号码归属地查询
    Dockerfile文件详细教程
    PHP没死，依然有78%的网站在使用
    大模型 舆情分析 数据构造 prompt提示词 经验分享 数据准备
    调用第三方系统的签名设计与校验实例讲解与实践
    day007
    metasploitable2靶场漏洞总结（部分）
    exception错误处理库学习
    vue-cli创建项目的步骤
  • 原文地址：https://blog.csdn.net/qq_64818885/article/details/134481692