数据结构4——栈和队列

目录

1.栈

1.1.栈的概念及结构

1.2栈的实现

2.队列

2.1队列的概念及结构

2.2队列的实现


1.栈

1.1.栈的概念及结构

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

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

出栈:栈的删除操作叫做出栈,出数据也在栈顶

(图源来自天命客)

1.2栈的实现

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

(图来自:小白苦学)

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;
//支持动态增长的栈
typedef struct Stact
{int* a;int top;int capacity;
}ST;
//初始化栈
void STInit(ST*ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps,STDataType x);
//出栈
void STPop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"void STInit(ST* ps)
{ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc::fail");return;}ps->top = 0;                 //ps->top=0;  top是栈顶元素的下一个位置ps->capacity = 4;            //ps->top=-1;  top是栈顶元素位置
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc::fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}int STSize(ST* ps)
{return ps->top;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}bool STEmpty(ST* ps)
{return ps->top == 0;
}

2.队列

2.1队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。(可以抽象理解为:左耳进右耳出)队列具有先进先出FIFO(First In First Out)入列队:进行插入操作一端称为队尾;出队列:进行删除操作的一端称为队头

(图源:长相思979)

2.2队列的实现

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

(图源:weixin_52872520)

Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);void QueueDestroy(Queue* pq);void QueuePush(Queue* pq,QDataType x);void QueuePop(Queue* pq);int QueueSize(Queue* pq);bool QueueEmpty(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while(cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc::fail");return;}newnode->next = NULL;newnode->data = x;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

家政小程序开发,打造便捷家政生活小程序

目前&#xff0c;随着社会人就老龄化和生活压力的加重&#xff0c;家政服务市场的需求正在不断上升&#xff0c;家政市场的规模也正在逐渐扩大&#xff0c;发展前景可观。 在市场快速发展的影响下&#xff0c;越来越多的企业开始进入到市场中&#xff0c;同时家政市场布局也发…

Spring Cloud Alibaba(六)

目录&#xff1a; 分布式链路追踪-SkyWalking为什么需要链路追踪什么是SkyWalkingSkyWalking核心概念什么是探针Java AgentJava探针日志监控实现之环境搭建Java探针日志监控实现之探针实现编写探针类TestAgent搭建 ElasticsearchSkyWalking服务环境搭建搭建微服务微服务接入Sky…

HTTP 探秘之旅:从入门到未来

文章目录 导言&#xff1a;目录&#xff1a;第一篇&#xff1a;HTTP&#xff0c;互联网的“快递员”第二篇&#xff1a;从点开网页到看到内容&#xff0c;HTTP 究竟做了什么&#xff1f;第三篇&#xff1a;HTTP 的烦恼与进化史第四篇&#xff1a;HTTP 的铠甲——HTTPS 的故事第…

万字长文解读深度学习——多模态模型BLIP2

&#x1f33a;历史文章列表&#x1f33a; 深度学习——优化算法、激活函数、归一化、正则化 深度学习——权重初始化、评估指标、梯度消失和梯度爆炸 深度学习——前向传播与反向传播、神经网络&#xff08;前馈神经网络与反馈神经网络&#xff09;、常见算法概要汇总 万字长…

qt QToolBox详解

1、概述 QToolBox是Qt框架中的一个控件&#xff0c;它提供了一个带标签页的容器&#xff0c;用户可以通过点击标签页标题来切换不同的页面。QToolBox类似于一个带有多页选项卡的控件&#xff0c;但每个“选项卡”都是一个完整的页面&#xff0c;而不仅仅是标签。这使得QToolBo…

如何把阿里云ECS里的文件下载到本地(免登录免配置)

如何把阿里云ECS里的文件下载到本地&#xff08;免登录免配置&#xff09; 作为一个阿里云ECS的用户&#xff0c;Up时长会遇到希望把ECS里的文件下载到自己的个人电脑&#xff0c;然后在自己的电脑里面查看&#xff0c;保存或者发送给别人。最近发现阿里云新上了一个功能&…

Centos7安装MySQL8.0详细教程(压缩包安装方式)

本章教程&#xff0c;主要介绍如何在Centos7上安装MySQL8.0版本数据库&#xff08;压缩包安装方式&#xff09; 一、卸载系统自带的 Mariadb 1、查询 rpm -qa|grep mariadb2.、卸载 如果有查询结果&#xff0c;就进行卸载&#xff0c;没有就跳过该步骤。 rpm -e --nodeps mar…

c++预编译头文件

文章目录 c预编译头文件1.使用g编译预编译头文件2.使用visual studio进行预编译头文件2.1visual studio如何设置输出预处理文件&#xff08;.i文件&#xff09;2.2visual studio 如何设置预编译&#xff08;初始创建空项目的情况下&#xff09;2.3 visual studio打开输出编译时…

MySql:理解数据库

目录 一、什么是数据库 第一层理解 第二层理解 第三层理解 二、Linux下的数据库 三、基本认识 登录数据库时&#xff0c; mysql -u root -h 127.0.0.1 -P 3306 -p -h指定MySql服务器所在主机&#xff0c;若在本地则为回环地址。-P表示目标主机上MySql服务端口号 一般简单…

Spire.PDF for .NET【页面设置】演示:旋转 PDF 中的页面

在某些情况下&#xff0c;您可能需要旋转 PDF 页面。例如&#xff0c;当您收到包含混乱页面的 PDF 文档时&#xff0c;您可能希望旋转页面以便更轻松地阅读文档。在本文中&#xff0c;您将学习如何使用Spire.PDF for .NET在 C# 和 VB.NET 中旋转 PDF 中的页面。 Spire.PDF for…

【JavaEE初阶 — 网络编程】实现基于TCP协议的Echo服务

TCP流套接字编程 1. TCP &#xff06; UDP 的区别 TCP 的核心特点是面向字节流&#xff0c;读写数据的基本单位是字节 byte 2 API介绍 2.1 ServerSocket 定义 ServerSocket 是创建 TCP 服务端 Socket 的API。 构造方法 方法签名 方法说明 ServerS…

[linux应用]emby媒体服务器软件简单部署和使用

一、介绍 Emby 是一款媒体服务器软件&#xff0c;用于组织、管理和共享个人的音乐、电影、电视节目和其他媒体文件。简单来说&#xff0c;是管理和播放电影的软件。官方网址&#xff1a;Emby - The open media solution 二、部署 安装包下载地址&#xff1a;Download Emby -…

burp2

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…

基于hexo框架的博客搭建流程

这篇博文讲一讲hexo博客的搭建及文章管理&#xff0c;也算是我对于暑假的一个交代 &#xff01;&#xff01;&#xff01;注意&#xff1a;下面的操作是基于你已经安装了node.js和git的前提下进行的&#xff0c;并且拥有github账号 创建一个blog目录 在磁盘任意位置创建一个…

106.【C语言】数据结构之二叉树的三种递归遍历方式

目录 1.知识回顾 2.分析二叉树的三种遍历方式 1.总览 2.前序遍历 3.中序遍历 4.后序遍历 5.层序遍历 3.代码实现 1.准备工作 2.前序遍历函数PreOrder 测试结果 3.中序遍历函数InOrder 测试结果 4.后序遍历函数PostOrder 测试结果 4.底层分析 1.知识回顾 在99.…

游戏引擎学习第25天

Git: https://gitee.com/mrxiao_com/2d_game 今天的计划 总结和复述&#xff1a; 这段时间的工作已经接近尾声&#xff0c;虽然每次编程的时间只有一个小时&#xff0c;但每一天的进展都带来不少收获。尽管看起来似乎花费了很多时间&#xff0c;实际上这些日积月累的时间并未…

【C++】深入优化计算题目分析与实现

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;第一题&#xff1a;圆的计算我的代码实现代码分析改进建议改进代码 老师的代码实现代码分析可以改进的地方改进代码 &#x1f4af;第二题&#xff1a;对齐输出我的代码实现…

Kafka配置SASL/PLAINTEXT安全认证

1、下载安装 Kafka下载地址&#xff1a;Apache Kafka 下载文件 wget https://downloads.apache.org/kafka/3.8.0/kafka_2.12-3.8.0.tgz 文件解压缩 tar -zxvf kafka_2.12-3.8.0.tgz 进入目录 cd kafka_2.12-3.8.0 2、Zookeeper 配置 2.1、修改 Zookeeper 配置文件 con…

go并发设计模式runner模式

go并发设计模式runner模式 真正运行的程序不可能是单线程运行的&#xff0c;go语言中最值得骄傲的就是CSP模型了&#xff0c;可以说go语言是CSP模型的实现。 假设现在有一个程序需要实现&#xff0c;这个程序有以下要求&#xff1a; 程序可以在分配的时间内完成工作&#xff0…

机器学习周志华学习笔记-第13章<半监督学习>

机器学习周志华学习笔记-第13章&#xff1c;半监督学习&#xff1e; 卷王&#xff0c;请看目录 13半监督学习13.1 生成式方法13.2 半监督SVM13.3 基于分歧的方法13.4 半监督聚类 13半监督学习 前面我们一直围绕的都是监督学习与无监督学习&#xff0c;监督学习指的是训练样本包…