当前位置: 首页 > news >正文

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

目录

  • 一、栈
    • 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.栈的概念及结构&#xff08;1&#xff09;栈的概念&#xff08;2&#xff09;栈的结构 2.栈的实现&#xff08;1&#xff09;类型和函数的声明&#xff08;2&#xff09;初始化栈&#xff08;3&#xff09;销毁&#xff08;4&#xff09;入栈&#xff08;5&#x…...

APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG

编辑&#xff1a;ll APT60DQ20BG-ASEMI新能源功率器件APT60DQ20BG 型号&#xff1a;APT60DQ20BG 品牌&#xff1a;ASEMI 封装&#xff1a;TO-3P 恢复时间&#xff1a;&#xff1e;50ns 正向电流&#xff1a;60A 反向耐压&#xff1a;200V 芯片个数&#xff1a;2 引脚数…...

[Android Framework] 系统 ANR 问题排查实践小结

文章目录 背景卡顿的定义:卡顿分类:卡顿原因汇总ANR 出现的原理应用层导致ANR系统导致ANR日志抓取traces.txt 是如何生成的分析思路与验证相关日志分析data/anr/traces.txt其他分析思路如何分析生成的 trace.html 文件呢?最后解决参考:背景 本文记录了工作中遇到的Andorid …...

【Unity】Text文本组件的一些操作

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

如何通过tomcat下载映射下载文件

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

Redis的8种数据结构和应用场景介绍,面试题答案

面试原题&#xff1a;你用过Redis哪些数据结构&#xff1f;&#xff08;网易一面 2023&#xff09;(面试题来自牛客网) 参考答案 后面有 详细答案解析&#xff0c;帮助更快记忆~ 参考答案共652字符&#xff0c;阅读约需1分8秒&#xff1b;全文共8694字符&#xff0c;阅读约需…...

Log4Qt日志框架(1)- 引入到QT中

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

【算法刷题之哈希表篇(1)】

目录 1.哈希表基础理论2.leetcode-242. 有效的字母异位词&#xff08;1&#xff09;方法一&#xff1a;排序&#xff08;2&#xff09;方法二&#xff1a;哈希表 3.leetcode-349. 两个数组的交集&#xff08;1&#xff09;方法一&#xff1a;哈希表&#xff08;2&#xff09;方…...

uni-app 打包生成签名Sha1

Android平台打包发布apk应用&#xff0c;需要使用数字证书&#xff08;.keystore文件&#xff09;进行签名&#xff0c;用于表明开发者身份。 可以使用JRE环境中的keytool命令生成。以下是windows平台生成证书的方法&#xff1a; 安装JRE环境&#xff08;推荐使用JRE8环境&am…...

【Django】Django创建一个文件下载服务

当使用Django创建一个下载服务时&#xff0c;您可以设置一个视图来处理文件下载请求&#xff0c;并根据您的需求提供文件下载链接。以下是一个简单的示例&#xff0c;演示如何在Django中实现基本的文件下载服务&#xff1a; 创建Django项目和应用&#xff1a; 首先&#xff0c…...

Navicat for Mysql 显示 emoji 表情符号乱码问题 — 其它乱码情况都可参考

系统环境&#xff1a; 操作系统&#xff1a;MAC OS 10.11.6 MySQL&#xff1a;Server version: 5.6.21 MySQL Community Server (GPL) Navicat for MySQL: version 9.3.1 - standard 1、问题发现 在客户端执行用户注册&#xff0c;用户名包括 emoji 表情符号&#xff0c;注册完…...

《数字图像处理-OpenCV/Python》连载(2)目录

《数字图像处理-OpenCV/Python》连载&#xff08;2&#xff09;目录 本书京东优惠购书链接&#xff1a;https://item.jd.com/14098452.html 本书CSDN独家连载专栏&#xff1a;https://blog.csdn.net/youcans/category_12418787.html 第一部分 OpenCV-Python的基本操作 第1章 …...

Go学习-Day4

文章目录 Go学习-Day4函数值传递&#xff0c;引用传递常用的函数 异常处理数组Slice切片 Go学习-Day4 个人博客&#xff1a;CSDN博客 函数 值传递&#xff0c;引用传递 值传递直接拷贝值&#xff0c;一般是基本数据类型&#xff0c;数组&#xff0c;结构体也是引用传递传递…...

将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

近期&#xff0c;工作中经常安装、部署python生产、开发环境&#xff0c;比较麻烦&#xff0c;也没有心情去优化。突然&#xff0c;我的电脑崩溃了&#xff0c;在重新安装电脑的过程中&#xff0c;保留了原来的安装软件&#xff08;有的没有放在系统盘中&#xff09;&#xff0…...

统计学补充概念07-比较树

概念 在层次聚类中&#xff0c;聚类结果可以以树状结构表示&#xff0c;通常称为树状图&#xff08;Dendrogram&#xff09;。树状图展示了数据点如何被合并或分裂以形成聚类的层次结构。通过观察树状图&#xff0c;可以更直观地理解数据点之间的相似性和关系。 在比较树状图…...

设计原则 --《设计模式之美》总结篇

本文是阅读《设计模式之美》的总结和心得&#xff0c;跳过了书中对面试和工作用处不大或不多的知识点&#xff0c;总结总共分为三章&#xff0c;分别是面对对象编程范式、设计原则和设计模式。 设计模式是代码设计时的一些经验总结。相比于设计模式&#xff0c;设计原则更抽象。…...

Day16-蜗牛影城后端开发

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

axios / fetch 实现 stream 流式请求

axios 是一个支持node端和浏览器端的易用、简洁且高效的http库。本文主要介绍 axios 如何实现 stream 流式请求&#xff0c;注意这里需要区分 node 环境和浏览器环境。 一、node端 代码演示&#xff1a; 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…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...