【数据结构】实现栈和队列
目录
- 一、栈
- 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;
}
感谢观看~
相关文章:

【数据结构】实现栈和队列
目录 一、栈1.栈的概念及结构(1)栈的概念(2)栈的结构 2.栈的实现(1)类型和函数的声明(2)初始化栈(3)销毁(4)入栈(5&#x…...

APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG
编辑:ll APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG 型号:APT60DQ20BG 品牌:ASEMI 封装:TO-3P 恢复时间:>50ns 正向电流:60A 反向耐压:200V 芯片个数:2 引脚数…...
[Android Framework] 系统 ANR 问题排查实践小结
文章目录 背景卡顿的定义:卡顿分类:卡顿原因汇总ANR 出现的原理应用层导致ANR系统导致ANR日志抓取traces.txt 是如何生成的分析思路与验证相关日志分析data/anr/traces.txt其他分析思路如何分析生成的 trace.html 文件呢?最后解决参考:背景 本文记录了工作中遇到的Andorid …...

【Unity】Text文本组件的一些操作
Unity的Text组件的几种常见的操作方法 Text组件是Unity中用于在UI界面上显示文本的组件。它包含了一些常见的属性和方法,可以用来控制文本的内容、外观和交互。以下是一些常见的Text组件的操作: 设置文本内容:通过直接在Unity编辑器中的Text…...

如何通过tomcat下载映射下载文件
1.1找到tomcat服务器中server.xml文件 !--doBase是静态资源路径位置, path作用相当于设置的key, doBase作用相当于value --> <Context path"/download" docBase"E:\testBackData"></Context>1.2 找到tomcat服务器中web.xml文…...

Redis的8种数据结构和应用场景介绍,面试题答案
面试原题:你用过Redis哪些数据结构?(网易一面 2023)(面试题来自牛客网) 参考答案 后面有 详细答案解析,帮助更快记忆~ 参考答案共652字符,阅读约需1分8秒;全文共8694字符,阅读约需…...

Log4Qt日志框架(1)- 引入到QT中
Log4Qt日志框架(1)- 引入到QT中 1 下载源码2 简介3 加入到自己的项目中3.1 使用库文件3.2 引入源文件 4 说明 1 下载源码 github:https://github.com/MEONMedical/Log4Qt 官方(版本较老):https://sourceforge.net/projects/log4q…...

【算法刷题之哈希表篇(1)】
目录 1.哈希表基础理论2.leetcode-242. 有效的字母异位词(1)方法一:排序(2)方法二:哈希表 3.leetcode-349. 两个数组的交集(1)方法一:哈希表(2)方…...

uni-app 打包生成签名Sha1
Android平台打包发布apk应用,需要使用数字证书(.keystore文件)进行签名,用于表明开发者身份。 可以使用JRE环境中的keytool命令生成。以下是windows平台生成证书的方法: 安装JRE环境(推荐使用JRE8环境&am…...
【Django】Django创建一个文件下载服务
当使用Django创建一个下载服务时,您可以设置一个视图来处理文件下载请求,并根据您的需求提供文件下载链接。以下是一个简单的示例,演示如何在Django中实现基本的文件下载服务: 创建Django项目和应用: 首先,…...

Navicat for Mysql 显示 emoji 表情符号乱码问题 — 其它乱码情况都可参考
系统环境: 操作系统:MAC OS 10.11.6 MySQL:Server version: 5.6.21 MySQL Community Server (GPL) Navicat for MySQL: version 9.3.1 - standard 1、问题发现 在客户端执行用户注册,用户名包括 emoji 表情符号,注册完…...

《数字图像处理-OpenCV/Python》连载(2)目录
《数字图像处理-OpenCV/Python》连载(2)目录 本书京东优惠购书链接:https://item.jd.com/14098452.html 本书CSDN独家连载专栏:https://blog.csdn.net/youcans/category_12418787.html 第一部分 OpenCV-Python的基本操作 第1章 …...
Go学习-Day4
文章目录 Go学习-Day4函数值传递,引用传递常用的函数 异常处理数组Slice切片 Go学习-Day4 个人博客:CSDN博客 函数 值传递,引用传递 值传递直接拷贝值,一般是基本数据类型,数组,结构体也是引用传递传递…...
将el-dialog封装成函数调用
1、 使用Vue实例化方法 // MyDialog.js import Vue from vue export const openFormDialog function ({ props {}, events {} }) {const vm new Vue({data () {return {form: {}}},render () {return (<el-dialogvisible{true}{...{ props }}{...{ on: events }}onClos…...

Windows10批处理命令行设置环境变量笔记,无需重新安装python与chrome
近期,工作中经常安装、部署python生产、开发环境,比较麻烦,也没有心情去优化。突然,我的电脑崩溃了,在重新安装电脑的过程中,保留了原来的安装软件(有的没有放在系统盘中)࿰…...
统计学补充概念07-比较树
概念 在层次聚类中,聚类结果可以以树状结构表示,通常称为树状图(Dendrogram)。树状图展示了数据点如何被合并或分裂以形成聚类的层次结构。通过观察树状图,可以更直观地理解数据点之间的相似性和关系。 在比较树状图…...
设计原则 --《设计模式之美》总结篇
本文是阅读《设计模式之美》的总结和心得,跳过了书中对面试和工作用处不大或不多的知识点,总结总共分为三章,分别是面对对象编程范式、设计原则和设计模式。 设计模式是代码设计时的一些经验总结。相比于设计模式,设计原则更抽象。…...

Day16-蜗牛影城后端开发
蜗牛影城后端开发 一 多表关联查询 电影集合movie的type(类别)字段关联到电影类别movieType表的_id(主键) 二 蜗牛影城后端开发 1 数据的导入导出 2 用户模块 UserModel.js //导入mongoose,并解构出Schema(类)和model(对象) const {Schema,model} =...

axios / fetch 实现 stream 流式请求
axios 是一个支持node端和浏览器端的易用、简洁且高效的http库。本文主要介绍 axios 如何实现 stream 流式请求,注意这里需要区分 node 环境和浏览器环境。 一、node端 代码演示: const axios require(axios);axios({method: get,url: http://tiven.c…...

Pytorch学习:torchvison.transforms常用包(ToTensor、Resize、Compose和RandomCrop)
torchvision.transforms常用包 1. torchvision.transforms.ToTensor2. torchvision.transforms.Resize3. torchvision.transforms.Compose4. torchvision.transforms.Normalize5. torchvision.transforms.RandomCrop 1. torchvision.transforms.ToTensor 将PIL Image或ndarray…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...