【数据结构】开卷数据结构~栈和队列详解

用户9645905

发布于 2022-11-30 11:46:21

2230

发布于 2022-11-30 11:46:21

文章被收录于专栏：Linux学习~

前言

本章主要讲解：

数据结构中的栈和队列的知识以及如何实现

栈

概念及结构

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

数据处理方式：

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

图示：

栈的实现

栈的实现一般可以使用 数组或者链表实现 相对而言数组的结构实现更优一些（数组在尾上插入数据的代价比较小）

图示：数组栈

接口展示

注：定长的静态栈实际中不实用，所以我们主要实现支持动态增长的数组栈

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
 STDataType* _a;
 int _top; // 栈顶
 int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps); 
// 入栈
void StackPush(Stack* ps, STDataType data); 
// 出栈
void StackPop(Stack* ps); 
// 获取栈顶元素
STDataType StackTop(Stack* ps); 
// 获取栈中有效元素个数
int StackSize(Stack* ps); 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps); 
// 销毁栈
void StackDestroy(Stack* ps);

栈结构创建

动态数组栈具有三个元素：数组指针（指向开辟的空间），栈顶位置，栈的长度

参考代码：

//栈类型结构
typedef struct Stack
{
	//数组栈（指向数组的指针）
	STDataType* a;
	//栈顶位置
	int top;
	//栈容量（数组长度）
	int capacity;
}ST;

栈的初始化

注意：

栈顶的表示的位置需要考虑好

参考代码：

//栈初始化
void StackInit(ST* ps)
{
	//避免传入空指针
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//定义top为栈最后数据的后一个位置
	//也可以选择让top为当前最后数据的位置 则初始化top=-1;
	ps->capacity = 0;
	return;
}

栈的销毁

注：动态开辟的空间结束时也需要进行销毁（避免内存泄漏）

参考代码：

//栈销毁
void StackDestroy(ST* ps)
{
	//避免传入空指针
	assert(ps);
	free(ps->a);//释放开辟的数组栈空间
	ps->a = NULL;//置空，避免造成野指针
}

入栈

注意：

入栈考虑是否栈满，栈满则进行扩展栈长度
入栈成功更新栈顶位置

参考代码：

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//栈满的情况
	{
		//如果原来容量为0则让新容量为4，否则为两倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//调整数组栈大小（特别的：当数组指针为NULL时，realloc的作用和malloc的作用一样）
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity);
		if (tmp == NULL)//tmp为NULL时则表示调整数组空间失败，那么就打印错误并结束进程
		{
			perror("realloc fail:");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;//存入数据
	ps->top++;//top位置更新
	return;
}

出栈

注意：

对于空栈不能再进行出栈
栈顶位置减减实现出栈的效果

参考代码：

//出栈
void StackPop(ST* ps)
{
	//避免传入空指针
	assert(ps);
	//出栈到数据个数为0结束
	if (StackEmpty(ps))
		return;
	ps->top--;//让top减减得到出栈的效果
	return;
}

注：这里我们封装了一个判断空栈的函数便于调用

空栈判断

注：C语言没有定义bool类型（C99之前），要在C里面使用需要包含头文件 <stdbool.h>

参考代码：

//是否为空栈
bool StackEmpty(ST* ps)
{
	//避免传入空指针
	assert(ps);

	return ps->top == 0;
}

栈顶数据获取

注意：

空栈时无法获取数据

注：这采用比较暴力的方式（断言），当然也可以选择if条件判断（比较温柔）

参考代码：

//获取栈顶数据
STDataType StackTop(ST* ps)
{
	//避免传入空指针
	assert(ps);
	//空栈（top-1会越界访问）
	assert(!StackEmpty(ps));//暴力断言不为空栈
	return ps->a[ps->top - 1];//这里top-1才是栈顶数据的下标
}

栈存入数据个数

参考代码：

//栈使用大小（存入数据个数）
int StackSize(ST* ps)
{
	//避免传入空指针
	assert(ps);

	return ps->top;
}

栈测试

示例代码：

void test()
{
	ST st;
	StackInit(&st);

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

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

	StackPush(&st, 5);
	StackPush(&st, 6);

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	StackDestroy(&st);
}

结果示图：

队列

概念及结构

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

数据处理方式

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

图示：

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些（出队列效率低）

图示：链表队列

接口展示

//默认队列数据类型
typedef int QDataType;

//队列节点类型（链表队列）
typedef struct QueueNode
{
	//址域
	struct QueueNode* next;
	//值域
	QDataType data;
}QueueNode;
//队列类型(记录队头和队尾)
typedef struct Queue
{
	QueueNode* head;//记录队列头结点地址
	QueueNode* tail;//记录队列尾结点地址
	// size_t _size;//记录队列数据个数（可有可无，自己选择）
}Queue;

//队列初始化
void QueueInit(Queue* pq);
//void QueueInit(QueueNode** pphead, QueueNode** pptail);
//队列销毁
void QueueDestroy(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);

队列类型创建

首先我们是个链表队列，即需要创建节点类型然后在队列常用到入栈和出栈操作（与头删和尾插相关），为了便于找到头结点和尾节点，这里创建一个队列结构体，类型成员为两个结点指针，用来记录头结点和尾节点地址

参考代码：

//默认队列数据类型
typedef int QDataType;

//队列节点类型（链表队列）
typedef struct QueueNode
{
	//址域
	struct QueueNode* next;
	//值域
	QDataType data;
}QueueNode;
//队列类型(记录队头和队尾)
typedef struct Queue
{
	QueueNode* head;//记录队列头结点地址
	QueueNode* tail;//记录队列尾结点地址
	// size_t _size;//记录队列数据个数（可有可无，自己选择）
}Queue;

队列初始化

最开始没有数据，即头指针和尾指针都为NULL

参考代码：

//队列初始化
void QueueInit(Queue* pq)
{
	//避免传入参数错误
	assert(pq);
	//初始化
	pq->head = pq->tail = NULL;
	return;
}

队列销毁

注意：

结点时一个个开辟的，需要一个个进行释放
释放前记得保存下个节点地址，避免地址丢失

参考代码：

//队列销毁
void QueueDestroy(Queue* pq)
{
	//避免传入参数错误
	assert(pq);
	//创建寻址指针
	QueueNode* cur = pq->head;
	while (cur)
	{
		//保存下个结点地址
		QueueNode* next = cur->next;
		//释放当前结点
		free(cur);
		//找到下一个结点
		cur = next;
	}
	return;
}

入队

注意：

入队开辟新结点并初始化
尾插考虑空队列的情况

参考代码：

//入队列
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;
	}
	else
	{
		pq->tail->next = newnode;//尾插
		pq->tail = newnode;//记录新尾节点
	}
	return;
}

出队

注意：

空队列无法再进行出队
出队需要对出队结点释放并更新头指针位置

参考代码：

//出队列
void QueuePop(Queue* pq)
{
	//避免传入参数错误
	assert(pq);
	//为空队列无法出队列
	assert(!QueueEmpty(pq));
	//保存下一个结点
	QueueNode* next = pq->head->next;
	//释放队列头
	free(pq->head);
	//队头更新
	pq->head = next;
	return;
}

队列头结点数据

注意：

空队列没有数据

参考代码：

//队列头结点数据
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;
}

队列存入数据个数

参考代码：

//队列存入数据个数
int QueueSize(Queue* pq)
{
	//避免传入参数错误
	assert(pq);
	int size = 0;
	//遍历队列
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

判断空队列

注：同样的对于C语言使用布尔类型需要包含<stdbool.h>头文件

参考代码：

//判断空队列
bool QueueEmpty(Queue* pq)
{
	//避免传入参数错误
	assert(pq);

	return pq->head == NULL;
}

队列测试

测试代码：

void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QDataType front = QueueFront(&q);
	printf("%d ", front);
	QueuePop(&q);

	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		QDataType front = QueueFront(&q);
		printf("%d ", front);
		QueuePop(&q);
	}
	printf("\n");
}

结果示图：

对上述内容有什么问题记得留言呦~可以的话记得留下你的三连哈！~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-11-01，如有侵权请联系 cloudcommunity@tencent.com 删除

数据处理

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据处理

编程算法

登录后参与评论

0 条评论

热度

【数据结构】开卷数据结构~栈和队列详解

【数据结构】开卷数据结构~栈和队列详解

前言

栈

栈的实现

接口展示

栈结构创建

栈的初始化

栈的销毁

入栈

出栈

空栈判断

栈顶数据获取

栈存入数据个数

栈测试

队列

队列的实现

接口展示

队列类型创建

队列初始化

队列销毁

入队

出队

队列头结点数据

队列尾结点数据

队列存入数据个数

判断空队列

队列测试

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐