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

数据结构——栈与队列的实现(全码)

一  栈的概念

        栈是一种特殊的线性表,栈内数据遵循先进后出(LIFO)的原则,对于栈,只能在同一侧进行入栈和出栈操作。

入栈操作和出栈操作是在栈的同一侧进行的,如图示:

对于栈这种数据类型,我们可以采用链表或者数组来实现,但是我们一般采取数组的形式进行实现。

 二  栈的实现

1.栈的声明

对于一个用数组形式来实现的栈来说,我们需要声明:

指向栈的有效地址指针,栈顶(栈的有效空间)top,  栈的最大容量capacity

typedef int TypeData;
typedef struct Stack {TypeData* a;int top;      //有效个数int capacity;  //最大空间
}ST;

这里top为什么时栈的有效个数呢?因为我们让top指向了当前数组存在有效数据的最大下标+1的位置,这样top更加直观的表达当前栈内的元素

 2.栈的初始化

在一个栈创建后,需要对栈进行初始化后才能进行使用,对于栈的初始状态:

指向数组首元素地址的指针为NULL

栈初始的最大容量为0

栈顶top的指向为数组为0的下标,也就是当前栈的有效数据个数为0

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

初始化后栈的图示如下: 

 

3.栈的入栈

        当我们往栈中入数据时,我们不能一昧的往里面入数据,在每次入数据前需要考虑当前栈的容量是否已经满了,如果当前栈的容量已满,我们需要先将栈的最大容量扩充后再进行入栈操作。

在扩充最大容量操作时,我们应当使用realloc函数,因为我们需要保留原本栈中存放的数据

在空栈时入栈,那么第一次扩充的栈的大小是4个数据类型空间(也可以是8个,10个等)

如果栈中本来就有数据,那么当栈满时,新栈的最大容量为旧栈的两倍(或整数倍)

void STPush(ST* ps, TypeData x)
{assert(ps);//检查空间是否足够if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建newcapacity个空间ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp == NULL) {perror("realloc");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}//空间足够ps->a[ps->top++] = x;
}

 

 

 4.栈的出栈前提

当进行出栈操作时,需要判定栈是否为空,如果栈为空(也就是没有数据),则无法出栈。

        当栈顶为0时,说明当前栈中无数据,返回true,否则返回false 

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

 

 

5.栈的出栈

在栈的出栈操作前需要判断当前栈中是否存有数据,否则不能进行出栈操作

通过栈顶指针-1即可完成出栈操作

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

 

 

6.取栈顶元素

    取栈顶元素前和出栈操作一样,需要判断当前栈是否为空,否则无法取栈顶元素

    取栈顶元素返回的是top-1位置的数据,并非top位置

TypeData STTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps->a[ps->top - 1];
}

 

 

 

7.获取栈的有效个数

    直接返回top即可,因为top不仅代表了栈顶,还代表了当前栈中的有效个数

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

8.栈的销毁

栈的销毁和顺序表基本一致:

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

 

 9.栈的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int TypeData;
typedef struct Stack {TypeData* a;int top;      //有效个数int capacity;  //最大空间
}ST;//初始化
void STInit(ST* ps)
{	assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->a)free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//入栈
void STPush(ST* ps, TypeData x)
{assert(ps);//检查空间是否足够if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建newcapacity个空间ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp == NULL) {perror("realloc");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}//空间足够ps->a[ps->top++] = x;
}//检查是否为空栈
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
TypeData STTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps->a[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
int main(){return 0;}

三  队列的概念

队列是一种只允许在一侧入数据操作,另一侧出数据操作的线性表,具有先进先出的的原则

在入数据操作的一端称作队尾,在出数据的一端称作队头

而对于队列的底层,我们可以选择数组或者链表来实现,在这里我们使用链表来实现,因为采用数组来实现是,在出队操作后数组需要相继往前移动一位,这样才能使后面的的数据接着出队,因此采用数组的话在出队操作时效率会比链表低

队列的内部数据用链表来表示:

 

1.队列的声明

在 上面队列的概念中我们了解到,队列的底层由链表来实现,而队列有队头和队尾,因此队列的结构体声明有些许不同,可以理解为队列由两部分组成:链表和队列本身,因此我们需要声明两个结构体:

//队列的在链表的基础上实现,所以结构体有两个,一个是链表结点(头删尾插)
typedef int TypeData;//链表结点结构声明
typedef struct QueueNode {TypeData data;struct QueueNode* next;
}Node;
//队列本身的声明
typedef struct Queue {struct QueueNode* phead;//队头struct QueueNode* ptail;//队尾int size;//记录队列的元素个数,每次入队+1,出队-1
}Queue;

2.队列的初始化

当我们创建一个队列时,队列中是不存在数据的,也就是不存在链表结点,因此我们在初始化时不需要初始化链表结点结构体:

//队列初始化
void QueueInit(Queue* ps) {assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}

初始化时,队尾指针和队头指针应当为空,因为此时队列中还不存在数据(结点)

初始化后图示:

 

3.队列的入队 

在队列的入队操作中,其实是对队列中链表的尾插操作

入队步骤:

1)创建新结点

2)在结点插入时需要判断当前队列是否为空(也就是链表是否为空),如果队列为空,那么新创建的结点就是链表的头结点,此时队尾指针和队头指针都指向头结点

3)如果当前队列不为空,那么直接在原队列上进行尾插,即在链表进行尾插,原链表最后一个结点被尾指针指向,所以原最后一个结点的指针指向新结点,原尾指针更新指向新结点

4)记录队列元素个数的size +1

//队列的入队,尾插
void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc");exit(1);}newNode->data = x;newNode->next = NULL;//两种情况,队列为空与不为空if (ps->phead == NULL) {ps->phead = ps->ptail = newNode;}else {//队列不为空ps->ptail->next = newNode;ps->ptail = newNode;}ps->size++;
}

4.队列的出队前提

队列的出队与栈一样,在出队前对队列判断当前队列是否为空,只有队列非空的时候才能进行出队操作

//判断队列是否为空
bool QueueEmpty(Queue* ps) {//头节点为空证明队列为空return ps->phead == NULL;
}

 5.队列的出队

对于队列的出队操作,其实就是链表的头删

       先记录下队头结点的下一个结点Next,再释放队头结点并将队头结点指向队头结点的下一个结点Next,最后再将记录队列元素size成员-1

//队列出队,头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;ps->size--;
}

但是这样子其实考虑的并不完全,如果队列中只有一个结点,队尾指针和队头 指针都指向该结点,那么 Next的指向为NULL,当结点释放后,队头指针指向Next达到了置空的作用,但是队尾指针却没有置空,那么此时队尾指针就成为了野指针,这是不被允许的!

因此我们需要分两种情况进行讨论:队列只有一个结点和队列有多个结点

怎样判断队列是否只有一个结点:当队头指针和队尾指针的指向相同时

//队列出队,头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps->phead == ps->ptail) {free(ps->phead);ps->phead = ps->ptail = NULL;}else {//队列有多个结点Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;}ps->size--;
}

6.取队头元素

    无需多言,队头指针指向的数据就是队头元素,直接返回即可

//取队头元素
TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->phead->data;
}

7.取队尾元素

    无需多言,队尾指针指向的元素就是队尾元素,直接返回即可

//取队尾元素
TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->ptail->data;
}

 8.队列的销毁

利用指针del指向要删除的结点,指针Next记录删除结点的下一个结点,当del为空时证明队列已经销毁,再将队列所有的指针置空,队列有效个数置0

//队列的销毁
void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del = ps->phead;while (del) {Queue* Next = del->next;free(del);del = Next;}ps->phead = ps->ptail = del = NULL;ps->size = 0;
}

9.获取队列的有效元素个数

    直接返回结构体成员变量size即可

TypeData QueueNums(Queue* ps) {return ps->size;
}

10.队列的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//队列的在链表的基础上实现,所以结构体有两个,一个是链表结点(头删尾插)
typedef int TypeData;//链表结点结构声明
typedef struct QueueNode {TypeData data;struct QueueNode* next;
}Node;typedef struct Queue {struct QueueNode* phead;struct QueueNode* ptail;int size;
}Queue;//队列初始化
void QueueInit(Queue* ps) {assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}//队列的入队,尾插
void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc");exit(1);}newNode->data = x;newNode->next = NULL;//两种情况,队列为空与不为空if (ps->phead == NULL) {ps->phead = ps->ptail = newNode;}else {//队列不为空ps->ptail->next = newNode;ps->ptail = newNode;}ps->size++;
}//判断队列是否为空
bool QueueEmpty(Queue* ps) {//头节点为空证明队列为空return ps->phead == NULL;
}//队列出队,头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps->phead == ps->ptail) {free(ps->phead);ps->phead = ps->ptail = NULL;}else {//队列有多个结点Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;}ps->size--;
}//取队头元素
TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->phead->data;
}//取队尾元素
TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->ptail->data;
}//队列的销毁
void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del = ps->phead;while (del) {Queue* Next = del->next;free(del);del = Next;}ps->phead = ps->ptail = del = NULL;ps->size = 0;
}TypeData QueueNums(Queue* ps) {return ps->size;
}

相关文章:

数据结构——栈与队列的实现(全码)

一 栈的概念 栈是一种特殊的线性表&#xff0c;栈内数据遵循先进后出(LIFO)的原则&#xff0c;对于栈&#xff0c;只能在同一侧进行入栈和出栈操作。 入栈操作和出栈操作是在栈的同一侧进行的&#xff0c;如图示&#xff1a; 对于栈这种数据类型&#xff0c;我们可以采用链表或…...

MacOS编译和安装Poco库的方法

1.从官网git下载最新的poco源代码 在/usr/local路径下创建Poco文件夹&#xff0c;克隆Poco源代码 sudo git clone -b poco-1.13.3-release https://github.com/pocoproject/poco.git2.等了一会后&#xff0c;报错啦&#xff01;&#xff01;&#xff01; error: RPC failed…...

医院管理新境界:Spring Boot技术突破

6系统测试 6.1概念和意义 测试的定义&#xff1a;程序测试是为了发现错误而执行程序的过程。测试(Testing)的任务与目的可以描述为&#xff1a; 目的&#xff1a;发现程序的错误&#xff1b; 任务&#xff1a;通过在计算机上执行程序&#xff0c;暴露程序中潜在的错误。 另一个…...

Docker 环境下 MinIO 监控实战:通过 Prometheus 实现集群与桶级别性能监控

Docker 环境下 MinIO 监控实战&#xff1a;通过 Prometheus 实现集群与桶级别性能监控 文章目录 Docker 环境下 MinIO 监控实战&#xff1a;通过 Prometheus 实现集群与桶级别性能监控一 获取 prometheus 配置二 配置的内容三 prometheus 的配置1&#xff09;集群级别的指标2&a…...

渗透测试入门学习——使用python脚本自动跟踪csrf_token实现对网站登录界面的暴力破解

目录 写在前面 使用方法 相关代码 写在前面 最近在学习使用Burp Suite时发现其intruder模块无法实现多种模式的混合使用&#xff0c;就如想要暴力破解账号和口令两个区域并同时跟踪网页的csrf_token时BP似乎不能很方便的实现这一功能&#xff0c;于是自己在练习时就想到了用…...

stc8最小系统使用usb下载程序,关于断电的避坑

首先&#xff0c;按stc官方的原理图做好最小系统。 下面&#xff0c;来看一下stc手册中的操作步骤 USB-ISP 下载程序步骤&#xff1a; 1、按下板子上的 P3.2/INT0 按键&#xff0c;就是 P3.2 接地 2、给目标芯片重新上电&#xff0c;不管之前是否已通电。 电子开关是按下停电后…...

API 数据接口:使用操作流程与安全指南

在当今数字化高速发展的时代&#xff0c;API 数据接口如同构建数字世界的关键纽带&#xff0c;将不同的软件系统和服务紧密连接在一起。无论是企业开发者致力于提升业务效率&#xff0c;还是个人用户追求更便捷的数字体验&#xff0c;深入了解 API 数据接口的使用操作流程以及全…...

elasticsearch 8.2 版本如何设置config/elasticsearch.yml

在Elasticsearch 8.2版本中,`config/elasticsearch.yml`文件是用于配置Elasticsearch的主要配置文件。你可以通过编辑这个文件来设置各种配置选项。以下是一些常见的配置选项及其设置方法: ### 1. 基本配置 #### 集群名称 ```yaml cluster.name: my-cluster ``` #### 节点…...

华为 HCIP-Datacom H12-821 题库 (33)

&#x1f423;博客最下方微信公众号回复题库,领取题库和教学资源 &#x1f424;诚挚欢迎IT交流有兴趣的公众号回复交流群 &#x1f998;公众号会持续更新网络小知识&#x1f63c; 1.VLAN Pool 只要通过一个 SSID 就能够同时支持多个业务 VLAN&#xff0c;从而缩小广播域&#…...

【网络篇】计算机网络——运输层详述(笔记)

目录 一、运输层 1. 概述 2. 运输层和网络层的关系 3. 运输层协议概述 二、多路复用和多路分解 1. 综述 2. 无连接的多路复用与多路分解&#xff08;UDP&#xff09; 3. 面向连接的多路复用与多路分解&#xff08;TCP&#xff09; 4. Web 服务器与TCP 三、UDP&#x…...

用java编写飞机大战

游戏界面使用JFrame和JPanel构建。背景图通过BG类绘制。英雄机和敌机在界面上显示并移动。子弹从英雄机发射并在屏幕上移动。游戏有四种状态&#xff1a;READY、RUNNING、PAUSE、GAMEOVER。状态通过鼠标点击进行切换&#xff1a;点击开始游戏&#xff08;从READY变为RUNNING&am…...

java Map中get方法爆错NullPointerException

代码如下&#xff1a; public class Hello {public static void main(String[] args) {Map<Integer,Integer> map new HashMap<>();map.put(2,1);int i map.get(1); System.out.println(i);} }运行出错&#xff0c;看代码很明显是get到一个不存在map的值&#x…...

ElasticSearch备考 -- Multi field

一、题目 Create the index hamlet_2 with one primary shard and no replicas Copy the mapping of hamlet_1 into hamlet_2, but also define a multi-field for speaker. The name of such multi-field is tokens and its data type is the (default) analysed string Reind…...

刷题 图论

面试经典 150 题 - 图 200. 岛屿数量 dfs 标记 visited class Solution { public:// dfs 染色const int direction[4][2] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x…...

基于JAVA的鲜花商城管理系统(源码+定制+讲解)鲜花商城管理系统、鲜花商城管理平台、鲜花商城信息管理、鲜花商城系统开发与应用、鲜花在线商城管理系统

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…...

深圳大学-Java程序设计-选实验1 基础知识练习

实验目的与要求&#xff1a; 实验目的&#xff1a;掌握Java程序设计开发环境的搭建&#xff0c;编写简单Java Project&#xff0c;掌握编译、运行等基本步骤和命令。 实验要求&#xff1a; (1).下载、安装"Java SE Development Kit 20.0.2"最新的版本&#xff0c;需…...

第 33 章 Ajax

第 33 章 Ajax 1.XMLHttpRequest 2.GET 与 POST 3.封装 Ajax 2005 年 Jesse James Garrett 发表了一篇文章&#xff0c;标题为&#xff1a;“Ajax&#xff1a;A new Approach to Web Applications”。他在这篇文章里介绍了一种技术&#xff0c;用他的话说&#xff0c;就叫&…...

LeetCode 209 Minimum Size Subarray Sum 题目解析和python代码

题目&#xff1a; Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead. Example 1: Input: target 7, nu…...

C# 入坑JAVA 潜规则 注解 列表 listMch,该列表存储了一个映射(Map)的集合 等 入门系列3

java 项目结构 文件说明 潜规则 java入门-CSDN博客 C# 入坑JAVA 潜规则 大小写敏感文件名和类名 枚举等 入门系列2-CSDN博客 java注解 好像和C# 特性 差不多 Data Builder NoArgsConstructor AllArgsConstructor 在Java中&#xff0c;Data、Builder、NoArgsConstructor和Al…...

2024年9月个人工作生活总结

本文为 2024年9月工作生活总结。 研发编码 vuepress构建的几个问题 某vuepress项目&#xff0c;是我在3年多以前自行构想自行着手搞的&#xff0c;主要用于将一些常用的数据文件&#xff08;markdown样式&#xff09;渲染成html网页文件&#xff0c;在自建服务程序里开启访问…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...