3.栈和队列（汇总版）

目录

1.栈（一端插和删）

2.队列（一端插另一段删）

2.1队列的概念及结构

2.2 队列的实现

队列的接口

1.初始化队列

2.销毁队列

3.插入元素

4.出队列（头删）

5.访问对头

6.访问队尾

7.判断队列是否为空

8.查看队列的元素个数

Queue整体代码：

Queue.h

Queue.c

test.c 

1.栈（一端插和删）

1.1栈的概念及结构

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

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

【注意：】因为不知道什么时候出栈，所以顺序也是多变的

具体实现，可以看一下下面这个图片的演示 

关键的元素有

接下来就是我们的增删查改，通过接口来实现啦

主体：

// 静态
//typedef int STDataType;
// #define N 10
// typedef struct Stack
// {
//  STDataType _a[N];
//  int _top; // 栈顶
// }Stack;
//更多用的是下面的动态
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;
typedef struct stack
{STDataType* a;//栈底int top;  //栈顶int capacity; //容量
}ST;//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//入栈（压栈）
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* ps);

点拨： 

//入栈
ps->a[ps->top] = x;
ps->top++;
//出栈
ps->top--;
//获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];//栈顶元素其实就是top前一位//这里注意栈为空时不能获取到元素
}

有一个小细节：栈顶初始化的选择会影响到栈，所以还是要通过接口来实现，如下

栈的灵魂就在于top，top++，top--,更多的还是在做题中去理解吧

2.队列（一端插另一段删）

2.1队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

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

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

2.2 队列的实现

创建结构体QueueNode这个结构体是创建节点的，节点由数据和指向下一个节点的指针构成的

第二个结构体是创建指向节点的两个指针，对头指针head和队尾指针tail

typedef int QueueDataType;typedef struct QueueNode
{struct QueueNode* next;QueueDataType data;}QNode;typedef struct Queue
{QNode* head;QNode* tail;}Queue;

队列的接口

void QueueInit(Queue* pq);   //初始化队列
void QueueDestory(Queue* pq);    //销毁队列void QueuePush(Queue* pq, QueueDataType x); //插入元素
void QueuePop(Queue* pq);   //出队列QueueDataType QueueFront(Queue* pq);  //查看队头元素
QueueDataType QueueBack(Queue* pq);   //查看队尾元素bool QueueEmpty(Queue* pq);  //检查队列是否为空
int QueueSize(Queue* pq);    //查看队列的长度

1.初始化队列

void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;}

2.销毁队列

当队列不为空时，用一个代替对头往后访问的指针cur ，当cur不为空时，用一个新的节点del 接收cur指向的节点。将del节点释放并置为空，cur在往后走完成对队列的遍历，最后将对头指针和队尾指针都置为空指针

void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;//再在其中定义Qnode引入while (cur){QNode* del = cur;//暂存销毁cur = cur->next;//保留好进行后移free(del);del = NULL;//del对每个节点进行释放，保留了cur后移}pq->head = pq->tail = NULL;}

3.插入元素

队列的性质插入元素只能是尾插，分为两种情况来看：1.队列为空 2.队列不为空

1. 队列为空时，先去malloc一个新节点，让对头和队尾都指向这个新节点

2. 当队列不为空时，malloc一个新节点，将新节点插入到tail指针的下一个位置，新的队尾指向新节点的下一个位置

void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 1.开辟一个新空间if (newnode == NULL)   {perror("malloc fail!!!");exit(-1);    //不成功直接退出程序}else{newnode->data = x;   //2. 将数据导入到新空间中newnode->next = NULL; //新节点指向空}//如果队列为空if (pq->head ==NULL&& pq->tail==NULL)//说明队列空{pq->head = pq->tail = newnode;  //都指向新节点}else{pq->tail->next = newnode;//3. 将tail的下一个定为newpq->tail = pq->tail->next;// tail后移}}

4.出队列（头删）

出队列也分为两种情况：1.队列有一个节点   2.队列有多个节点

void QueuePop(Queue* pq)//队列特性  头删
{assert(pq);assert(!QueueEmpty(pq));//一个节点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else//很多节点{QNode* del = pq->head;//del暂存然后销毁pq->head = pq->head->next;//保留起来好进行后移free(del);del = NULL;}}

5.访问对头

访问得有元素，需要判断队列是否为空

QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

6.访问队尾

访问得保证队列有元素，需要判断队列是否为空

QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty);return pq->tail->data;
}

7.判断队列是否为空

bool QueueEmpty(Queue* pq)
{return pq->head == NULL;   //空返回1  有元素0}

8.查看队列的元素个数

查看队列元素的个数得保证队列有元素，生成一个新的指针接受队头指针，代替头指针往后访问队列,返回n 的数值就是队列的元素个数。

int QueueSize(Queue* pq)
{assert(pq);assert(!QueueEmpty);int n = 0;QNode* cur = pq->head;while (cur){++n;cur = cur->next;}return n;
}

Queue整体代码：

Queue.h

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

Queue.c

#include "Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;}
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);del = NULL;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!!!");exit(-1);}else{newnode->data = x;newnode->next = NULL;}//如果队列为空if (pq->head ==NULL&& pq->tail==NULL)//说明队列空{pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}}void QueuePop(Queue* pq)//队列特性  头删
{assert(pq);assert(!QueueEmpty(pq));//一个节点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else//很多节点{QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}}QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty);return pq->tail->data;
}bool QueueEmpty(Queue* pq)
{return pq->head == NULL;   //空返回1  有元素0}
int QueueSize(Queue* pq)
{assert(pq);assert(!QueueEmpty);int n = 0;QNode* cur = pq->head;while (cur){++n;cur = cur->next;}return n;}

test.c 

#include"Queue.h"void testqueue()
{Queue q;QueueInit(&q);QueuePush(&q, 555);QueuePush(&q, 666);QueuePush(&q, 777);QueuePush(&q, 1);while (!QueueEmpty(&q)){printf("%d", QueueFront(&q));QueuePop(&q);printf("\n");}QueueDestory(&q);
}int main()
{testqueue();return 0;
}

//书摘：问题的出现不是让你止步不前，而是为你指明方向

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

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

相关文章

美特CRM upload.jsp 文件上传致RCE漏洞复现(CNVD-2023-06971)

美特CRM upload.jsp 文件上传致RCE漏洞复现(CNVD-2023-06971)

0x01 产品简介 MetaCRM是一款智能平台化CRM软件,通过提升企业管理和协同办公,全面提高企业管理水平和运营效率,帮助企业实现卓越管理。美特软件开创性地在CRM领域中引入用户级产品平台MetaCRM V5/V6，多年来一直在持续地为客户创造价值，大幅提升了用户需求满足度与使用的满意…
阅读更多...
workminer之dht通信部分

workminer之dht通信部分

workminer是通过SSH爆破传播的挖矿木马&#xff0c;感染后会释放xmrig挖矿程序利用主机的CPU挖取北方门罗币。该样本能够执行特定的指令&#xff0c;指令保存在一个配置文件config中&#xff0c;config文件类似于xml文件&#xff0c;里面有要执行的指令和参数&#xff0c;样本中…
阅读更多...
Three.js纹理贴图

Three.js纹理贴图

偏移 旋转 重复 纹理显示的清晰度 <template><div id"webgl"></div> </template><script setup> import * as THREE from three; import { OrbitControls } from three/addons/controls/OrbitControls.js;const scene new THREE…
阅读更多...
数据库SQL语言实战（七）

数据库SQL语言实战（七）

前言 这次的有一点点难~~~~~我也写了好久 练习题 题目一 在学生表pub.student中统计名字&#xff08;姓名的第一位是姓氏&#xff0c;其余为名字&#xff0c;不考虑复姓&#xff09;的使用的频率&#xff0c;将统计结果放入表test5_01中 create table test5_01(First_name…
阅读更多...
【notes2】并发，IO，内存

【notes2】并发，IO，内存

文章目录 1.线程/协程/异步&#xff1a;并发对应硬件资源是cpu&#xff0c;线程是操作系统如何利用cpu资源的一种抽象2.并发&#xff1a;cpu&#xff0c;线程2.1 可见性&#xff1a;volatile2.2 原子性&#xff08;读写原子&#xff09;&#xff1a;AtomicInteger/synchronized…
阅读更多...
SparkSql介绍

SparkSql介绍

概述 SparkSQL&#xff0c;顾名思义&#xff0c;就是Spark生态体系中的构建在SparkCore基础之上的一个基于SQL的计算模块。SparkSQL的前身不叫SparkSQL&#xff0c;而叫Shark&#xff0c;最开始的时候底层代码优化&#xff0c;sql的解析、执行引擎等等完全基于Hive&#xff0c…
阅读更多...
React中的高阶组件的封装,高阶函数,HOC的含义及用法:

React中的高阶组件的封装,高阶函数,HOC的含义及用法:

含义及作用: 高阶函数代码案例: 调用高阶组价:
阅读更多...
软件测试与管理：黑盒测试-等价类划分法和 边界值分析法

软件测试与管理：黑盒测试-等价类划分法和 边界值分析法

知识思维导图&#xff1a; 例题1&#xff1a;日期检查功能的等价类划分 设有一个档案管理系统&#xff0c;要求用户输入以年月表示的日期。假设日期限定在1990年1月~2049年12月&#xff0c;并规定日期由6位数字字符组成&#xff0c;前4位表示年&#xff0c;后2位表示月。现用等…
阅读更多...
计算机组成原理实验一 寄存器实验

计算机组成原理实验一 寄存器实验

目录 实验目的和要求 实验环境 实验内容与过程 连接线表 将8AH写入A寄存器 将6cH写入W寄存器 实验结果与分析 实验箱主要部件 将55H写入A寄存器 将66H写入W寄存器 按住STEP脉冲键实验现象? (实验箱中有什么变化) 放开STEP 键实验现象? (实验箱中有什么变化) 数据…
阅读更多...
proxy代理面试题

proxy代理面试题

1、动态属性值 const r1add[1][2][3]4//输出10 const r2add[10][20]30//输出60 const r3add[100][200][300]400//输出1000柯里化&#xff0c;有参考下文 https://blog.csdn.net/p1967914901/article/details/127621032 add 是对象&#xff0c;通过链式传入属性求和返回结果&a…
阅读更多...
蛋白质/聚合物防污的机器学习(材料基因组计划)

蛋白质/聚合物防污的机器学习(材料基因组计划)

前言&#xff1a;对于采用机器学习去研究聚合物的防污性能&#xff0c;以及或者其他性质。目前根据我的了解我认为最困难的点有三条&#xff1a; 其一&#xff1a;数据&#xff0c;对于将要训练的数据必须要有三点要求&#xff0c;1.数据要多&#xff0c;也就是大数据&#xff…
阅读更多...
毕设：邮件分发系统

毕设：邮件分发系统

文章目录 前言一、登录1.邮箱登录2.账号登录 二、注册三、首页四、写邮件五、收邮件六、草稿箱七、垃圾箱八、已发送九、通讯录十、用户管理十一、邮件管理十二、登录日志总结 前言 分享一下邮件分发系统 一、登录 1.邮箱登录 2.账号登录 二、注册 三、首页 首页有邮件信息&…
阅读更多...
【蓝桥杯备赛国赛】5-5

【蓝桥杯备赛国赛】5-5

文章目录 求阶乘双子数 求阶乘 求阶乘 分析k的范围&#xff0c;10的18次方。这个数字很大 想要末尾有0的存在必须要2和5&#xff0c;但是通过分析2的数目应该是远远多于5的&#xff0c;所以只要5的数目够多即可。所以for循环的层次也是10的九次方以上&#xff0c;必然会超时&…
阅读更多...
光端机(2)——光纤通信学习笔记九

光端机(2)——光纤通信学习笔记九

学习笔记里面只关注基本原理和概念&#xff0c;复杂的公式和推导都没有涉及 光端机 光发射机 作用&#xff1a;实现电光转换。将来自电端机的电信号对光源发出的光波进行调制&#xff0c;然后将调制好的光信号耦合到光线中传输。 基本性能要求 1.合适的发光波长&#xff08;光…
阅读更多...
GateWay检查接口耗时

GateWay检查接口耗时

添加gateway依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifactId> </dependency>创建一个LogTimeGateWayFilterFactory类&#xff0c;可以不是这个名字但是后面必须是x…
阅读更多...
webstorm 常用插件

webstorm 常用插件

安装插件步骤&#xff1a; 打开软件&#xff0c;文件 -- 设置-- 插件 -- 输入插件名称 -- 安装 代码截图: code screenShots 先选中代码&#xff0c;按 ctrl shift alt a&#xff0c;就可截取选中的代码颜色注释: comments highlighter 对注释的文字改变颜色高亮成对符号: h…
阅读更多...
设计模式Java实现-建造者模式

设计模式Java实现-建造者模式

楔子 小七在2019年的时候&#xff0c;就想写一个关于设计模式的专栏&#xff0c;但是最终却半途而废了。粗略一想&#xff0c;如果做完一件事要100分钟&#xff0c;小七用3分钟热情做的事&#xff0c;最少也能完成10件事情了。所以这一次&#xff0c;一定要把他做完&#xff0…
阅读更多...
【前端】HTML实现个人简历信息填写页面

【前端】HTML实现个人简历信息填写页面

文章目录 前言一、综合案例&#xff1a;个人简历信息填写页面 前言 这篇博客仅仅是对HTML的基本结构进行了一些说明&#xff0c;关于HTML的更多讲解以及CSS、Javascript部分的讲解可以关注一下下面的专栏&#xff0c;会持续更新的。 链接&#xff1a; Web前端学习专栏 下面我对…
阅读更多...
【毕业设计】基于SSM的运动用品商城的设计与实现

【毕业设计】基于SSM的运动用品商城的设计与实现

1.项目介绍 在这个日益数字化和信息化的时代&#xff0c;随着人们购物习惯的转变&#xff0c;传统的实体商店已经无法满足人们日益增长的在线购物需求。因此&#xff0c;基于SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架的运动用品商城项目应运而生&#xff0…
阅读更多...
LearnOpenGL（七）之摄像机

LearnOpenGL（七）之摄像机

一、摄像机/观察空间 当我们讨论摄像机/观察空间(Camera/View Space)的时候&#xff0c;是在讨论以摄像机&#xff08;人&#xff09;的视角作为场景原点时场景中所有的顶点坐标&#xff1a;观察矩阵把所有的世界坐标变换为相对于摄像机位置与方向的观察坐标。要定义一个摄像机…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023