栈和队列篇

目录

一、栈

1.栈的概念及结构

1.1栈的概念

1.2栈的结构示意图

2.栈的实现

2.1支持动态增长的栈的结构

2.2压栈(入栈)

2.3出栈

2.4支持动态增长的栈的代码实现

二、队列

1.队列的概念及结构

1.1队列的概念

1.2队列的结构示意图

2.队列的实现

2.1队列的结构

2.2队尾入队列

2.3队头出队列

2.4队列的代码实现

一、栈

1.栈的概念及结构

1.1栈的概念

        栈是一种特殊的线性表。栈只允许在固定的一端进行插入和删除数据的操作,栈的插入操作叫做压栈(进栈),栈的删除操作叫做出栈,进行数据插入和删除操作的一端叫做栈顶,另一端为栈底。栈中的元素遵循先进后出的原则。

1.2栈的结构示意图

2.栈的实现

        栈一般分为静态栈和支持动态增长的栈,静态栈由于栈的空间大小固定不具实用性,所以我们只针对支持动态增长的栈进行代码实现:

2.1支持动态增长的栈的结构

        栈的实现一般使用数组形式来实现,支持动态增长的栈即开辟一个动态数组a用来存储数据,当栈的容量满了之后方便扩容。

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;		// 栈顶int capacity;  // 容量 
}Stack;

2.2压栈(入栈)

        每次压栈首先检查栈的容量是否已满,再决定是否需要扩容,压栈的元素变为新的栈顶

// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 5 : (ps->capacity) * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc:");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = data;ps->top++;
}

2.3出栈

        出栈后新的栈顶变为出栈前的栈顶的前一个元素

// 出栈 
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}

2.4支持动态增长的栈的代码实现

#pragma once
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;		// 栈顶int capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = 0;//top指向栈顶的下一个位置,对top的操作需要是:先使用后++ps->capacity = 0;
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 5 : (ps->capacity) * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc:");return;}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = data;ps->top++;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

二、队列

1.队列的概念及结构

1.1队列的概念

        不同于栈的概念,队列只允许在其一端进行插入数据操作,在另一端进行删除数据操作。进行插入数据操作的一端是队尾,进行删除数据操作的一端是队头。队列是一种特殊的线性表,遵循先进先出的原则。

1.2队列的结构示意图

2.队列的实现

2.1队列的结构

        队列的实现一般使用链表的结构更优:

代码:

// 队列成员节点结构
typedef int QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;

简图:

2.2队尾入队列

代码:

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* NewNode = (QNode*)malloc(sizeof(QNode));if (NewNode == NULL){perror("malloc:");return;}NewNode->data = data;NewNode->next = NULL;if (q->size == 0){q->front = q->rear = NewNode;}else{q->rear->next = NewNode;q->rear = q->rear->next;}q->size++;
}

简图:

2.3队头出队列

代码:

// 队头出队列 
void QueuePop(Queue* q)
{assert(q);//assert(!QueueEmpty(q));if (q->front ==q->rear){if (q->front == NULL){return;}else{free(q->front);q->front = q->rear = NULL;}}else{QNode* Tmp = q->front;q->front = Tmp->next;free(Tmp);Tmp = NULL;}q->size--;
}

简图:

2.4队列的代码实现

#pragma once
#include<assert.h>
#include<stdlib.h>
#include<stdio.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)
{assert(q);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("malloc:");return;}NewNode->data = data;NewNode->next = NULL;if (q->size == 0){q->front = q->rear = NewNode;}else{q->rear->next = NewNode;q->rear = q->rear->next;}q->size++;
}// 队头出队列 
void QueuePop(Queue* q)
{assert(q);//assert(!QueueEmpty(q));if (q->front ==q->rear){if (q->front == NULL){return;}else{free(q->front);q->front = q->rear = NULL;}}else{QNode* Tmp = q->front;q->front = Tmp->next;free(Tmp);Tmp = NULL;}q->size--;
}// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->data;
}// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0 ? 1 : 0;
}// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);while(!QueueEmpty(q)){QueuePop(q);}
}

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

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

相关文章

安防监控/视频存储/视频汇聚平台EasyCVR接入海康Ehome车载设备出现收流超时的原因排查

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。视频汇聚平台既具…

uni-app之android项目云打包

1&#xff0c;项目根目录&#xff0c;找到mainfest.json&#xff0c;如果appid是空的&#xff0c;需要生成一个appid 2&#xff0c;点击重新获取appid&#xff0c;这个时候需要登录&#xff0c;那就输入账号密码登录下 3&#xff0c;登陆后可以看到获取appid成功 4&#xff0c;…

四轴飞行器的电池研究(MatlabSimulink仿真)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

【力扣每日一题】2023.8.31 一个图中连通三元组的最小度数

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一个无向图&#xff0c;要我们找出三个节点&#xff0c;这三个节点他们两两相连&#xff0c;这三个节点除了连接到对方的其他线…

Windows下Redis的安装

文章目录 一,Redis介绍二,Redis下载三,Redis安装-解压四,Redis配置五,Redis启动和关闭(通过terminal操作)六,Redis连接七,Redis使用 一,Redis介绍 远程字典服务,一个开源的,键值对形式的在线服务框架,值支持多数据结构,本文介绍windows下Redis的安装,配置相关,官网默认下载的是…

QT day1

作业&#xff1a; 编写一个类似图片的 #include "burger.h"burger::burger(QWidget *parent): QWidget(parent) {//设置初始尺寸this->resize(400,320);//设置尺寸最大值最小值this->setMaximumSize(400,320);this->setMinimumSize(400,320);//设置窗口标…

中国行政区域带坐标经纬度sql文件及地点获取经纬度方法

文章目录 前言一、如何获取某地的经纬度&#xff1f;1.1 搜索百度地图1.2 在下方找到地图开放平台1.3 下滑找到坐标拾取器1.4 使用 二、sql文件2.1 创建表2.2 插入数据 前言 当工作业务上需要涉及地图&#xff0c;给前端返回经纬度等场景&#xff0c;需要掌握区域经纬度的获取…

在iPhone 15发布之前,iPhone在智能手机出货量上占据主导地位,这对安卓来说是个坏消息

可以说这是一记重拳&#xff0c;但似乎没有一个有价值的竞争者能与苹果今年迄今为止的智能手机出货量相媲美。 事实上&#xff0c;根据Omdia智能手机型号市场跟踪机构收集的数据&#xff0c;苹果的iPhone占据了前四名。位居榜首的是iPhone 14 Pro Max&#xff0c;2023年上半年…

C# Linq源码分析之Take(四)

概要 本文主要对Take的优化方法进行源码分析&#xff0c;分析Take在配合Select&#xff0c;Where等常用的Linq扩展方法使用时候&#xff0c;如何实现优化处理。 本文涉及到Select, Where和Take和三个方法的源码分析&#xff0c;其中Select, Where, Take更详尽的源码分析&…

iOS开发Swift-3-UI与按钮Button-摇骰子App

1.创建新项目Dice 2.图标 删去AppIcon&#xff0c;将解压后的AppIcon.appiconset文件拖入Assets包。 3.将素材点数1-6通过网页制作成2x&#xff0c;3x版本并拖入Asset。 4.设置对应的UI。 5.拖入Button组件并设置style。 6.Ctrl加拖拽将Button拖拽到ViewController里&#xff0…

WPF实战项目十三(API篇):备忘录功能api接口、优化待办事项api接口

1、新建MenoDto.cs /// <summary>/// 备忘录传输实体/// </summary>public class MemoDto : BaseDto{private string title;/// <summary>/// 标题/// </summary>public string Title{get { return title; }set { title value; OnPropertyChanged();…

Day5:react函数组件与类组件

「目标」: 持续输出&#xff01;每日分享关于web前端常见知识、面试题、性能优化、新技术等方面的内容。 「主要面向群体&#xff1a;」前端开发工程师&#xff08;初、中、高级&#xff09;、应届、转行、培训、自学等同学 Day4-今日话题 react「函数组件和类组件」的区别&…

ZLMediaKit 重建docker包

1.下载容器到本地服务器并运行 #此镜像为github持续集成自动编译推送&#xff0c;跟代码(master分支)保持最新状态 docker run -id -p 1935:1935 -p 8080:80 -p 8443:443 -p 8554:554 -p 10000:10000 -p 10000:10000/udp -p 8000:8000/udp -p 9000:9000/udp zlmediakit/zlmedi…

好马配好鞍:Linux Kernel 4.12 正式发布

Linus Torvalds 在内核邮件列表上宣布释出 Linux 4.12&#xff0c;Linux 4.12 的主要特性包括&#xff1a; BFQ 和 Kyber block I/O 调度器&#xff0c;livepatch 改用混合一致性模型&#xff0c;信任的执行环境框架&#xff0c;epoll 加入 busy poll 支持等等&#xff0c;其它…

shell脚本中时间的编写规范20230902

背景&#xff1a;经常写shell&#xff0c;但是很多种时间格式规范真是记不住哈&#xff0c;&#x1f604;&#xff0c;索性记录一下 一、 获取-年 下面的这两种写法都成 year$(date "%Y") yeardate "%Y"echo -e "测试输出 年: ${year}"输出结…

unity 之参数类型之引用类型

文章目录 引用类型引用类型与值类型的差异 引用类型 在Unity中&#xff0c;引用类型是指那些在内存中存储对象引用的数据类型。以下是在Unity中常见的引用类型的介绍&#xff1a; 节点&#xff08;GameObject&#xff09;&#xff1a; 在Unity中&#xff0c;游戏对象&#xff…

DevEco Studio 配置

首先,打开deveco studio 进入首页 …我知道你们想说什么,我也想说 汉化配置 没办法,老样子,先汉化吧,毕竟母语看起来舒服 首先,点击软件左下角的configure,在配置菜单里选择plugins 进入到插件页面, 输入chinese,找到汉化插件,(有一说一写到这我心里真是很不舒服) 然后点击o…

Nmap 7.94 发布:新功能!

Nmap 的最新版本 7.94 在其 26 岁生日之际发布。 最重要的升级是在所有平台上将 Zenmap 和 Ndiff 从 Python 2 迁移到 Python 3。 这个新版本的 Nmap 7.94 进行了升级&#xff0c;进行了多项改进&#xff0c;修复了一些关键错误&#xff0c;并添加了新的 Npcap、操作系统指纹…

浅析Linux系统I/O模型

文章目录 概述阻塞式I/O模型非阻塞式I/O模型I/O多路复用模型信号驱动式I/O模型异步I/O模型相关参考 概述 在操作系统中&#xff0c;I/O类操作是相对慢速的&#xff0c;应用发起一个I/O操作&#xff0c;需要等待I/O资源就绪后&#xff0c;才能继续后面的处理。这种简单的请求-响…

【八股】2023秋招八股复习笔记5(计算机网络-CN)

文章目录 八股目录目录1、应用层 & HTTP一些http题HTTPS 加密原理&#xff08;问过&#xff09;HTTP/1.1 新特性HTTP/2.0 与 RPC&#xff08;问过&#xff09;GET 和 POST 比较 2、传输层 & TCPTCP三次握手 & 四次挥手&#xff08;问过&#xff09;为什么每次TCP 连…