深入理解数据结构(3)：栈和队列详解

标头风景图片

  • 文章主题：顺序表和链表详解🌱
  • 所属专栏：深入理解数据结构📘
  • 作者简介：更新有关深入理解数据结构知识的博主一枚，记录分享自己对数据结构的深入解读。😄
  • 个人主页：[₽]的个人主页🔥🔥

栈和队列详解

  • 前言
  • 栈
    • 栈的概念及结构
    • 栈的实现
  • 队列
    • 队列的概念及结构
    • 队列的实现
  • 结语

前言

上文我们已经讲完了线性表中最基本的、最常用的顺序表和链表，这一次博主为大家带来基于顺序表和链表实现的线性表中也是十分常用的数据结构栈和队列的详解，希望能够让你对数据结构有一个更加深入的理解。

栈

栈的概念及结构

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

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，最简单。
栈的数组实现
静态数组栈
下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;

动态数组栈
Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 支持动态增长的栈
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);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void StackInit(Stack* ps)
{
	assert(ps);
	// 栈区数组未创建，赋成NULL
	ps->_a = NULL;
	ps->_capacity = 0;
	// 表示top指向栈顶元素
	ps->_top = -1;
	// 表示top指向栈顶元素的下一个
	//ps->_top = 0
}
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	// 栈区数据已满，扩容
	if (ps->_top + 1 == ps->_capacity)
	{
		// 确定扩容后的新容量，如果是 0 就扩容为 4 ，如果已经扩过容了就将容量在增加一个原来这么多，即扩大为原来的两倍
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		// 扩容
		STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
		// 扩容失败打印失败原因后返回
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		// 未失败将容量更新成新容量，数据指针更新成新指针
		ps->_capacity = newcapacity;
		ps->_a = tmp;
	}
	// 插入数据
	ps->_top++;
	ps->_a[ps->_top] = data;
}
void StackPop(Stack* ps)
{
	assert(ps);
	// 栈不为空时才能删除数据
	assert(ps->_top + 1 > 0);
	// 栈顶元素坐标下移，删除数据
	ps->_top--;
}
STDataType StackTop(Stack* ps)
{
	assert(ps);
	// 不为空，为空弹不出数据来进行访问，并且访问会导致数组越界
	assert(ps->_top + 1 > 0);
	// 返回栈顶元素值
	return ps->_a[ps->_top];
}
int StackSize(Stack* ps)
{
	assert(ps);
	// 返回栈中有效元素个数（栈顶元素 +1 即为栈中有效元素个数）
	return ps->_top + 1;
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	// 为空则返回非 0 的真
	return ps->_top + 1 == 0;
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	// 数据内存释放，再将记录数据的各值清空
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = -1;
}

Test.c

#include "Stack.h"
void StackTest1()
{
	// 初始化栈
	Stack S1;
	StackInit(&S1);

	// 数据入栈
	StackPush(&S1, 1);
	StackPush(&S1, 2);
	StackPush(&S1, 3);
	StackPush(&S1, 4);
	StackPush(&S1, 5);

	// 销毁栈
	StackDestroy(&S1);

	// 检测是否销毁成功
	if (S1._a == NULL && S1._capacity == 0 && S1._top == -1)
		printf("销毁成功！\n");
	else
		printf("销毁失败。\n");
}
void StackTest2()
{
	// 初始化栈
	Stack S1;
	StackInit(&S1);

	// 数据入栈
	StackPush(&S1, 1);
	StackPush(&S1, 2);
	StackPush(&S1, 3);
	StackPush(&S1, 4);
	StackPush(&S1, 5);

	// 从栈顶读取数据后弹出栈中数据
	while (!StackEmpty(&S1))
	{
		printf("%d ", StackTop(&S1));
		StackPop(&S1);
	}
	printf("\n");

	// 销毁栈
	StackDestroy(&S1);
}
void StackTest3()
{
	// 初始化栈
	Stack S1;
	StackInit(&S1);

	// 栈为空时也弹出数据
	StackPop(&S1);

	// 销毁栈
	StackDestroy(&S1);
}
int main()
{
	StackTest3();
	return 0;
}

队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
入队：队列的插入操作叫做入队，入数据在队尾。
出队：队列的删除操作叫做出队。出数据在队头。
（栈和对列都是将出数据的地方叫作顶/头）
队列的出队入队

队列的实现

队列也可以数组和链表的结构实现，使用链表（带头的单链表）的结构实现更优一些(时间复杂度O(1)，比数组来说在队头删除数据更加简洁)，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低(时间复杂度为O(N))。
带头单链表实现的队列
队列
Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int _size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* q)
{
	assert(q);
	// 首尾指针都赋成NULL，元素个数赋0
	q->_front = q->_rear = NULL;
	q->_size = 0;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	// 释放队列数据内存
	QNode* cur = q->_front;
	while (cur)
	{
		QNode* tmp = cur;
		cur = cur->_next;
		free(tmp);
	}
	// 将队列中的首尾指针数据赋成NULL，队列元素个数也置为0
	q->_front = q->_rear = NULL;
	q->_size = 0;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	// 创建新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("maloc fail");
		return;
	}
	newnode->_data = data;
	newnode->_next = NULL;
	// 无节点
	if (q->_front == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	// 有节点
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	// 队尾入数据时总元素个数加一
	q->_size++;
}
void QueuePop(Queue* q)
{
	assert(q);
	// 无节点
	assert(q->_front);
	// 有节点
	QNode* tmp = q->_front;
	q->_front = q->_front->_next;
	free(tmp);
	// 一个节点时，尾指针因为释放节点变成野指针，需要置空
	if (q->_front == NULL)
		q->_rear = NULL;
	// 队头出数据时总元素个数减一
	q->_size--;
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	// 无节点
	assert(q->_front);
	// 有节点
	return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	// 无节点
	assert(q->_front);
	// 有节点
	return q->_rear->_data;
}
int QueueSize(Queue* q)
{
	assert(q);
	// 直接将储存队列主要数据的结构体中的元素个数拿出来返回
	return q->_size;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_size == 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueTest1()
{
	// 队列初始化
	Queue Q1;
	QueueInit(&Q1);

	// 队尾入数据
	QueuePush(&Q1, 1);
	QueuePush(&Q1, 2);
	QueuePush(&Q1, 3);
	QueuePush(&Q1, 4);
	QueuePush(&Q1, 5);

	// 销毁队列
	QueueDestroy(&Q1);

	if (Q1._front == NULL && Q1._rear == NULL && Q1._size == 0)
		printf("销毁成功！\n");
	else
		printf("销毁失败。\n");
}

void QueueTest2()
{
	// 队列初始化
	Queue Q1;
	QueueInit(&Q1);

	// 队尾入数据
	QueuePush(&Q1, 1);
	QueuePush(&Q1, 2);
	QueuePush(&Q1, 3);
	QueuePush(&Q1, 4);
	QueuePush(&Q1, 5);

	// 打印队列中的数据
	printf("Queue: \n");
	while (!QueueEmpty(&Q1))
	{
		printf("%d ", QueueFront(&Q1));
		QueuePop(&Q1);
	}
	printf("\n");

	// 销毁队列
	QueueDestroy(&Q1);
}

void QueueTest3()
{
	// 队列初始化
	Queue Q1;
	QueueInit(&Q1);

	// 队尾入数据
	QueuePush(&Q1, 1);
	QueuePush(&Q1, 2);
	QueuePush(&Q1, 3);
	QueuePush(&Q1, 4);
	QueuePush(&Q1, 5);

	// 打印队列中的数据
	printf("Queue: \n");
	while (!QueueEmpty(&Q1))
	{
		printf("%d ", QueueFront(&Q1));
		QueuePop(&Q1);
	}
	printf("\n");

	// 无节点从队列中弹出数据
	QueuePop(&Q1);

	// 销毁队列
	QueueDestroy(&Q1);
}

void QueueTest4()
{
	// 队列初始化
	Queue Q1;
	QueueInit(&Q1);

	// 队尾入数据
	QueuePush(&Q1, 1);
	QueuePush(&Q1, 2);
	QueuePush(&Q1, 3);
	QueuePush(&Q1, 4);
	QueuePush(&Q1, 5);

	// 打印队尾中的数据
	printf("BackNum: \n%d\n", QueueBack(&Q1));

	// 打印队列中的数据
	printf("Queue: \n");
	while (!QueueEmpty(&Q1))
	{
		printf("%d ", QueueFront(&Q1));
		QueuePop(&Q1);
	}
	printf("\n");

	// 销毁队列
	QueueDestroy(&Q1);
}

void QueueTest5()
{
	// 队列初始化
	Queue Q1;
	QueueInit(&Q1);

	// 队尾入数据
	QueuePush(&Q1, 1);
	QueuePush(&Q1, 2);
	QueuePush(&Q1, 3);
	QueuePush(&Q1, 4);
	QueuePush(&Q1, 5);

	// 打印队列中的数据个数
	printf("QueueSize: \n%d\n", QueueSize(&Q1));

	// 打印队列中的数据
	printf("Queue: \n");
	while (!QueueEmpty(&Q1))
	{
		printf("%d ", QueueFront(&Q1));
		QueuePop(&Q1);
	}
	printf("\n");

	// 销毁队列
	QueueDestroy(&Q1);
}

int main()
{
	QueueTest5();
	return 0;
}

环形队列
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统中的生产者消费者模型中就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现（差别不是很大，并且环形队列的元素个数是固定的，但也可以不是在栈区的静态数组实现的，其可用在动态区用长度不变的数组来实现内存大小不变的效果，可理解成动态数组大小不变所实现的仿静态效果，并且虽逻辑结构上两种环形队列都相接，数组型的环形队列物理结构上首尾不相接，链表物理结构上相接）。
环形队列逻辑图
通常为区分队头和队尾，会在数组中多加一个元素来既防止数组越界，又能够解决因空和满索引条件相同而造成无法判断的假溢出问题（此时环形队列容量为数组总元素个数减一）：
数组环形队列实现的底层逻辑图

结语

以上就是博主对栈和队列的详解，😄希望对你的数据结构的学习有所帮助！看都看到这了，点个小小的赞或者关注一下吧（当然三连也可以~），你的支持就是博主更新最大的动力！让我们一起成长，共同进步！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/504157.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

系统优化都没做过？看这篇就够了

系统优化都没做过？看这篇就够了

目录 一、系统优化指标 二、系统优化简介 三、系统优化 3.1 CPU 高 3.2 内存占用高 业务引起的内存升高 程序自身引起的内存问题 3.3 磁盘I/O 3.4 网络 3.5 数据库优化 3.6 响应时间高 3.7 吞吐量 3.8 代码层面优化 3.9 业务优化 四、JVM优化 4.1 堆内存设置 4.2 选择何时的…
阅读更多...
半导体工艺技术

半导体工艺技术

完整内容点击&#xff1a;【半导体工艺技术】
阅读更多...
win10蓝牙开关不见了怎么办,win10设置里面蓝牙开关不见了

win10蓝牙开关不见了怎么办,win10设置里面蓝牙开关不见了

最近&#xff0c;有用户在使用win10系统的时候&#xff0c;发现设置蓝牙和其他设备中蓝牙开关不见了。正常情况下&#xff0c;“蓝牙和其他设备”下面是有蓝牙开启开关的&#xff0c;没有的话是怎么回事呢?出现这样的情况&#xff0c;可能是应为系统没有将测到蓝牙设备或者蓝牙…
阅读更多...
高德地图key注册教程_地图数据采集软件

高德地图key注册教程_地图数据采集软件

1.先注册成为开发者账号。 2.再申请高德地图Key。 3.把申请得到的高德地图Key填入软件中。 1.请先打开以下连接 高德地图key注册地址 易地图数据采集大师手机App版介绍 易地图数据采集大师电脑PC版介绍 2.注册新用&#xff08;如果已有开发者账号&#xff0c;本步可省略&am…
阅读更多...
知识蒸馏详解及pytorch官网demo案例

知识蒸馏详解及pytorch官网demo案例

知识蒸馏Knowledge Distillation(KD) 1、简介 一种模型压缩方法 知识蒸馏的一般框架&#xff08;如下图&#xff09; 三部分&#xff1a;知识、蒸馏算法、师生架构。 知识 将知识分为三种形式&#xff1a;基于响应的&#xff08;response-based&#xff09;、基于特征的&…
阅读更多...
pytest--python的一种测试框架--pytest常用断言类型

pytest--python的一种测试框架--pytest常用断言类型

一、pytest常用断言类型 等于: 不等于&#xff1a;&#xff01; 大于&#xff1a;> 小于&#xff1a;< 属于&#xff1a;in 不属于&#xff1a;not in 大于等于&#xff1a;> 小于等于&#xff1a;< 是&#xff1a;is 不是&#xff1a;is not def test_two():ass…
阅读更多...
酷得单片机方案 2.4G儿童遥控漂移车

酷得单片机方案 2.4G儿童遥控漂移车

电子方案开发定制&#xff0c;我们是专业的 东莞酷得智能单片机方案之2.4G遥控玩具童车具有以下比较有特色的特点&#xff1a; 1、内置充电电池&#xff1a;这款小车配备了可充电的电池&#xff0c;无需频繁更换电池&#xff0c;既环保又方便。充电方式可能为USB充电或者专用…
阅读更多...
LATTICE进阶篇DDR2--(0)获取ddr2 IP核

LATTICE进阶篇DDR2--(0)获取ddr2 IP核

前言 想要仿真lattice的DDR2由来已久&#xff0c;但苦于对其了解甚少&#xff0c;在查阅过很多资料后&#xff0c;终于对这个IP核的仿真有了一些了解。 现做一些总结&#xff0c;以备不时之需&#xff0c;也让有需要的朋友&#xff0c;少走一些弯路。 环境&#xff1a;win10…
阅读更多...
算法学习——LeetCode力扣动态规划篇5

算法学习——LeetCode力扣动态规划篇5

算法学习——LeetCode力扣动态规划篇5 198. 打家劫舍 198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09; 描述 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统…
阅读更多...
通知中心架构：打造高效沟通平台，提升信息传递效率

通知中心架构：打造高效沟通平台，提升信息传递效率

随着信息技术的快速发展&#xff0c;通知中心架构作为一种关键的沟通工具&#xff0c;正逐渐成为各类应用和系统中必不可少的组成部分。本文将深入探讨通知中心架构的意义、设计原则以及在实际场景中的应用。 ### 什么是通知中心架构&#xff1f; 通知中心架构是指通过集中管…
阅读更多...
信息学奥赛一本通T1268-完全背包问题

信息学奥赛一本通T1268-完全背包问题

solution1 二维形式 #include<iostream> #include<algorithm> using namespace std; const int maxn 35, maxv 210; int w[maxn], c[maxn], dp[maxn][maxv]; int main(){int n, m;scanf("%d%d", &m, &n);for(int i 1; i < n; i){scanf(&…
阅读更多...
电脑win10系统更新后很卡怎么办,win10电脑更新完系统特别卡

电脑win10系统更新后很卡怎么办,win10电脑更新完系统特别卡

更新或者升级win10系统后发现电脑变卡了，这是什么原因呢?如果电脑硬件不是特别差，那么可以按照下面的方法来缓解卡顿，因为可能是内存不足所引起的，试试清理更新缓存和禁用开机启动项。但如果是硬件较低或者太老旧，并且本身的内存就很小的话，那么建议你还是升级硬件吧。下…
阅读更多...
.NET 开发支持技术路线 .Net 7 将停止支持

.NET 开发支持技术路线 .Net 7 将停止支持

.NET 开发技术路线图 微软方面强调&#xff0c;使用 .NET 7 的应用程序将在支持结束后继续运行&#xff0c;但用户可能无法获得 .NET 7 应用程序的技术支持。他们不会继续为 .NET 7 发布新的安全更新&#xff0c;用户可能会面临安全漏洞问题。 开发人员必须使用 .NET 8 SDK 构建…
阅读更多...
Windows提权！！！

Windows提权！！！

之前讲过一下提权&#xff0c;但是感觉有点不成体系&#xff0c;所以我们就成体系的来讲一下这个操作系统的提权 目录 Windows的提权 1.Widnows的内核溢出提权 1.MSF自带的提权模块&#xff08;Win11都能提上来&#xff0c;有点牛逼&#xff09; 2.CS的插件提权 3.补丁对比…
阅读更多...
毕设论文目录设置

毕设论文目录设置

添加目录 选择一种格式的自动目录 更新目录 发现该目录中只有1、2章&#xff0c;3、4章 然后再点击更新目录 对应的&#xff0c;小标题添加二级目录
阅读更多...
基于JavaSpringMVC+Mybatis+Jquery高校毕业设计管理系统设计和实现

基于JavaSpringMVC+Mybatis+Jquery高校毕业设计管理系统设计和实现

基于JavaSpringMVCMybatisJquery高校毕业设计管理系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐…
阅读更多...
【C语言】结构体详解（一）

【C语言】结构体详解（一）

目录 1、什么是结构体? 2、结构体成分 3、结构体变量的定义与初始化 3.1、结构体变量的三种定义方式 3.2、结构体变量的初始化 4、结构体成员的访问&#xff08;两种方式&#xff09; 4.1、直接访问 4.2、间接访问 5、结构的特殊声明 5.1、不完全声明&#xff08;匿…
阅读更多...
医院陪诊管理系统（源码+文档）

医院陪诊管理系统（源码+文档）

TOC) 文件包含内容 1、搭建视频 2、流程图 3、开题报告 4、数据库 5、参考文献 6、服务器接口文件 7、接口文档 8、任务书 9、功能图 10、环境搭建软件 11、十六周指导记录 12、答辩ppt模板 13、技术详解 14、前端后台管理&#xff08;管理端程序&#xff09; 15、项目截图 1…
阅读更多...
06-JavaScript DOM对象

06-JavaScript DOM对象

1. 从ECMA到W3C 我们知道&#xff0c;ECMA定义的是js的变量语法等基础的标准规范&#xff0c;而W3C是针对浏览器API提出的规范&#xff0c; 所以我们要工作不可能只了解语法&#xff0c;我们的代码要在浏览器上跑起来就需要我们去了解W3C的标准。 那么W3C规定了哪一系列的的A…
阅读更多...
深入PostgreSQL中的pg_global表空间

深入PostgreSQL中的pg_global表空间

pg_global表空间的位置 在PG当中&#xff0c;一个实例(cluster)初始化完以后&#xff0c;你会看到有下边两个与表空间相关的目录生成&#xff1a; $PGDATA/base $PGDATA/global 我们再用元命令\db以及相关视图看看相应的表空间信息&#xff1a; postgres# \db …
阅读更多...
最新文章

Copyright @ 2022~2023