初阶数据结构之---栈和队列(C语言)

引言

在顺序表和链表那篇博客中提到过,栈和队列也属于线性表

线性表:

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以数组链式结构的形式存储。

但栈和队列相比于之前学的顺序表和链表,就简单的多了。

现在我们就来看看数据结构中的队列到底是什么,以及用C语言的模拟实现吧!

概念及结构

栈的概念

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

压栈(push):栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
出栈(pop):栈的删除操作叫做出栈。出数据也在栈顶

在上图中,左边两图是压栈(push)的过程;右边两图是出栈(pop)的过程

以上就是栈的概念及逻辑,下面我们就可以来看看栈的实现了

栈的具体结构

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小,其缓存命中率也高。

下面是数组实现栈的结构

capacity是容量,指向所开空间最后一位的下一位;top是有效元素个数,指向有效数字的下一位

下面是链表实现栈的结构

由于数组实现栈相比于链表实现更有优势,这里我们用数组手搓一个栈

手搓一个栈(栈的实现)

这里的栈的空间也需要动态开辟(需要时动态扩容),故数组的内存是开辟在堆中的。

先放上需要实现的接口,头文件Stack.h

//Stack.h
// 下面是定长的静态栈的结构,实际中一般不实用
// 所以我们主要实现后面的支持动态增长的栈
// typedef int STDataType;
// #define N 10
// typedef struct Stack
// {
//  STDataType _a[N];
//  int _top; // 栈顶
// }Stack;#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int STDataType;
typedef struct stack
{STDataType* a;int top;  //栈顶int capacity; //容量
}ST;//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestory(ST* ps);
//入栈(压栈)
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* ps);

此时我们可以开始实现头文件接口中的内容了

初始化和销毁栈

感觉没什么好说的,注意下销毁的free就行

//初始化栈
void STInit(ST* ps) 
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
//销毁栈
void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

入栈(压栈)和出栈

注意在空间不够的时候要动态开辟空间realloc,这里入空间开辟后返回的指针先用tmp接收是为了防止开辟失败时找不到原来的内存空间,当开辟成功后再将新开辟的地址赋给ps->a,realloc同时也会自动释放过去的空间。

//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) {int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//这里是三目操作符//下面别忘乘sizeof(STDataType)STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));if (tmp == NULL) {perror("realloc tmp fail:");exit(1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;++ps->top;//入栈后最大元素数加一
}
//出栈
void STPop(ST* ps)
{assert(ps);//出栈时要保证栈中有元素assert(!STEmpty(ps));ps->top--;
}

获取栈顶元素

栈顶元素其实就是top前一位,这里注意栈为空时不能获取到元素

//获取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

获取栈中有效元素个数和检测栈是否为空

这里也是根据栈的top去判断就行

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

体验一下栈

//测试栈的代码
#include"Stack.h"
int main()
{struct stack st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)) {printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestory(&st);return 0;
}

怎么说呢,栈就这么点内容,再多的没有,简单的结构应该大家都能理解,如果有疑问的朋友也欢迎再评论区提出,我也会尽我所能去提供帮助。

队列

队列的概念及结构

队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出。FIFO(First In First Out)

入队列(push):进行插入操作的一端称为队尾

出队列(pop):进行删除操作的一端称为队头

队列的具体结构

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

所以这里我们讲队列链表结构的具体实现

下面是对队列维护的具体结构

下面是关于队列从队头出元素,队尾进元素的过程。

手搓一个队列(队列的实现)

先放上要实现的接口,我放在头文件Queue.h中

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 链式结构:表示队列 
typedef int QDataType;
//队列的一个结点
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{QNode* _front;QNode* _rear;int size;//队列元素个数
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

 初始化队列

这个没什么可说的,将维护队列的指针初始化制空,size置零

// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->size = 0;
}

队尾入队列

之前在实现链表的时候专门写了一个CreateNode函数,是因为当时在链表头尾中间各处插入时都需要用到。但是队列这里不同,只有入队列这一处用到了CreateNode,我们就大可不必再写这个函数,直接写在这个Push函数里就行。

在新结点开辟出来后,需要分两种情况讨论

  1. 队列中无结点(_front 和 _rear 都为空):这种情况需要同时对_front和_rear做出调整
  2. 队列中有结点:这时直接将新节点链接到 _rear 尾结点之后,同时新节点成为尾结点
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);//需要新结点,直接创建QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail:");exit(1);}newnode->_data = data;newnode->_next = NULL;if (q->_front == NULL) {q->_front = newnode;q->_rear = newnode;}else {q->_rear->_next = newnode;q->_rear = newnode;}q->size++;
}

队头出队列

这里注意_front和_rear两个指针

这里需要分三种情况讨论:

  1. 队列为空:无法执行pop,assert断言
  2. 队列只有一个结点:释放节点同时将队列置空
  3. 队列中有多个结点:将队头指针释放,_front指向下一个结点(这里稍微注意下释放顺序,不要出现释放之后还去访问结点next的情况)
// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(q->_front);if (q->size == 1) {//如果只有一个结点,直接释放free(q->_front);q->_front = q->_rear = NULL;}else {QNode* pnext = q->_front->_next;free(q->_front);q->_front = pnext;}q->size--;
}

获取队列头部元素和获取队列尾部元素

这里直接应用_front和_rear指针就可以

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}

获取队列有效元素个数和检测队列是否为空

获取队列有效元素可以直接运用上我们的size,size的大小即为有效元素个数,size为0时队列为空

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}

销毁队列

这里稍微复杂一些,需要分三种情况讨论:

  1. 队列中无元素:直接返回,不用释放了
  2. 队列中有一个元素:释放一次并置空指针,size置零
  3. 队列中有多个元素:对照链表的销毁方式销毁,最后置空指针,size置零
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);if (q->_front == NULL)return;if (q->size == 1) {free(q->_front);}else {while (q->_front) {QNode* pnext = q->_front->_next;free(q->_front);q->_front = pnext;}}q->_front = q->_rear = NULL;q->size = 0;
}

体验一下手搓的队列

#include"Queue.h"
int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 3);QueuePush(&q, 5);QueuePush(&q, 7);QueuePush(&q, 9);while (!QueueEmpty(&q)) {printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);return 0;
}

队列拓展之设计循环队列

实际中我们有时还会使用一种队列,叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。

循环队列的存储数据量有一个上限,即容量一定,其逻辑结构图大概是这样的:

循环队列可以使用数组实现,也可以使用循环链表实现:

我们将最后一个有效元素的下一位设计为尾,当front和tail相等的时候,就是队列为空的时候。

就链表实现的循环队列来说,相对比较复杂:如果你把有效数字的下一位当作尾,你将无法直接访问到链表尾元素;如果你把尾元素当作有效数字末尾,还得去区分队列只有一个元素和没有元素的情况,以及tail和front重合时是队列是满的还是空的。同时链表实现的队列还无法直接算出有效数字个数,虽然这时你也许可以存一个size专门来记录有效数字个数。

或许在你给链表设计一大堆解决方案之前,可以来看看用顺序结构来设计环形链表,你会发现,之前的一系列问题在顺序结构面前已经不复存在。

你可以通过下标直接访问到有效数字的上一位和下一位,你可以通过tail和front的相对位置直接计算出有效数字个数,你更可以单凭front和tail的相对位置来判断环形队列此时是满的还是空的。

如果大家已经有思路想法,可以先来看看这道题:622. 设计循环队列 - 力扣(LeetCode)

那么,我们接下来看看用顺序表设计循环队列的方案吧

对于循环队列的结构设计

上图中注意专门预留空间解决假溢出问题,当(rear + 1)%(k + 1) == front 时,队列为满;当rear == front 时,队列为空。这里(rear + 1)%(k + 1)是对下标的一种处理方式,使其逻辑结构为一个环,下标数字范围在(0 ~ k)。

下面我们来实现循环队列的一些功能函数

循环队列初始化

注意在malloc的时候多开了1的空间预留,开始将front和rear都置零,obj中的k置为n,这里的n指的是要开环形队列能容纳有效元素的大小

//MyCircularQueue(k): 构造器,设置队列长度为 k
MyCircularQueue* myCircularQueueCreate(int n) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int) * (n + 1));if (obj->a == NULL) {perror("malloc fail:");exit(1);}obj->front = 0;obj->rear = 0;obj->k = n;return obj;
}

检查循环队列是否为空和是否为满

当(rear + 1)%(k + 1) == front 时,队列为满;当rear == front 时,队列为空

//isEmpty(): 检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}//isFull(): 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

循环队列尾插入数据

如果队列已满则返回false,插入失败

//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj))return false;obj->a[obj->rear] = value;obj->rear = (obj->rear + 1) % (obj->k + 1);return true;
}

循环队列头删除数据

如果队列为空则返回false,删除失败

//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;obj->front = (obj->front + 1) % (obj->k + 1);return true;
}

循环队列头部和尾部获取元素

这里获取尾部元素需要经行一定的处理,rear的前一位 = (rear - 1 + k + 1)%(k + 1)

取模这部分大家可以拿出草稿纸画一画,其实也不难理解

//Front: 从队首获取元素。如果队列为空,返回 -1
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}//Rear: 获取队尾元素。如果队列为空,返回 -1
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}

释放循环队列

这里释放就行

//Free:释放空间
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

以上就是循环队列的内容,如果大家对链表实现循环队列有兴趣,可以自己在电脑上敲敲试试,虽然逻辑相比顺序表实现复杂一些,不过同样是可行的。也可以返回去做做那道力扣循环队列实现的题目,巩固一下所学。

结语

到这里栈和队列的内容基本上就结束了,本篇文章讲解了栈和队列的概念和结构,并用C语言进行了模拟实现,最后拓展了循环队列的概念结构以及循环队列的实现。如果本篇博客对你有帮助的话,还请多多支持博主,后续博主还会产出更多有意思的内容♥

有疑问或者博文有错误可以评论区提出或者私信我哦~

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

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

相关文章

【操作系统(Operator System)】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 一、概念 二、结构示意图 三、尝试理解操作系统 系统调用和库函数概念 承上启下 总结 前言 世上有两种耀眼的光芒&#xff0c;一种是正在升起的太阳&#xff…

【Go语言】Go语言中的字典

Go语言中的字典 字典就是存储键值对映射关系的集合&#xff0c;在Go语言中&#xff0c;需要在声明时指定键和值的类型&#xff0c;此外Go语言中的字典是个无序集合&#xff0c;底层不会按照元素添加顺序维护元素的存储顺序。 如下所示&#xff0c;Go语言中字典的简单示例&…

FRM模型十三:互换定价(二)

定义一个互换&#xff0c;本金为1e7&#xff0c;7年后到期 固定端&#xff1a;利率2.5%,每年付息一次 浮动端&#xff1a;Libor6M,每半年付息一次 import QuantLib as ql from prettytable import PrettyTable# 定义全局时间&#xff1a;当前日期&#xff0c;下一个结算日&…

【Mybatis】快速入门 基本使用 第一期

文章目录 Mybatis是什么&#xff1f;一、快速入门&#xff08;基于Mybatis3方式&#xff09;二、MyBatis基本使用2.1 向SQL语句传参2.1.1 mybatis日志输出配置2.1.2 #{}形式2.1.3 ${}形式 2.2 数据输入2.2.1 Mybatis总体机制概括2.2.2 概念说明2.2.3 单个简单类型参数2.2.4 实体…

计算机网络|Socket

文章目录 Socket并发socket Socket Socket是一种工作在TCP/IP协议栈上的API。 端口用于区分不同应用&#xff0c;IP地址用于区分不同主机。 以下是某一个服务器的socket代码。 其中with是python中的一个语法糖&#xff0c;代表当代码块离开with时&#xff0c;自动对s进行销毁…

将python程序打包为exe格式

1. 安装pyinstaller winr打开命令窗口 输入&#xff1a; pip install pyinstaller输入命令后会自动安装pyinstaller 2. 打包 进入你的代码所在位置&#xff0c;输入cmd 在弹出的窗口中输入 pyinstaller --onefile your_script.pyyour_script.py修改为你需要打包的程序名字 …

Sqli-labs靶场第19关详解[Sqli-labs-less-19]自动化注入-SQLmap工具注入

Sqli-labs-Less-19 通过测试发现&#xff0c;在登录界面没有注入点&#xff0c;通过已知账号密码admin&#xff0c;admin进行登录发现&#xff1a; 返回了Referer &#xff0c;设想如果在Referer 尝试加上注入语句&#xff08;报错注入&#xff09;&#xff0c;测试是否会执行…

简单网站模板1(HTML)

想要拥有自己的网站&#xff0c;却不知该如何才能简约好看&#xff0c;接下来分享一种自己搭建的网站模板&#xff0c;希望大家喜欢。 展示图&#xff1a; CODE: <!DOCTYPE html> <html> <head><title>我的网站</title><style>body {fo…

【详识JAVA语言】面向对象程序三大特性之二:继承

继承 为什么需要继承 Java中使用类对现实世界中实体来进行描述&#xff0c;类经过实例化之后的产物对象&#xff0c;则可以用来表示现实中的实体&#xff0c;但是 现实世界错综复杂&#xff0c;事物之间可能会存在一些关联&#xff0c;那在设计程序是就需要考虑。 比如&…

黑马点评-短信登录业务

原理 模型如下 nginx nginx基于七层模型走的事HTTP协议&#xff0c;可以实现基于Lua直接绕开tomcat访问redis&#xff0c;也可以作为静态资源服务器&#xff0c;轻松扛下上万并发&#xff0c; 负载均衡到下游tomcat服务器&#xff0c;打散流量。 我们都知道一台4核8G的tomca…

微服务API网关---APISIX

最近在做微服务调研&#xff0c;看到了apisix这个网关&#xff0c;于是进行了初步了解一下。 微服务是指&#xff0c;将大型应用分解成多个独立的组件&#xff0c;其中每个组件都各自的负责对应项目。 系统的架构大致经历了&#xff1a;单体应用架构–> SOA架构 -->微服务…

(六)Dropout抑制过拟合与超参数的选择--九五小庞

过拟合 即模型在训练集上表现的很好&#xff0c;但是在测试集上效果却很差。也就是说&#xff0c;在已知的数据集合中非常好&#xff0c;再添加一些新数据进来效果就会差很多 欠拟合 即模型在训练集上表现的效果差&#xff0c;没有充分利用数据&#xff0c;预测准确率很低&a…

SpringCache【缓存接口返回值信息】【前端访问后端,后端访问数据库(可以缓存这个过程,前端访问后端,保存记录,下次访问直接返回之前的数据)】

SpringCache 针对不同的缓存技术需要实现不同的CacheManager&#xff1a;注解入门程序CachePut注解CacheEvict注解Cacheable注解 Spring Cache是一个框架&#xff0c;实现了基于注解的缓存功能&#xff0c;只需要简单地加一个注解&#xff0c;就能实现缓存功能&#xff0c;大大…

Appium手机Android自动化

目录 介绍 什么是APPium&#xff1f; APPium的特点 环境准备 adb(android调试桥)常用命令 appium图形化简单使用 连接手机模拟器 使用appium桌面端应用程序 ​编辑 整合java代码测试 环境准备 引入所需依赖 书写代码简单启动 ​编辑 Appium元素定位 id定位 介…

spring.factories的常用配置项

概述 spring.factories 实现是依赖 spring-core 包里的 SpringFactoriesLoader 类&#xff0c;这个类实现了检索 META-INF/spring.factories 文件&#xff0c;并获取指定接口的配置的功能。 Spring Factories机制提供了一种解耦容器注入的方式&#xff0c;帮助外部包&am…

详细了解C++中的namespace命名空间

键盘敲烂&#xff0c;月薪过万&#xff0c;同学们&#xff0c;加油呀&#xff01; 目录 键盘敲烂&#xff0c;月薪过万&#xff0c;同学们&#xff0c;加油呀&#xff01; 一、命名空间的理解 二、&#xff1a;&#xff1a;作用域运算符 三、命名空间&#xff08;namespace&…

像用Excel一样用Python:pandasGUI

文章目录 启动数据导入绘图 启动 众所周知&#xff0c;pandas是Python中著名的数据挖掘模块&#xff0c;以处理表格数据著称&#xff0c;并且具备一定的可视化能力。而pandasGUI则为pandas打造了一个友好的交互窗口&#xff0c;有了这个&#xff0c;就可以像使用Excel一样使用…

Qt CMake 国际化相关配置

文章目录 更新ts文件发布ts文件 本来用qmake使用pro文件很简单的一件事&#xff0c;结果用cmake折腾了半天。 何必呢~ 参考&#xff1a;QT6.3 CMake 多语言切换 这是我的 cmake_minimum_required(VERSION 3.16)project(testQml3_6 VERSION 0.1 LANGUAGES CXX)set(CMAKE_AUTO…

Tkinter.Text控件中,文本存在某个关键字的将被高亮显示(标记颜色+字体加粗)

在Tkinter的Text控件中&#xff0c;要标记某个关键字并改变其颜色&#xff0c;你可以使用tag_add方法来给包含关键字的文本添加标签&#xff0c;然后使用tag_config方法来配置该标签的显示样式&#xff0c;包括前景色&#xff08;字体颜色&#xff09;和背景色等。以下是一个完…

简历中自我评价,是否应该删掉?

你好&#xff0c;我是田哥 年后&#xff0c;不少朋友已经开始着手准备面试了&#xff0c;准备面试的第一个问题就是&#xff1a;简历。 写简历是需要一些技巧的&#xff0c;你的简历是要给面试官看&#xff0c;得多留点心。 很多简历上都会写自我评价/个人优势/个人总结等&…