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

【数据结构】栈和队列（c语言实现）（附源码）

news 来源：原创 2024/9/19 3:08:29

🌟🌟作者主页：ephemerals__

🌟🌟所属专栏：数据结构

目录

一、栈

1.栈的概念与结构

2.栈的实现

2.1 栈的结构定义

2.2 方法的声明

2.3 方法的实现

2.3.1  初始化

2.3.2 销毁

2.3.3 判空

2.3.4 压栈

2.3.5 出栈

2.3.6 取栈顶元素

2.4 程序全部代码

二、队列

1.队列的概念与结构

2.队列的实现

2.1 队列的结构定义

2.2 方法声明

2.3 方法实现

2.3.1 初始化

2.3.2 判空

2.3.3 入队列

2.3.4 出队列

2.3.5 取队头数据和队尾数据

2.3.6 销毁队列

2.4 程序全部代码

总结

正文开始

一、栈

1.栈的概念与结构

栈的概念：栈是一种特殊的线性表，它不允许被遍历，并且只能够在固定的一端进行数据的插入或者删除操作。进行插入或删除操作的一端称之为栈顶，另一端称为栈底。由于数据的插入和删除在同一端，所以栈的数据元素遵从“先进后出”的原则。

2.栈的实现

        一般可以使用顺序表或者链表实现栈，在进行插入删除操作时满足先进后出原则即可。由于顺序表的尾插与尾删操作效率较高，接下来我们尝试用顺序表实现它。

2.1 栈的结构定义

栈的结构定义与顺序表完全相同，定义如下：

typedef int STDataType;typedef struct Stack
{STDataType* arr;//起始指针int capacity;//栈的空间大小int top;//有效数据的个数
};

2.2 方法的声明

接下来是栈的一些常用方法：

//初始化
void STInit(ST* ps);//销毁
void STDestroy(ST* ps);//判空
bool STEmpty(ST* ps);//压栈
void STPush(ST* ps, STDataType n);//出栈
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);

2.3 方法的实现

2.3.1  初始化
//初始化
void STInit(ST* ps)
{assert(ps);//防止传空指针ps->arr = NULL;ps->capacity = ps->top = 0;
}
2.3.2 销毁
//销毁
void STDestroy(ST* ps)
{assert(ps);//防止传空if (ps->arr != NULL)//防止多次free{free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}
2.3.3 判空

        当栈中有效数据个数为0时，栈即为空。

//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
2.3.4 压栈

        进行压栈操作时，我们将结构成员top作为栈顶，在尾部插入数据：

//压栈
void STPush(ST* ps, STDataType n)
{assert(ps);if (ps->capacity == ps->top)//若空间不够，则增容{int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));if (tmp == NULL)//内存申请失败，则直接退出程序{perror("realloc");exit(1);}ps->arr = tmp;//成功则让arr指向申请好的空间ps->capacity = NewCapacity;}ps->arr[ps->top++] = n;//在栈顶插入数据
}
2.3.5 出栈

        为遵循“先进后出”原则，既然在尾部插入数据，那么删除数据时也要在尾部进行：

//出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));//确保栈不为空ps->top--;
}
2.3.6 取栈顶元素

        对于栈这样的数据结构，我们不能进行遍历，但是可以访问到栈顶元素。代码如下：

//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps && !STEmpty(ps));return ps->arr[ps->top - 1];//栈顶top-1的位置即为栈顶元素
}

2.4 程序全部代码

        关于栈实现的全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* arr;//起始指针int capacity;//栈的空间大小int top;//有效数据的个数
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestroy(ST* ps);//判空
bool STEmpty(ST* ps);//压栈
void STPush(ST* ps, STDataType n);//出栈
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//初始化
void STInit(ST* ps)
{assert(ps);//防止传空指针ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);//防止传空if (ps->arr != NULL)//防止多次free{free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//压栈
void STPush(ST* ps, STDataType n)
{assert(ps);if (ps->capacity == ps->top)//若空间不够，则增容{int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));if (tmp == NULL)//内存申请失败，则直接退出程序{perror("realloc");exit(1);}ps->arr = tmp;//成功则让arr指向申请好的空间ps->capacity = NewCapacity;}ps->arr[ps->top++] = n;//在栈顶插入数据
}//出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));//确保栈不为空ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps && !STEmpty(ps));return ps->arr[ps->top - 1];//栈顶top-1的位置即为栈顶元素
}

二、队列

        学习了栈的特性和方法实现之后，我们再来了解一个新的数据结构：队列。

1.队列的概念与结构

队列也是一种特殊的线性表，与栈相反，它只能在一端插入数据，另一端删除数据。插入数据的端叫做队尾；删除数据的一端叫做队头。因此，队列的数据元素遵从“先进先出”的原则。

2.队列的实现

        与栈相同，队列的实现也可以用顺序表或链表。由于顺序表两端的插入和删除操作要涉及到数据的全体移动，效率较低，我们就尝试用链表来实现队列。

2.1 队列的结构定义

        队列的结构定义如下：

typedef int QDataType;//定义队列的节点
typedef struct QueueNode
{QDataType data;//数据域struct QueueNode* next;//指针域
}QNode;//定义队列
typedef struct Queue
{QNode* phead;//队头指针QNode* ptail;//队尾指针int size;//队列元素个数
}Queue;

2.2 方法声明

//初始化
void QInit(Queue* pq);//判空
bool QEmpty(Queue* pq);//入队列
void QPush(Queue* pq, QDataType n);//出队列
void QPop(Queue* pq);//取队头数据
QDataType QFront(Queue* pq);//取队尾数据
QDataType QBack(Queue* pq);//销毁
void QDestroy(Queue* pq);

2.3 方法实现

2.3.1 初始化
//初始化
void QInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;//将两指针都制为空pq->size = 0;//数据个数为0
}
2.3.2 判空

        当队头指针和队尾指针都指向空时，说明队列为空。

//判空
bool QEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}
2.3.3 入队列

        入队列的操作与单链表尾插十分相似，由于有队尾指针，就无需遍历链表。注意其中的一些细节处理。

//入队列
void QPush(Queue* pq, QDataType n)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点if (newnode == NULL)//创建失败退出程序{perror("malloc");exit(1);}newnode->data = n;newnode->next = NULL;if (QEmpty(pq))//队列为空的情况{pq->phead = pq->ptail = newnode;//队头与队尾都指向新节点}else//其他情况,尾插操作{pq->ptail->next = newnode;//将新节点连接在队尾之后pq->ptail = newnode;//队尾指向新节点}pq->size++;//空间大小+1
}
2.3.4 出队列

        出队列时，注意是在队头删除数据。

//出队列
void QPop(Queue* pq)
{assert(pq && !QEmpty(pq));//确保队列不为空if (pq->phead == pq->ptail)//队列只有一个元素的情况{free(pq->phead);//删除该节点pq->phead = pq->ptail = NULL;//两指针制为空}else{QNode* next = pq->phead->next;//先记录下一个节点free(pq->phead);pq->phead = next;//让队头指向下一个节点}pq->size--;//空间大小-1
}
2.3.5 取队头数据和队尾数据
//取队头数据
QDataType QFront(Queue* pq)
{assert(pq && !QEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QBack(Queue* pq)
{assert(pq && !QEmpty(pq));return pq->ptail->data;
}
2.3.6 销毁队列
//销毁
void QDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur != NULL)//遍历删除{QNode* next = cur->next;//记录后继节点free(cur);cur = next;//cur指针指向记录的节点}pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.4 程序全部代码

        队列实现的全部代码如下：

#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* phead;//队头指针QNode* ptail;//队尾指针int size;//队列元素个数
}Queue;//初始化
void QInit(Queue* pq);//判空
bool QEmpty(Queue* pq);//入队列
void QPush(Queue* pq, QDataType n);//出队列
void QPop(Queue* pq);//取队头数据
QDataType QFront(Queue* pq);//取队尾数据
QDataType QBack(Queue* pq);//销毁
void QDestroy(Queue* pq);//初始化
void QInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;//将两指针都制为空pq->size = 0;//数据个数为0
}//判空
bool QEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;
}//入队列
void QPush(Queue* pq, QDataType n)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点if (newnode == NULL)//创建失败退出程序{perror("malloc");exit(1);}newnode->data = n;newnode->next = NULL;if (QEmpty(pq))//队列为空的情况{pq->phead = pq->ptail = newnode;//队头与队尾都指向新节点}else//其他情况,尾插操作{pq->ptail->next = newnode;//将新节点连接在队尾之后pq->ptail = newnode;//队尾指向新节点}pq->size++;//空间大小+1
}//出队列
void QPop(Queue* pq)
{assert(pq && !QEmpty(pq));//确保队列不为空if (pq->phead == pq->ptail)//队列只有一个元素的情况{free(pq->phead);//删除该节点pq->phead = pq->ptail = NULL;//两指针制为空}else{QNode* next = pq->phead->next;//先记录下一个节点free(pq->phead);pq->phead = next;//让队头指向下一个节点}pq->size--;//空间大小-1
}//取队头数据
QDataType QFront(Queue* pq)
{assert(pq && !QEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QBack(Queue* pq)
{assert(pq && !QEmpty(pq));return pq->ptail->data;
}//销毁
void QDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur != NULL)//遍历删除{QNode* next = cur->next;//记录后继节点free(cur);cur = next;//cur指针指向记录的节点}pq->phead = pq->ptail = NULL;pq->size = 0;
}

总结

        今天我们学习了栈和队列这两种数据结构：栈只能从同一端进行插入、删除操作，遵从“先进后出”原则；而队列只能从一端插入、另一端删除，遵从“先进先出”原则。栈和队列在一些场景的实用性很高，例如二叉树的层序遍历、快速排序的非递归实现等。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 学python的第一天：PyCharm创建项目
  • kickstart自动安装脚本
  • 通信原理实验——PCM编译码
  • 什么是V2X？
  • Vue+live2d实现虚拟人物互动（一次体验叙述）
  • RocketMQ 的消息存储机制
  • 3.4数组和特殊矩阵
  • Java开发：文件上传和下载
  • 按摩虎口穴位的作用
  • Laravel php框架与Yii php 框架的优缺点
  • 上线前端系统
  • 7.C基础_数组
  • DAP-Seq：解锁转录因子结合位点的新钥匙
  • 眼在手外-机器人坐标系与相机坐标系标定方法
  • CTF-web基础 web服务器
  • 【Under-the-hood-ReactJS-Part0】React源码解读
  • 【vuex入门系列02】mutation接收单个参数和多个参数
  • create-react-app项目添加less配置
  • Git同步原始仓库到Fork仓库中
  • Spring-boot 启动时碰到的错误
  • vue--为什么data属性必须是一个函数
  • XForms - 更强大的Form
  • 模仿 Go Sort 排序接口实现的自定义排序
  • 如何设计一个比特币钱包服务
  • 扫描识别控件Dynamic Web TWAIN v12.2发布，改进SSL证书
  • 一、python与pycharm的安装
  • 最近的计划
  • d²y/dx²； 偏导数问题 请问f1 f2是什么意思
  • ​Spring Boot 分片上传文件
  • ​你们这样子，耽误我的工作进度怎么办？
  • # C++之functional库用法整理
  • # Maven错误Error executing Maven
  • #我与Java虚拟机的故事#连载10： 如何在阿里、腾讯、百度、及字节跳动等公司面试中脱颖而出...
  • #知识分享#笔记#学习方法
  • ( 10 )MySQL中的外键
  • （1）SpringCloud 整合Python
  • （k8s）Kubernetes本地存储接入
  • （每日一问）设计模式：设计模式的原则与分类——如何提升代码质量？
  • （十七）Flink 容错机制
  • (转)scrum常见工具列表
  • ***利用Ms05002溢出找“肉鸡
  • .gitignore文件---让git自动忽略指定文件
  • .NET Core 控制台程序读 appsettings.json 、注依赖、配日志、设 IOptions
  • .NET Core 项目指定SDK版本
  • .Net MVC4 上传大文件，并保存表单
  • .net 程序发生了一个不可捕获的异常
  • .NET 中小心嵌套等待的 Task，它可能会耗尽你线程池的现有资源，出现类似死锁的情况
  • .NET/C# 中设置当发生某个特定异常时进入断点（不借助 Visual Studio 的纯代码实现）
  • .Net通用分页类(存储过程分页版,可以选择页码的显示样式,且有中英选择)
  • .pop ----remove 删除
  • .pub是什么文件_Rust 模块和文件 - 「译」
  • /etc/X11/xorg.conf 文件被误改后进不了图形化界面
  • [2023-年度总结]凡是过往,皆为序章
  • [BJDCTF 2020]easy_md5
  • [BZOJ1053][HAOI2007]反素数ant