【数据结构】实现栈和队列

目录

  • 一、栈
    • 1.栈的概念及结构
      • （1）栈的概念
      • （2）栈的结构
    • 2.栈的实现
      • （1）类型和函数的声明
      • （2）初始化栈
      • （3）销毁
      • （4）入栈
      • （5）出栈
      • （6）检查是否为空
      • （7）获取栈的元素个数
      • （8）获取栈顶元素
  • 二、栈的全部代码
    • 1.Stack.h
    • 2Stack.c
    • 3.Test.c
  • 三、队列
    • 1.队列的概念及结构
      • （1）队列的概念
      • （2）队列的结构
    • 2.队列的实现
      • （1）类型和函数的声明
      • （2）初始化队列
      • （3）销毁
      • （4）入队
      • （5）出队
      • （6）获取头部元素
      • （7）获取队尾元素
      • （8）获取元素个数
      • （9）检查是否为空
  • 四、队列的全部代码
    • 1.Queue.h
    • 2.Queue.c
    • 3.Test.c

一、栈

1.栈的概念及结构

（1）栈的概念

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

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

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

（2）栈的结构

在这里插入图片描述

2.栈的实现

（1）类型和函数的声明

栈的结构与顺序表相同，也是用数组。因为栈的特点是出栈、入栈在同一位置，所以用数组尾插更方便。

typedef int STDataType;
typedef struct Stack
{STDataType* data;int top;int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//检查是否为空
bool STEmpty(ST* ps);
//获取栈的元素个数
int STSize(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);

（2）初始化栈

void STInit(ST* ps)
{assert(ps);ps->data = NULL;ps->capacity = 0;ps->top = 0;
}

（3）销毁

void STDestroy(ST* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->capacity = 0;ps->top = 0;
}

（4）入栈

void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}ps->data[ps->top] = x;ps->top++;
}

（5）出栈

void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}

（6）检查是否为空

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

（7）获取栈的元素个数

int STSize(ST* ps)
{assert(ps);return ps->top;
}

（8）获取栈顶元素

STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->data[ps->top - 1];
}

二、栈的全部代码

1.Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{STDataType* data;int top;int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//检查是否为空
bool STEmpty(ST* ps);
//获取栈的元素个数
int STSize(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);

2Stack.c

#include "Stack.h"
//初始化
void STInit(ST* ps)
{assert(ps);ps->data = NULL;ps->capacity = 0;ps->top = 0;
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->data = tmp;ps->capacity = newcapacity;}ps->data[ps->top] = x;ps->top++;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}
//检查是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//获取栈的元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->data[ps->top - 1];
}

3.Test.c

#include "Stack.h"
void test()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);
}
int main()
{test();return 0;
}

在这里插入图片描述

三、队列

1.队列的概念及结构

（1）队列的概念

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

（2）队列的结构

在这里插入图片描述

2.队列的实现

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

（1）类型和函数的声明

队列除了节点的结构体以外，还要再创建一个结构体，方便找到尾指针。

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
//初始化
void QueInit(Que* pq);
//销毁
void QueDestroy(Que* pq);
//入队
void QuePush(Que* pq, QDataType x);
//出队
void QuePop(Que* pq);
//获取头部元素
QDataType QueFront(Que* pq);
//获取队尾元素
QDataType QueBack(Que* pq);
//获取元素个数
int QueSize(Que* pq);
//检查是否为空
bool QueEmpty(Que* pq);

（2）初始化队列

void QueInit(Que* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}

（3）销毁

void QueDestroy(Que* 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;
}

（4）入队

入队相当于尾插，因为只有一个入口插入节点，所以直接在这个函数创建一个新节点。分两种情况：刚开始没有节点尾插、已有节点再尾插。

void QuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

（5）出队

出队相当于头删。如果没有节点，就不能再删了，所以要断言检查是否为空。这里的头删也要分两种情况：只有一个节点、一个以上的节点。

void QuePop(Que* pq)
{assert(pq);assert(!QueEmpty(pq));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--;
}

（6）获取头部元素

QDataType QueFront(Que* pq)
{assert(pq);assert(!QueEmpty(pq));return pq->head->data;
}

（7）获取队尾元素

QDataType QueBack(Que* pq)
{assert(pq);assert(!QueEmpty(pq));return pq->tail->data;
}

（8）获取元素个数

int QueSize(Que* pq)
{assert(pq);return pq->size;
}

（9）检查是否为空

bool QueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}

四、队列的全部代码

1.Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
//初始化
void QueInit(Que* pq);
//销毁
void QueDestroy(Que* pq);
//入队
void QuePush(Que* pq, QDataType x);
//出队
void QuePop(Que* pq);
//获取头部元素
QDataType QueFront(Que* pq);
//获取队尾元素
QDataType QueBack(Que* pq);
//获取元素个数
int QueSize(Que* pq);
//检查是否为空
bool QueEmpty(Que* pq);

2.Queue.c

#include "Queue.h"
//初始化
void QueInit(Que* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
//销毁
void QueDestroy(Que* 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 QuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
//出队
void QuePop(Que* pq)
{assert(pq);assert(!QueEmpty(pq));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--;
}
//获取头部元素
QDataType QueFront(Que* pq)
{assert(pq);assert(!QueEmpty(pq));return pq->head->data;
}
//获取队尾元素
QDataType QueBack(Que* pq)
{assert(pq);assert(!QueEmpty(pq));return pq->tail->data;
}
//获取元素个数
int QueSize(Que* pq)
{assert(pq);return pq->size;
}
//检查是否为空
bool QueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}

3.Test.c

#include "Queue.h"
void test()
{Que q;QueInit(&q);QuePush(&q, 1);QuePush(&q, 2);QuePush(&q, 3);QuePush(&q, 4);QuePush(&q, 5);while (!QueEmpty(&q)){printf("%d ", QueFront(&q));QuePop(&q);}printf("\n");QueDestroy(&q);
}
int main()
{test();return 0;
}

在这里插入图片描述
在这里插入图片描述
感谢观看~

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

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

相关文章

连接未来 驱动创新｜腾讯云 CODING DevOps 主题沙龙诚邀您的参与

连接未来 驱动创新｜腾讯云 CODING DevOps 主题沙龙诚邀您的参与

点击链接了解详情 随着企业数字化转型步入深水区&#xff0c;DevOps 作为数字化转型关键的内建阶段&#xff0c;其应用和实施已经成为企业提升研发效率&#xff0c;实现快速迭代和持续交付的重要手段。然而如何有效地实施 DevOps&#xff0c;如何利用 DevOps 推动业务发展和创新…
阅读更多...
CSS加载失败的6个原因

CSS加载失败的6个原因

有很多刚刚接触 CSS 的新手有时会遇到 CSS 加载失败这个问题&#xff0c;但测试时&#xff0c;网页上没有显示该样式的问题&#xff0c;这就说明 CSS 加载失败了。出现这种状况一般是因为的 CSS 路径书写错&#xff0c;或者是在浏览器中禁止掉了 CSS 的加载&#xff0c;可以重新…
阅读更多...
vue3 路由缓存问题

vue3 路由缓存问题

目录 解决问题的思路&#xff1a; 解决问题的方案&#xff1a; 1、给roter-view添加key&#xff08;破坏复用机制&#xff0c;强制销毁重建&#xff09; 2、使用beforeRouteUpdate导航钩子 3、使用watch监听路由 vue3路由缓存&#xff1a;当用户从/users/johnny导航到/use…
阅读更多...
[网络架构]Self-organized operational neural networks (SelfONN)

[网络架构]Self-organized operational neural networks (SelfONN)

Self-organized operational neural networks (SelfONN 背景CNNONNSelfONNCNN, ONN&#xff0c; SelfONN对比SelfONN与CNN的关系总结References 背景 本节要分享的是SelfONN, SelfONN可以看作是ONN的优化/升级&#xff0c; 而ONN可以看作是更一般化的CNN&#xff0c; 克服了CN…
阅读更多...
自己实现 SpringMVC 底层机制 系列之-实现任务阶段 6-完成控制器方法获取参数-@RequestParam

自己实现 SpringMVC 底层机制 系列之-实现任务阶段 6-完成控制器方法获取参数-@RequestParam

&#x1f600;前言 自己实现 SpringMVC 底层机制 系列之-实现任务阶段 6-完成控制器方法获取参数-RequestParam &#x1f3e0;个人主页&#xff1a;尘觉主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是尘觉&#xff0c;希望我的文章可以帮助到大家&#xff0c…
阅读更多...
Feign:使用接口方式调用服务

Feign:使用接口方式调用服务

创建一个新的消费者模块并导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://ma…
阅读更多...
Linux学习之firewallD

Linux学习之firewallD

systemctl status firewalld.service查看一下firewalld服务的状态&#xff0c;发现状态是inactive (dead)。 systemctl start firewalld.service启动firewalld&#xff0c;systemctl status firewalld.service查看一下firewalld服务的状态&#xff0c;发现状态是active (runni…
阅读更多...
无涯教程-PHP - preg_grep()函数

无涯教程-PHP - preg_grep()函数

preg_grep() - 语法 array preg_grep ( string $pattern, array $input [, int $flags] ); 返回由与给定模式匹配的输入数组元素组成的数组。 如果将flag设置为PREG_GREP_INVERT&#xff0c;则此函数返回输入数组中与给定模式不匹配的元素。 preg_grep() - 返回值 返回使用…
阅读更多...
pdf转word最简单方法~

pdf转word最简单方法~

pdf转word最简单方法&#xff01;pdf转word最简单方法我们都知道&#xff0c;PDF文件是一种只读文件格式&#xff0c;无法按照需求对PDF文件进行更改与编辑&#xff0c;从而影响到了PDF文件的使用。所以&#xff0c;我们需要将PDF文件转换为word文档&#xff0c;以此来保证文件…
阅读更多...
LLM 生成式配置的推理参数温度 top k tokens等 Generative configuration inference parameters

LLM 生成式配置的推理参数温度 top k tokens等 Generative configuration inference parameters

在这个视频中&#xff0c;你将了解一些方法和相关的配置参数&#xff0c;这些参数可以用来影响模型在下一个词生成时的最终决策方式。如果你在Hugging Face网站或AWS的游乐场中使用过LLMs&#xff0c;你可能已经看到了这些控制选项&#xff0c;用来调整LLM的行为。每个模型都暴…
阅读更多...
【数据库】表操作 习题总结

【数据库】表操作 习题总结

目录 关系建表 数据库sql的执行顺序 内外连接的写法 1.设计一张商品表 2.设计一张老师表 3.设计一张图书表 4.查询练习 5.查询练习 6.设计一个考勤系统 7.设计一个学校宿舍管理系统 8.设计一个车辆违章系统 9.设计一个学校食堂管理系统 10.有一张员工表emp&#xf…
阅读更多...
AWS SDK 3.x for .NET Framework 4.0 可行性测试

AWS SDK 3.x for .NET Framework 4.0 可行性测试

前言 为了应对日益增长的网络安全挑战, 越来越多的互联网厂商已经陆续开始或者已经彻底停止了对 SSL 3 / TLS 1.0 / TLS1.1 等上古加密算法的支持. 而对于一些同样拥有悠久历史的和 AWS 服务相关联的应用程序, 是否可以通过仅更新 SDK 版本的方式来适应新的环境. 本文将以 Win…
阅读更多...
前端处理图片文件的方法

前端处理图片文件的方法

在项目开发过程中&#xff0c;有一个需求&#xff0c;需要前端对上传的图片进行处理&#xff0c;以字符串的形式传给后端&#xff0c;实现效果如下&#xff1a; 1.上传图片的组件 在该项目中&#xff0c;使用了element plus组件库 <el-uploadv-model:file-list"fileL…
阅读更多...
2023年目标检测研究进展

2023年目标检测研究进展

综述 首先关于写这个笔记&#xff0c;我个人思考了很久关于以下几点。1&#xff1a;19年开始从做OCR用到图像和文本这种多模态联合处理的后&#xff0c;也就有意识的开始关注自然语言处理&#xff0c;这样的结果导致可能停留在前期图像上的学习和实践&#xff0c;停滞的研究如…
阅读更多...
17万字数字化医院信息化建设大数据平台建设方案WORD

17万字数字化医院信息化建设大数据平台建设方案WORD

导读&#xff1a;原文《17万字数字化医院信息化建设大数据平台建设方案WORD》&#xff08;获取来源见文尾&#xff09;&#xff0c;本文精选其中精华及架构部分&#xff0c;逻辑清晰、内容完整&#xff0c;为快速形成售前方案提供参考。 目录 第1章 医院信息化概述 1.1 国内…
阅读更多...
【开发】视频云存储EasyCVR视频汇聚平台AI智能算法定制

【开发】视频云存储EasyCVR视频汇聚平台AI智能算法定制

安防视频集中存储EasyCVR视频汇聚平台&#xff0c;可支持海量视频的轻量化接入与汇聚管理。平台能提供视频存储磁盘阵列、视频监控直播、视频轮播、视频录像、云存储、回放与检索、智能告警、服务器集群、语音对讲、云台控制、电子地图、平台级联、H.265自动转码等功能。为了便…
阅读更多...
2023国赛数学建模思路 - 案例：最短时间生产计划安排

2023国赛数学建模思路 - 案例：最短时间生产计划安排

文章目录 0 赛题思路1 模型描述2 实例2.1 问题描述2.2 数学模型2.2.1 模型流程2.2.2 符号约定2.2.3 求解模型 2.3 相关代码2.4 模型求解结果 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 最短时…
阅读更多...
Log4j反序列化命令执行漏洞(CVE-2017-5645)Apache Log4j2 lookup JNDI 注入漏洞（CVE-2021-44228）

Log4j反序列化命令执行漏洞(CVE-2017-5645)Apache Log4j2 lookup JNDI 注入漏洞（CVE-2021-44228）

一.Log4j反序列化命令执行漏洞(CVE-2017-5645&#xff09; Apache Log4j是一个用于Java的日志记录库&#xff0c;其支持启动远程日志服务器。Apache Log4j 2.8.2之前的2.x版本中存在安全漏洞。攻击者可利用该漏洞执行任意代码 环境&#xff1a;vulhub 工具下载地址&#xff1…
阅读更多...
Oracle Database12c数据库官网下载和安装教程

Oracle Database12c数据库官网下载和安装教程

文章目录 下载安装Oracle自带的客户端工具使用 下载 进入oracle官网 点击下载连接之后右上角会有一个下载 我们只需要数据库本体就够了 运行这个下载器 等待下好之后即可 出现 Complete 之后代表下载成功&#xff0c;然后我们解压即可 安装 双击 双击setup.exe 根据…
阅读更多...
opencv进阶09-视频处理cv2.VideoCapture示例（打开本机电脑摄像头）

opencv进阶09-视频处理cv2.VideoCapture示例（打开本机电脑摄像头）

视频信号&#xff08;以下简称为视频&#xff09;是非常重要的视觉信息来源&#xff0c;它是视觉处理过程中经常要处理的一类信号。实际上&#xff0c;视频是由一系列图像构成的&#xff0c;这一系列图像被称为帧&#xff0c;帧是以固定的时间间隔从视频中获取的。获取&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发