【初阶数据结构】详解栈和队列（来自知识星空的一抹流光）

文章目录

  • 前言
  • 1. 栈
    • 1.1 栈的概念及结构
    • 1.2 栈的实现
      • 1.2.1 "栈"实现的选择
    • 1.3 栈的代码实现
      • 1.3.1 栈的结构体定义（用的是顺序表）
      • 1.3.2 栈的头文件设置
      • 1.3.3 栈的各功能的实现
  • 2. 队列
    • 2.1 队列的概念及结构
    • 2.2 "队列"实现的选择
    • 2.3 队列的代码实现
      • 2.3.1 队列的结构体定义
      • 2.3.2 队列的头文件
      • 2.3.3 队列各功能的实现

前言

在学习栈和队列中，你是否会被人提问过什么是栈和队列？是否知道栈和队列的特征以及栈和队列的代码实现？

通过本文的讲解，以上的问题都会一扫而空的！！！💖

话不多说，让我们开启轻松而愉悦的探索之旅吧。
哈哈哈

1. 栈

1.1 栈的概念及结构

栈：一种特殊的线性表，其只允许再固定的一端进行插入和删除数据的操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的元素遵循着**后进先出（LIFO：Last In First Out）**的原则。

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

1.2 栈的实现

我们根据栈的特点，以及我们所学过的数据结构(顺序表、链表、双向链表)中选择，我们会选择哪种数据结构呢？

我会更倾向于顺序表。但其实，栈的实现一般可以用数组或者链表。

1.2.1 "栈"实现的选择

之所以选择顺序表，主要有以下的原因：

  1. 容易找到栈顶的位置。
    为什么会这样说呢？你可以想一下**，顺序表的底层是数组，数组如果我要查找到最后一个元素是比较容易的。而相较于链表来说，就要遍历整个链表，从而遭到链表的为节点，在进行数据的操作，那此时的算法时间复杂度就为O(n)了**。那可能有的人思维比较活跃，他说那我直接把链表的头部当作栈顶的位置，那我就不需要找链表的尾节点，那时间复杂度就变为O(1)了。没错，这个就是用链表实现栈的一种优化方式。不过单凭这一点，还不足以让我放弃使用顺序表这个念头！
  2. 缓存命中率高。
    我们都知道数组在内存中是连续存储的。那根据空间的局部性原理，缓存的命中率就会高，这也就意味着CPU读取数据的速度就会加快，从而给程序的运行提高了速度。这个特点是链表无法比拟的。

顺序表实现栈的情况
链表实现栈的情况

1.3 栈的代码实现

1.3.1 栈的结构体定义（用的是顺序表）

//使用动态顺序表实现栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top; //可以看作栈顶指针
	int capacity; //记录当前栈可用的空间
}Stack;

1.3.2 栈的头文件设置

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//栈的接口实现

//栈的初始化
void STInit(Stack* ps);

//添加数据 - 栈
void STPush(Stack* ps,STDataType x);

//删除数据 - 栈
void STPop(Stack* ps);

//栈的销毁
void STDestory(Stack* ps);

//查看栈顶元素
STDataType STTop(Stack* ps);

//判断栈是否未空
int STEmpty(Stack* ps);

//查看栈的大小
int STSize(Stack* ps);

1.3.3 栈的各功能的实现

#define _CRT_SECURE_NO_WARNINGS	

#include"Stack.h"

//栈的初始化
void STInit(Stack* ps)
{
	ps->arr = (STDataType*)malloc(sizeof(STDataType)*4); //一开始先给4个大小的空间

	ps->top = 0;

	ps->capacity = 4;
}

//添加数据 - 栈
void STPush(Stack* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		//说明得扩容了
		STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STDataType)* 2* ps->capacity);

		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}

		ps->arr = tmp;

		ps->capacity*=2;
	}

	ps->arr[ps->top] = x;
	ps->top++;
}

//删除数据 - 栈
void STPop(Stack* ps)
{
	assert(ps && ps->arr);
	assert(!STEmpty(ps));

	ps->top--;
}


//栈的销毁
void STDestory(Stack* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;

	ps->capacity = 0;
	ps->top = 0;
}

//查看栈顶元素
STDataType STTop(Stack* ps)
{
	return ps->arr[ps->top-1];
}

//判断栈是否未空
int STEmpty(Stack* ps)
{
	if (ps->top == 0)
	{
		return 1;
	}

	return 0;
}

//查看栈的大小
int STSize(Stack* ps)
{
	return ps->top + 1;
}

好了，到这里，关于栈的知识已经全部讲解完毕了。接下来，我们再来看看另一个数据结构——“队列”！
哈哈哈

2. 队列

2.1 队列的概念及结构

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

队列的一些基本操作：

  • 入队列：进行插入数据的操作。
    • 进行插入操作的一端称为队尾；
  • 出队列：进行伤处数据的操作。
    • 进行删除数据的一端称为队头；

为了让大家对队列有个形象的认知，我会给大家展示一副关于的队列的图：
队列

2.2 "队列"实现的选择

经过了栈的洗礼，大家或多或少都应该猜出来了，队列是使用链表来实现的。

如果你没有猜到，没关系，听我给你解释一下是为什么。

我们可以知道的一个信息就是：队列只能在一端进行插入操作，在另一端进行删除操作。如果我们使用顺序表来实现，在插入操作环节比较容易实现，但是在删除操作用数组实现就比较繁琐了。但是，如果我们使用链表来实现的话，只要我们合理的控制头节点和尾节点，就能够很方便的实现插入和删除操作。这个就是我们为什么会推荐选择用链表来实现队列。

以下就是用链表来实现队列的示例图：
队列
那接下来，我们就用代码实现队列。

2.3 队列的代码实现

这个实现过程中，可能有一个点让大家比较难以理解，其它点都是比较简单的。

2.3.1 队列的结构体定义

typedef int QDataType;
typedef struct QNode
{
	QDataType data;
	struct QNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

这里就是那个难点所在！为什么这里会是要定义两个结构体，你在"栈"实现的时候，才定义一个结构体啊？如果有这个问题的读者，那么恭喜你们跟上了本文的思路了。

我在之前说过，实现队列的插入或者删除操作时，只要我们能够合理的控制头节点和尾节点的指针，就足以能够实现队列。那此时，我们就要想一下，能不能有个更简单的方式，一起控制着头指针和尾指针。方法就是：将头节点的指针和尾节点的指针用一个结构体给打包起来，只要我们使用头节点和尾节点的指针时，就不要额外再定义其它变量了。

如果你还不理解的话，我再跟你讲一下，如果不使用这个方式定义结构体的危害。
如果你不这样做的话，你再给函数传递参数时，你就得往函数里面多传递两个参数或者是每当进行删除或插入数据时，我们都得先定义两个变量分别代表头节点和尾节点，十分的繁琐！

相信经过以上的讲解，你已经理解了为什么要使用两个结构体。

2.3.2 队列的头文件

#pragma once

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

//队列的初始化
void QInit(Queue* p);

//销毁队列
void QDestory(Queue* p);

//添加数据
void QPush(Queue* p, QDataType x);

//删除数据
void QPop(Queue* p);

//查看队头元素
QDataType QFront(Queue* p);

//查看队尾元素
QDataType QBack(Queue* p);

//队列的大小
int QSize(Queue* p);

//判断列表是否为空
bool QEmpty(Queue* p);

2.3.3 队列各功能的实现

#define _CRT_SECURE_NO_WARNINGS	

#include"queue.h"


//队列的初始化
void QInit(Queue* p)
{
	assert(p);

	p->head = p->tail = NULL;
	p->size = 0;
}

//销毁队列
void QDestory(Queue* p)
{
	assert(p);

	QNode* pcur = p->head->next;
	
	
	while (pcur != NULL)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pcur = NULL;
}

//添加数据
void QPush(Queue* p, QDataType x)
{
	assert(p);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	//插入数据，只能在队尾插入
	if (p->head == NULL)
	{
		assert(p->tail == NULL);
		p->head = p->tail = newnode;
	}

	else
	{
		p->tail->next = newnode;
		p->tail = p->tail->next;
	}

	p->size++;
}

//删除数据
void QPop(Queue* p)
{
	assert(p && p->head);

	//删除数据只能够在队头删除
	QNode* pcur = p->head;

	//但只有一个节点的情况
	if (p->head == p->tail)
	{
		free(p->head);
		p->head = p->tail = NULL;
	}

	else
	{
		p->head = pcur->next;
		free(pcur);

		pcur = NULL;
	}


	p->size--;
	
}

//查看队头元素
QDataType QFront(Queue* p)
{
	assert(p && p->head);

	return p->head->data;
}

//查看队尾元素
QDataType QBack(Queue* p)
{
	assert(p && p->tail);

	return p->tail->data;
}

//队列的大小
int QSize(Queue* p)
{
	assert(p);

	return p->size;
}

//判断列表是否为空
bool QEmpty(Queue* p)
{
	assert(p);
	if (QSize(p) == 0)
	{
		return true;
	}

	return false;
}

好了，到这里，栈和队列的知识就已经全部讲解完毕了。之后我会出关于这个知识点一系列的编程题详解，希望大家能够持续的关注！

如果觉得本文将的还不错的话，麻烦给偶点个赞吧！！！
hahaha

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

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

相关文章

【即时通讯】轮询方式实现

【即时通讯】轮询方式实现

技术栈 LayUI、jQuery实现前端效果。django4.2、django-ninja实现后端接口。 代码仓 - 后端 代码仓 - 前端 实现功能 首次访问页面并发送消息时需要设置昵称发送内容为空时要提示用户不能发送空消息前端定时获取消息&#xff0c;然后展示在页面上。 效果展示 首次发送需要…
阅读更多...
深入理解数据库的 4NF：多值依赖与消除数据异常

深入理解数据库的 4NF：多值依赖与消除数据异常

在数据库设计中&#xff0c; "范式" 是一个常常被提到的重要概念。许多初学者在学习数据库设计时&#xff0c;经常听到第一范式&#xff08;1NF&#xff09;、第二范式&#xff08;2NF&#xff09;、第三范式&#xff08;3NF&#xff09;以及 BCNF&#xff08;Boyce-…
阅读更多...
滑动窗口在算法中的应用

滑动窗口在算法中的应用

滑动窗口是一种经典的算法技巧&#xff0c;就像在处理一系列动态数据时&#xff0c;用一扇可以滑动的“窗口”来捕捉一段连续的子数组或子字符串。通过不断地移动窗口的起点或终点&#xff0c;我们能够以较低的时间复杂度来解决一系列问题。在这篇文章中&#xff0c;我们将通过…
阅读更多...
维信小程序禁止截屏/录屏

维信小程序禁止截屏/录屏

一、维信小程序禁止截屏/录屏 //录屏截屏,禁用wx.setVisualEffectOnCapture({visualEffect:hidden});wx.setVisualEffectOnCapture(Object object) 测试安卓手机&#xff1a; 用户截屏&#xff0c;被禁用 用户录屏&#xff0c;录制的是空白内容/黑色内容的视频。 二、微信小…
阅读更多...
C++ | Leetcode C++题解之第386题字典序排数

C++ | Leetcode C++题解之第386题字典序排数

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<int> lexicalOrder(int n) {vector<int> ret(n);int number 1;for (int i 0; i < n; i) {ret[i] number;if (number * 10 < n) {number * 10;} else {while (number % 10 9 || numbe…
阅读更多...
EasyPlayer.js网页H5 Web js播放器能力合集

EasyPlayer.js网页H5 Web js播放器能力合集

最近遇到一个需求&#xff0c;要求做一款播放器&#xff0c;发现能力上跟EasyPlayer.js基本一致&#xff0c;满足要求&#xff1a; 需求 功性能 分类 需求描述 功能 预览 分屏模式 单分屏&#xff08;单屏/全屏&#xff09; 多分屏&#xff08;2*2&#xff09; 多分屏…
阅读更多...
【阿一网络安全】如何让你的密码更安全？（二） - 非对称加密

【阿一网络安全】如何让你的密码更安全？（二） - 非对称加密

上次《【阿一网络安全】如何让你的密码更安全&#xff1f;(一) - 对称加密》提到加密算法的对称加密&#xff0c;我们这次来聊聊非对称加密。 和对称加密不同&#xff0c;非对称加密的加密密钥和解密密钥不同。 非对称加密 大概过程就是&#xff0c;发送方使用公钥对明文数据…
阅读更多...
mac 安装redis

mac 安装redis

官网下载指定版本的redis https://redis.io/ 目前3.2.0 是最新最稳定的 版本 这里是历史版本下载 下载指定版本 安装 1.放到自定义目录下并解压 2.打开终端&#xff0c;执行命令 cd redis的安装目录下 make test -- 此命令的作用是将redis源代码编译成可执行文件&#xff0c…
阅读更多...
SPI驱动学习五（如何编写SPI设备驱动程序）

SPI驱动学习五（如何编写SPI设备驱动程序）

目录 一、SPI驱动程序框架二、怎么编写SPI设备驱动程序1. 编写设备树2. 注册spi_driver3. 怎么发起SPI传输3.1 接口函数3.2 函数解析 三、示例1&#xff1a;编写SPI_DAC模块驱动程序1. 要做什么事情2. 硬件2.1 原理图2.2 连接 3. 编写设备树4. 编写驱动程序5. 编写app层操作程序…
阅读更多...
C++语法知识点合集：11.模板

C++语法知识点合集：11.模板

文章目录 一、非类型模板参数1.非类型模板参数的基本形式2.指针作为非类型模板参数3.引用作为非类型模板参数4.非类型模板参数的限制和陷阱&#xff1a;5.几个问题 二、模板的特化1.概念2.函数模板特化3.类模板特化(1)全特化(2)偏特化(3)类模板特化应用示例 三、模板分离编译1.…
阅读更多...
微带结环行器仿真分析+HFSS工程文件

微带结环行器仿真分析+HFSS工程文件

微带结环行器仿真分析HFSS工程文件 工程下载&#xff1a;微带结环行器仿真分析HFSS工程文件 我使用HFSS版本的是HFSS 2024 R2 参考书籍《微波铁氧体器件HFSS设计原理》和视频微带结环行器HFSS仿真 1、环形器简介 环行器是一个有单向传输特性的三端口器件&#xff0c;它表明…
阅读更多...
使用Qt编程QtNetwork无法使用

使用Qt编程QtNetwork无法使用

使用 VS 构建 Qt 项目时 QtNetwork 无法使用的问题 - 摘叶飞镖 - 博客园 (cnblogs.com) 另外,强烈建议在使用QNetworkAccessManager之前看看这篇文章: Qt 之 QNetworkAccessManager踏坑记录-CSDN博客 C Qt开发&#xff1a;QNetworkAccessManager网络接口组件 阅读目录 1.1 …
阅读更多...
在Ubuntu上运行QtCreator相关程序

在Ubuntu上运行QtCreator相关程序

背景&#xff1a;希望尝试在Linux系统上跑一下使用QtCreator相关的程序&#xff0c;因为有一些工作岗位要求有Linux上使用Qt的经验。 (1)我是把Windows上的程序移过来的&#xff0c;Windows上文件名称是不区分大小写的。 而Ubuntu上是区分的 所以一部分头文件需要进行修改&am…
阅读更多...
idea创建SpringBoot项目

idea创建SpringBoot项目

目录 1. 新建一个SpringBoot项目 2. 使用Springboot官网创建项目 3. 使用阿里云地址创建SpringBoot项目 4. 使用maven创建SpringBoot项目 5. 在Idea中隐藏指定文件/文件夹 1. 新建一个SpringBoot项目 Springboot2 要求jdk版本: 1.8 maven: 3.3 内嵌的tomcat: tomcat9 我们…
阅读更多...
深度学习（一）-感知机+神经网络+激活函数

深度学习（一）-感知机+神经网络+激活函数

深度学习概述 深度学习的特点 优点 性能更好 不需要特征工程 在大数据样本下有更好的性能 能解决某些传统机器学习无法解决的问题 缺点 小数据样本下性能不如机器学习 模型复杂 可解释性弱 深度学习与传统机器学习相同点 深度学习、机器学习是同一问题不同的解决方法 …
阅读更多...
11.5.软件系统分析与设计-面向对象的程序设计与实现

11.5.软件系统分析与设计-面向对象的程序设计与实现

面向对象的程序设计与实现 设计模式 Java代码 C代码
阅读更多...
SQL进阶技巧：每年在校人数统计 | 区间重叠问题

SQL进阶技巧：每年在校人数统计 | 区间重叠问题

目录 0 问题分析 1 数据准备 2 问题分析 3 小结 区间重叠问题 0 问题分析 有一个录取学生人数表 in_school_stu，记录的是每年录取学生的人数及录取学生的学制，计算每年在校学生人数。 1 数据准备 create table in_school_stu as ( select stack(5,1,2001,2,1200,2,2000…
阅读更多...
UML的图及其他图补充

UML的图及其他图补充

一、UML图 1.类图 ‌类图‌是统一建模语言&#xff08;UML&#xff09;中的一种静态结构图&#xff0c;主要用于描述软件系统的静态结构。它显示了模型中的类、类的内部结构以及它们与其他类的关系。类图是面向对象建模的主要组成部分&#xff0c;用于对系统的词汇进行建模、对…
阅读更多...
SigLIP——采用sigmoid损失的图文预训练方式

SigLIP——采用sigmoid损失的图文预训练方式

SigLIP——采用sigmoid损失的图文预训练方式 FesianXu 20240825 at Wechat Search Team 前言 CLIP中的infoNCE损失是一种对比性损失&#xff0c;在SigLIP这个工作中&#xff0c;作者提出采用非对比性的sigmoid损失&#xff0c;能够更高效地进行图文预训练&#xff0c;本文进行…
阅读更多...
93. UE5 GAS RPG 应用负面效果表现

93. UE5 GAS RPG 应用负面效果表现

在上一篇文章里&#xff0c;我们实现了添加负面效果GE&#xff0c;并且在添加GE时&#xff0c;也会给角色应用一个负面效果标签作为标识。在这一篇里&#xff0c;我们将通过负面效果标签标识&#xff0c;应用角色身上展现对应的负面效果的表现。 我们将在这篇文章里添加一个自定…
阅读更多...
最新文章

Copyright @ 2022~2023