重生之“我打数据结构，真的假的？”--3.栈和队列

1.栈和队列的基本概念

1.1 栈

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

1.2 初始化及功能实现

#include"stack.h"typedef int datatype;
typedef struct stack
{datatype* a;int top;int capacity;
}ST;void InitST(ST* sl)
{assert(sl);                  //sl不为NULLsl->a = NULL;sl->top = 0;sl->capacity = 0;
}//初始化void STpush(ST* sl, int data)
{assert(sl);if (sl->top == sl->capacity){int newcapacity = sl->capacity == 0 ? 2 : sl->capacity * 2;datatype* tmp = (datatype*)realloc(sl->a, newcapacity * sizeof(datatype));sl->a = tmp;sl->capacity = newcapacity;}sl->a[sl->top] = data;sl->top++;
}//插入
void STpop(ST* sl)
{assert(sl);                //！！！！！！判断指针是否为空，《《《《判断的是栈是否存在》》》》》》          assert(!STempty(sl));      //！！！！！！！！！与上文不同，《《《《判断的是栈是否为空》》》》》》sl->top--;
}//删除datatype STtop(ST* sl)
{assert(sl);assert(!STempty(sl));return sl->a[sl->top-1];
}//取栈顶void STdestroy(ST* sl)
{assert(sl);free(sl->a);sl->a = NULL;sl->top = sl->capacity = 0;
}bool STempty(ST* sl)
{assert(sl);return sl->top == 0;
}

1.3 括号匹配问题

. - 力扣（LeetCode）

思路：

1.设立一个栈，依次从s中取出元素，如果为左括号类型 则入栈

2.否则取栈顶元素（如果栈为空则直接返回false）如果匹配

则删除栈顶元素，如果不匹配，返回false

3.s访问完后，如果栈为空，则返回true，否则返回false

bool isValid(char* s) {typedef struct stack
{char * a;int top;int capacity;
}ST;bool STempty(ST* sl)
{assert(sl);return sl->top == 0;
}
void InitST(ST* sl)
{assert(sl);                  //sl不为NULLsl->a = NULL;sl->top = 0;sl->capacity = 0;
}void STpush(ST* sl, char data)
{assert(sl);if (sl->top == sl->capacity){int newcapacity = sl->capacity == 0 ? 2 : sl->capacity * 2;char* tmp = (char*)realloc(sl->a, newcapacity * sizeof(char));sl->a = tmp;sl->capacity = newcapacity;}sl->a[sl->top] = data;sl->top++;
}
void STpop(ST* sl)
{assert(sl);                //！！！！！！判断指针是否为空，《《《《判断的是栈是否存在》》》》》》          assert(!STempty(sl));      //！！！！！！！！！与上文不同，《《《《判断的是栈是否为空》》》》》》sl->top--;
}char STtop(ST* sl)
{assert(sl);assert(!STempty(sl));return sl->a[sl->top-1];
}void STdestroy(ST* sl)
{assert(sl);free(sl->a);sl->a = NULL;sl->top = sl->capacity = 0;
}int i=0;char j;char k;ST L;ST R;InitST(&L);InitST(&R);while(s[i]!='\0'){if(s[i]=='('||s[i]=='['||s[i]=='{'){STpush(&L, s[i]);i++;}else{if(STempty(&L))return false;if((STtop(&L)=='('&&s[i]==')')||(STtop(&L)=='{'&&s[i]=='}')||(STtop(&L)=='['&&s[i]==']')){STpop(&L);i++;}elsereturn false;}}if(STempty(&L))return true;elsereturn false;}

2.队列 

2.1 概念

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素

2.2 初始化及功能实现

typedef int datatype;
typedef struct Queuenode
{datatype data;struct Queuenode * next;
}Qnode;typedef struct QT
{Qnode* head;Qnode* tail;int size;
}QT;void QueueInit(QT* sl)
{assert(sl);sl->head = NULL;sl->tail = NULL;sl->size = 0;
}bool Queueempty(QT* sl)
{assert(sl);return sl->head ==NULL;
}void Queuepush(QT* sl, int x)
{assert(sl);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));newnode->next = NULL;newnode->data = x;if (Queueempty(sl)){sl->head = newnode;sl->tail = newnode;}else{sl->tail->next = newnode;sl->tail = newnode;}sl->size++;
}void Queuepop(QT* sl)
{assert(sl);assert(!Queueempty(sl));Qnode* next = sl->head->next;free(sl->head);sl->head = next;sl->size--;
}int Queuetop(QT* sl)
{assert(sl);assert(!Queueempty(sl));return sl->head->data;
}void Queuedestroy(QT* sl)
{assert(sl);while (!Queueempty(sl))Queuepop(sl);sl->head = sl->tail = NULL;sl->size = 0;
}

2.3 循环队列 

. - 力扣（LeetCode）

typedef struct Queuenode
{int data;struct Queuenode * next;
}Qnode;typedef struct {
Qnode* head;
Qnode* tail;
int size;
int flag;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* sl=NULL;sl=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));sl->head = NULL;sl->tail = NULL;sl->size = 0;sl->flag = k;return sl;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head ==NULL;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(obj->size>=obj->flag)return false;Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));newnode->next = NULL;newnode->data = value;if(myCircularQueueIsEmpty(obj)){obj->head = newnode;obj->tail = newnode;obj->tail->next=obj->head;obj->head->next=obj->tail;}else{ obj->tail->next = newnode;obj->tail = newnode;if(obj->head->next==obj->head)obj->head->next=obj->tail;obj->tail->next=obj->head;}
obj->size++;
return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{if(obj->head!=obj->tail){Qnode* next = obj->head->next;obj->tail->next=next;free(obj->head);obj->head = next;obj->size--;}else{free(obj->head);obj->head = obj->tail = NULL;obj->size = 0;}}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {int i=0;if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->head->data;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->tail->data;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->flag;
}void myCircularQueueFree(MyCircularQueue* obj) {while (!myCircularQueueIsEmpty(obj)){Qnode* next = obj->head->next;obj->tail->next=next;if(obj->head!=obj->tail){ free(obj->head);obj->head = next;obj->size--;}else{obj->head = obj->tail = NULL;obj->size = 0;break;}}}

3.用栈实现队列 

 . - 力扣（LeetCode）

 思路：

1.可以设立两个栈 p，q

（1）入队：将p中元素依次入栈q，再将函数传递的数据入栈q

（2）出队：将q中元素依次入栈p，再取q栈顶元素

typedef struct stack
{int * a;int top;int capacity;
}ST;typedef struct {
ST* p;
ST* q;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue*sl=NULL;sl=(MyQueue*)malloc(sizeof(MyQueue));sl->q=(ST*)malloc(sizeof(ST));sl->p=(ST*)malloc(sizeof(ST));sl->q->a=NULL;sl->q->top=0;sl->q->capacity=0;sl->p->a=NULL;sl->p->top=0;sl->p->capacity=0;return sl;
}bool STempty(ST* sl)
{assert(sl);return sl->top == 0;
}int STtop(ST* sl)
{assert(sl);assert(!STempty(sl));int i;i=sl->a[sl->top-1];return i;
}void myQueuePush(MyQueue* obj, int x) {while(!STempty(obj->q)){
if (obj->p->top == obj->q->capacity)
{int newcapacity = obj->q->capacity == 0 ? 2 : obj->p->capacity * 2;int * tmp = (int*)realloc(obj->p->a, newcapacity * sizeof(int));obj->p->a = tmp;obj->p->capacity = newcapacity;
}
obj->p->a[obj->p->top] =STtop(obj->q) ;
obj->p->top++;
obj->q->top--;}if (obj->p->top == obj->p->capacity)
{int newcapacity = obj->p->capacity == 0 ? 2 : obj->p->capacity * 2;int * tmp = (int*)realloc(obj->p->a, newcapacity * sizeof(int));obj->p->a = tmp;obj->p->capacity = newcapacity;
}
obj->p->a[obj->p->top] = x;
obj->p->top++;
}int myQueuePop(MyQueue* obj) {while(!STempty(obj->p)){if (obj->q->top == obj->q->capacity)
{int newcapacity = obj->q->capacity == 0 ? 2 : obj->q->capacity * 2;int * tmp = (int*)realloc(obj->q->a, newcapacity * sizeof(int));obj->q->a = tmp;obj->q->capacity = newcapacity;
}
obj->q->a[obj->q->top] =STtop(obj->p) ;
obj->q->top++;
obj->p->top--;}int i=STtop(obj->q);obj->q->top--;return i;
}int myQueuePeek(MyQueue* obj) {while(!STempty(obj->p)){if (obj->q->top == obj->q->capacity)
{int newcapacity = obj->q->capacity == 0 ? 2 : obj->q->capacity * 2;int * tmp = (int*)realloc(obj->q->a, newcapacity * sizeof(int));obj->q->a = tmp;obj->q->capacity = newcapacity;
}
obj->q->a[obj->q->top] =STtop(obj->p) ;
obj->q->top++;
obj->p->top--;}int i=STtop(obj->q);return i;
}bool myQueueEmpty(MyQueue* obj) {if(STempty(obj->p)&&STempty(obj->q))return true;elsereturn false;
}void myQueueFree(MyQueue* obj) {free(obj->p);free(obj->q);
}

 

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

深度剖析：品牌推广中的专业外包服务商策略

深度剖析：品牌推广中的专业外包服务商策略

回顾历史，从农业革命到工业革命，再到如今的信息技术革命，每一次社会生产力的飞跃都伴随着分工的细化和专业化的提升。亚当斯密在《国富论》中提出的“分工论”早已揭示了这一真理：通过分工，每个人专注于自己擅长的领域…
阅读更多...
计算机网络（Wrong Question）

计算机网络（Wrong Question）

一、计算机网络体系结构 1.1 计算机网络概述 D 注：计算机的三大主要功能是数据通信、资源共享、分布式处理。（负载均衡、提高可靠性） 注：几段链路就是几段流水。 C 注：记住一个基本计算公式：若n个分组&a…
阅读更多...
昇思25天学习打卡营第01天|昇思MindSpore大模型基础j介绍

昇思25天学习打卡营第01天|昇思MindSpore大模型基础j介绍

昇思MindSpore和华为昇思MindSpore大模型学习打卡系列文章，本文仅供参考~ 文章目录 前言一、昇思MindSpore是什么？二、执行流程三、设计理念四、层次结构五、Huawei昇腾AI全栈 前言 随着计算机大模型的不断发展，Ai这门技术也越来越重要&#…
阅读更多...
HarmonyOS 自定义节点

HarmonyOS 自定义节点

1. HarmonyOS 自定义节点 1.1. 概念 官方文档（https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V5/arkts-user-defined-capabilities-V5）   自定义能力是HarmonyOS ArkUI开发框架提供的对UI界面进行开发和设计的能力。现有的自定义…
阅读更多...
数模打怪（八）之图论模型

数模打怪（八）之图论模型

一、作图 图的数学语言描述： G( V(G), E(G) )，G（graph）：图，V（vertex）：顶点集，E（edge）：边集 1、在线作图 https://csac…
阅读更多...
《牛角型电解电容和螺栓型电解电容》

《牛角型电解电容和螺栓型电解电容》

牛角型电解电容之所以被称为牛角型，是因为引出端子的形状类似牛角。 螺栓型电解电容被称为螺栓型，是因为其引出端子的形状像螺栓。 牛角型电解电容和螺栓型电解电容，虽然也是电容，但在普通电路板上用的很少，更多是安…
阅读更多...
Linux网络-wget命令

Linux网络-wget命令

作者介绍：简历上没有一个精通的运维工程师。希望大家多多关注我，我尽量把自己会的都分享给大家，下面的思维导图也是预计更新的内容和当前进度(不定时更新)。 Linux服务器作为一个常用的网络服务器，主要的作用就是向客户端提供网络…
阅读更多...
学习测试11-移动自动化（略）

学习测试11-移动自动化（略）

安卓SDK 链接: https://pan.baidu.com/s/1P4v9K2RYAGEoA5M_93hHlQ?pwdqsbu 提取码: qsbu 复制这段内容后打开百度网盘手机App，操作更方便哦 记得配置环境变量 下载Appium软件 hub网址：https://github.com/appium/appium-desktop/releases 链接: https…
阅读更多...
【Node.js入门精要】从零开始的开发之旅

【Node.js入门精要】从零开始的开发之旅

说明文档：Node.js 教程_w3cschool 概念 Node.js 是一个开源、跨平台的 JavaScript 运行时环境，基于 Chrome 的 V8 引擎构建，专为构建高性能和可扩展的网络应用程序而设计的服务端语言。它采用事件驱动、非阻塞 I/O 模型，能够处理大…
阅读更多...
【Django】前端技术HTML常用标签(开发环境vscode)

【Django】前端技术HTML常用标签(开发环境vscode)

文章目录 安装两个常用插件HTML常用标签定义文档类型DOCTYPE网页的结构html/head//title/body/div标题h1/h2/h3/h4/h5分割线hr段落 p列表ul/li，ol/li超链接a文本span图片img按钮button表格table（table、tr、th、td）表单form 安装两个常用插件…
阅读更多...
学习大数据DAY25 Shell脚本的书写2与Shell工具的使用

学习大数据DAY25 Shell脚本的书写2与Shell工具的使用

目录 自定义函数 递归-自己调用自己 上机练习 12 Shell 工具 sort sed awk 上机练习 13 自定义函数 name(){ action; } function name { Action; } name 因为 shell 脚本是从上到下逐行运行，不会像其它语言一样先编译，所以函数必 须在调…
阅读更多...
React Router-v6.25.1

React Router-v6.25.1

以下例子是根据vitereactts构建的，使用路由前先安装好这些环境！！！！ 1、路由的简单使用 首先要创建一个浏览器路由器并配置我们的第一个路由。这将为我们的 Web 应用启用客户端路由。 该main.jsx文件是入口点。打开它…
阅读更多...
前端知识--前端访问后端技术Ajax及框架Axios

前端知识--前端访问后端技术Ajax及框架Axios

一、异步数据请求技术----Ajax Ajax是前端访问后端的技术，为异步请求（不刷新页面，请求数据，只更新局部数据）。 例如：在京东网站中搜索电脑，就会出现一些联想搜索，但此时页面并没有…
阅读更多...
Pytorch深度学习实践（5）逻辑回归

Pytorch深度学习实践（5）逻辑回归

逻辑回归 逻辑回归主要是解决分类问题 回归任务：结果是一个连续的实数分类任务：结果是一个离散的值 分类任务不能直接使用回归去预测，比如在手写识别中（识别手写 0 − − 9 0 -- 9 0−−9），因为各个类别…
阅读更多...
动态获取配置文件中的配置参数，当配置文件中的参数修改之后，不需要重启项目

动态获取配置文件中的配置参数，当配置文件中的参数修改之后，不需要重启项目

这里写目录标题 一、本地开发环境二、nocas环境配置 一、本地开发环境 如果是在本地开发环境中，读取的配置文件是本地根目录下的application.properties文件： 路径为配置文件的绝对路径。 配置文件里面配置的参数需要和获取的参数名称相互对应 通过Au…
阅读更多...
linux怎么创建python

linux怎么创建python

第一步，创建一个test文件夹。 第二步，打开终端进入该文件。 第三步，vim test.py。 第四步，编写代码。 第五步，编辑好之后，按Esc键切换到命令模式，然后输入:wq，再按回车键即可自动保存…
阅读更多...
Java突击复习小练习，附带讲解

Java突击复习小练习，附带讲解

练习： 1.下面的代码在主方法中可以正常执行吗，如果不能，为什么？ 2.已知i的值为10，请问在情况一和情况二中j的值是否相同呢？如果不相同，它们的值分别是多少呢?为什么？ 3.在主方法运…
阅读更多...
3D打印：重塑模具制造业的创新引擎

3D打印：重塑模具制造业的创新引擎

在科技浪潮的推动下，3D打印技术正以前所未有的速度渗透到制造业的核心，尤其在模具制造领域，它正引领一场深刻的创新革命。该技术通过颠覆传统制造范式，显著优化了模具生产的复杂流程，实现了从设计到成品的一体化的高效…
阅读更多...
系统架构设计师教程 第4章 信息安全技术基础知识-4.3 信息安全系统的组成框架4.4 信息加解密技术-解读

系统架构设计师教程 第4章 信息安全技术基础知识-4.3 信息安全系统的组成框架4.4 信息加解密技术-解读

系统架构设计师教程 第4章 信息安全技术基础知识-4.3 信息安全系统的组成框架 4.3　信息安全系统的组成框架4.3.1　技术体系4.3.1.1 基础安全设备4.3.1.2 计算机网络安全4.3.1.3 操作系统安全4.3.1.4 数据库安全4.3.1.5 终端安全设备4.3.2 组织机构体系4.3.3 管理体系4.4 信息加…
阅读更多...
【PostgreSQL 16】专栏日常

【PostgreSQL 16】专栏日常

本专栏从 3 个月前开始着手准备&#xff0c;利用周末及节假日的时间来整理。 ldczzDESKTOP-HVJOUVN MINGW64 ~/mypostgres (dev) $ git lg |tee * 7a7f468 - (HEAD -> dev, origin/main, origin/dev, main) 完成服务端编程的初步整理 (6 minutes ago) <Laven Liu> * …
阅读更多...
最新文章

Copyright @ 2022~2023