栈和队列题目详解

前言：

在前面我们学习了栈和队列，栈的特性是后进先出，队列的特性是先进先出，当我们了解了这些之后，我们就可以用到栈和队列的特性来简单的做一些题目了。

1. 有效的括号

有效的括号：. - 力扣（LeetCode）

思路：这个题目我们就可以很好的利用栈的特性来进行解决，我们让左括号入栈，如果我们读取过程中，遇到了右括号，我们就将栈顶的左括号拿出来与它进行匹配，这里会出现两种情况：

情况1：我们在遇到右括号的时候，发现栈为空，此时说明配对失败了。

情况2：当我们遍历完字符串了之后，发现栈不为空，那么此时说明左右括号的数量不匹配，此时也说明失败了。

 代码：

typedef char STDataType;

typedef struct Stack
{
	STDataType* arr;
	int top;
	int capacity;
}st;

void STInit(st* pst);

void STDestroy(st* pst);

void STPush(st* pst, STDataType x);

void STPop(st* pst);

STDataType STTop(st* pst);

bool STEmpty(st* pst);

int STSize(st*pst);
void STInit(st* pst)
{
	assert(pst);
	pst->arr = NULL;
	pst->top = pst->capacity = 0;
}

void STDestroy(st* pst)
{
	assert(pst);
	free(pst->arr);
	pst->arr = NULL;
	pst->capacity = pst->top = 0;
}

void STPush(st* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
	pst->arr[pst->top++] = x;
}

void STPop(st* pst)
{
	assert(pst);
	assert(pst->top > 0);
	
	pst->top--;
}

STDataType STTop(st* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->arr[pst->top - 1];
}

bool STEmpty(st* pst)
{
	assert(pst);
	return pst->top == 0;
}

int STSize(st*pst)
{
	assert(pst);
	return pst->top;
}

bool isValid(char* s) {
    st pst;
    STInit(&pst);
    while(*s)
    {
        //左扩号进栈
        if(*s == '('||*s == '[' || *s == '{')
        {
            STPush(&pst,*s);
        }
        else
        {
            //如果左括号没有入栈，那么栈是空的，就不能和之后的右括号进行匹配
            if(STEmpty(&pst))
            {
                return false;
            }
            //创建字符类型接收栈顶元素
            char tmp = STTop(&pst);
            //出栈
            STPop(&pst);
            //这里有一对匹配不合格直接返回false
            if(tmp == '(' && *s != ')' ||
               tmp == '[' && *s != ']' ||
               tmp == '{' && *s != '}')
               return false;
        }
        //让s往后走
        s++;
    }
    //如果s走完了，但是栈内还有元素，就说明匹配不成功
    if(!STEmpty(&pst))
    {
        return false;
    }
    else
    {
        return true;
    }
}

2. 用队列实现栈

用队列实现栈：. - 力扣（LeetCode）

思路：我们知道栈的特性是后进先出，队列是先进先出，我们如何使用两个队列来实现一个栈，其实，我们可以一个队列用来存数据，一个队列为空队列，我们在之后的入数据入到不为空的队列，如果要出数据，我们就可以将不为空的队列的前size-1个数据入到空队列里面，不为空的队列最后剩下的一个数据就栈的栈顶元素。

 代码：

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* qp);
//入队 出队
void QPush(Queue* qp, QDataType x);
void QPop(Queue* qp);
//获取队首,队尾数据
QDataType QFront(Queue* qp);
QDataType QBack(Queue* qp);

//获取对内有效数据个数
int QSize(Queue* qp);

//判断队列是否为空
bool QEmpty(Queue* qp);

//销毁队列
void QDestroy(Queue* qp);
void QInit(Queue* qp)
{
	assert(qp);
	qp->phead = NULL;
	qp->ptail = NULL;
	qp->size = 0;
}

void QDestroy(Queue* qp)
{
	assert(qp);
	QNode* cur = qp->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	qp->phead = qp->ptail = NULL;
	qp->size = 0;	
}

void QPush(Queue* qp, QDataType x)
{
	assert(qp);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (qp->phead == NULL)
	{
		qp->phead = qp->ptail = newnode;
	}
	else
	{
		qp->ptail->next = newnode;
		qp->ptail = newnode;
	}
	qp->size++;
}

void QPop(Queue* qp)
{
	assert(qp);
	assert(qp->size > 0);
	if (qp->phead->next == NULL)
	{
		free(qp->phead);
		qp->phead = qp->ptail = NULL;
	}
	else
	{
		QNode* next = qp->phead->next;
		free(qp->phead);
		qp->phead = next;
	}
	qp->size--;
}

QDataType QFront(Queue* qp)
{
	assert(qp);
	assert(qp->phead);
	return qp->phead->data;
}

QDataType QBack(Queue* qp)
{
	assert(qp);
	assert(qp->ptail!=NULL);

	return qp->ptail->data;
}

int QSize(Queue* qp)
{
	assert(qp);
	return qp->size;
}

bool QEmpty(Queue* qp)
{
	assert(qp);

	return qp->size == 0;
}


typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    //初始化栈
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    if(pst == NULL)
    {
        perror("malloc");
        exit(1);
    }
    //初始化两个队列
   QInit(&pst->q1);
   QInit(&pst->q2);

   return pst;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //如果q1队列为空，我们就把数据插入到q2
    if( QEmpty(&obj->q1))
    {
       
        QPush(&obj->q2,x);
    }
    else//反之插入到q1
    {
        QPush(&obj->q1,x);

    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    //假设法
    //这里我们们假设q1为空队列，q2为非空队列
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if(QEmpty(&obj->q2))//如果q2为空队列
    {
        //交换一下
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    //将非空队列里面前size-1个数据导入到空队列，此时剩下的数据就是栈顶元素
    while(QSize(noempty)>1)
    {
        QPush(empty,QFront(noempty));
        QPop(noempty);
    }
    //接收非空队列的最后一个数据即栈顶数据
    int ret = QFront(noempty);
    //删除栈顶数据
    QPop(noempty);
    return ret;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    //这里如果q1是空队列，返回q2的队尾
    if(QEmpty(&obj->q1))
    {
        return QBack(&obj->q2);
    }
    else
    {
        //反之返回q1的队尾
        return QBack(&obj->q1);

    }
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    //两个队列同时为空才是空
    return QEmpty(&obj->q1)&& QEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    //释放
    QDestroy(&obj->q1);
    QDestroy(&obj->q2);
    free(obj);
    obj = NULL;

}

3. 用栈实现队列

用栈实现队列：. - 力扣（LeetCode）

思路：这里我们如何用两个队列来是实现栈，我们还是可以用一个栈用来入数据，一个栈用来出数据，如果有数据，就都入到入数据的这个栈里面，如果需要出数据，我们先判断出数据的这个栈是否为空，如果为空，我们就把入数据的这个栈里面的数据全部导入到出数据的这个栈里面。

代码：

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;
	int top;
	int capacity;
}st;

void STInit(st* pst);

void STDestroy(st* pst);

void STPush(st* pst, STDataType x);

void STPop(st* pst);

STDataType STTop(st* pst);

bool STEmpty(st* pst);

int STSize(st*pst);

void STInit(st* pst)
{
	assert(pst);
	pst->arr = NULL;
	pst->top = pst->capacity = 0;
}

void STDestroy(st* pst)
{
	assert(pst);
	free(pst->arr);
	pst->arr = NULL;
	pst->capacity = pst->top = 0;
}

void STPush(st* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDataType* tmp = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
	pst->arr[pst->top++] = x;
}

void STPop(st* pst)
{
	assert(pst);
	assert(pst->top > 0);
	
	pst->top--;
}

STDataType STTop(st* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->arr[pst->top - 1];
}

bool STEmpty(st* pst)
{
	assert(pst);
	return pst->top == 0;
}

int STSize(st*pst)
{
	assert(pst);
	return pst->top;
}

typedef struct {
    ///创建两个栈，一个栈用来入数据，一个栈用来出数据
    st pushst;
    st popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* tmp = (MyQueue*)malloc(sizeof(MyQueue));
    if(tmp == NULL)
    {
        perror("malloc");
        exit(1);
    }
    //初始化两个栈
    STInit(&tmp->pushst);
    STInit(&tmp->popst);
    return tmp;

}

void myQueuePush(MyQueue* obj, int x) {
     assert(obj);
     //我们直接将数据插入到入栈栈里面
     STPush(&obj->pushst,x);
}

int myQueuePop(MyQueue* obj) {
    //这里我们调用一下下面的函数，如果出栈栈为空则把入栈栈的数据都导入到出栈栈里面
    //然后接收队列开头元素
    int ret = myQueuePeek(obj);
    
    //直接删除出栈栈的栈顶元素
    STPop(&obj->popst);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //如果出栈栈为空
    if(STEmpty(&obj->popst))
    {
        //那么我们把入栈栈的数据导入到出栈栈里面
        while(!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    //此时的栈顶元素就是队列的队头元素
    return STTop(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
   //两个栈都为空，队列才为空
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);
    //先释放动态申请的两个栈 
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    //在释放动态申请的队列
    free(obj);
    obj = NULL;


}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

YOLOv10改进 | Conv篇 | 利用FasterBlock二次创新C2f提出一种全新的结构（全网独家首发，参数量下降70W）

YOLOv10改进 | Conv篇 | 利用FasterBlock二次创新C2f提出一种全新的结构（全网独家首发，参数量下降70W）

一、本文介绍 本文给大家带来的改进机制是利用FasterNet的FasterBlock改进特征提取网络，将其用来改进ResNet网络，其旨在提高计算速度而不牺牲准确性，特别是在视觉任务中。它通过一种称为部分卷积（PConv）的新技术来减少…
阅读更多...
火柴棒图python绘画

火柴棒图python绘画

使用Python绘制二项分布的概率质量函数（PMF） 在这篇博客中，我们将探讨如何使用Python中的scipy库和matplotlib库来绘制二项分布的概率质量函数（PMF）。二项分布是统计学中常见的离散概率分布，描述了在固定次…
阅读更多...
夏日智启：我的Datawhale AI夏令营探索之旅

夏日智启：我的Datawhale AI夏令营探索之旅

前言 最近几年，AI（人工智能）的发展呈现出了前所未有的迅猛势头，其影响力和应用范围不断扩大，深刻地改变着我们的生活、工作和社会结构。尤其是AI大模型技术，国内外可谓是“百模大战”，百舸争流…
阅读更多...
ESP32网络开发：1.创建一个基于TCP网络协议的网站

ESP32网络开发：1.创建一个基于TCP网络协议的网站

一、TCP协议的介绍 TCP（传输控制协议，Transmission Control Protocol）是互联网协议套件中的一种核心协议，主要用于在网络中的计算机之间可靠地传输数据。TCP协议位于OSI模型（开放系统互联模型）的传输层&…
阅读更多...
虚拟机内安装vue-dev-tools

虚拟机内安装vue-dev-tools

前言 项目开发调试都需要在Citrix在虚拟机环境下，Citrix内连接不到外网，在这边文章，我将介绍自己在Citrix环境内安装 vue-dev-tools的经验 环境 vue 步骤 1. 下载.crx文件 百度网盘里的 .crx文件的 下载链接 2. 加载.crx文件 打开浏览…
阅读更多...
软件兼容性测试重要吗?有哪些测试流程和注意事项?

软件兼容性测试重要吗?有哪些测试流程和注意事项?

软件兼容性测试是指测试软件在不同硬件、操作系统、网络环境和软件环境下的稳定性和可用性的能力，也就是说，软件在不同的平台上是否能正常运行，是否能与其他软件和系统兼容。 兼容性问题是影响软件用户体验的重要因素之一，如果软…
阅读更多...
学习大数据DAY13 PLSQL基础语法2

学习大数据DAY13 PLSQL基础语法2

目录 选择结构 IF语句 简单判断语句 带判断不成立语句 多判断语句 IF语句注意事项： CASE 语句 简单CASE语句 搜索型CASE语句 作业 循环语句 循环结构 简单循环 属性 描述 位置 场景 WHILE循环 属性 FOR循环 数值型for循环 数值型for循环的特性…
阅读更多...
【Redis】简单了解Redis中常用的命令与数据结构

【Redis】简单了解Redis中常用的命令与数据结构

希望文章能给到你启发和灵感～ 如果觉得文章对你有帮助的话，点赞 关注 收藏 支持一下博主吧～ 阅读指南 开篇说明一、基础环境说明1.1 硬件环境1.2 软件环境 二、Redis的特点和适用场景三、Redis的数据类型和使用3.1字符串（String&…
阅读更多...
谷粒商城实战笔记-24-分布式组件-SpringCloud Alibaba-Nacos配置中心-命名空间与配置分组

谷粒商城实战笔记-24-分布式组件-SpringCloud Alibaba-Nacos配置中心-命名空间与配置分组

文章目录 一，命名空间1，简介1.1，命名空间的主要功能和特点1.2，使用场景1.3，如何指定命名空间 2，命名空间实战2.1，环境隔离2.2，服务隔离 二，配置集三，配置集ID…
阅读更多...
HTML+CSS+JS 实现3D风吹草动效果（B站视频）

HTML+CSS+JS 实现3D风吹草动效果（B站视频）

效果&#xff1a; 代码&#xff1a; <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>3D effect&…
阅读更多...
线下线上游戏电竞陪伴APP小程序H5同城线下约玩APP开发，语聊约玩平台搭建游戏陪玩APP源码

线下线上游戏电竞陪伴APP小程序H5同城线下约玩APP开发，语聊约玩平台搭建游戏陪玩APP源码

开发一款线下陪玩约玩APP的实际意义和在生活中的应用场景 1、满足社交需求:现代社会人们的社交圈往往受到时间、地点和其他限制的影响。线下陪玩约玩APP可以提供一个平台&#xff0c;让用户通过约玩的方式结识新朋友、扩大社交圈 2、解决孤独感:有些人由于工作忙碌、居住环境单…
阅读更多...
MySQL体系架构解析

MySQL体系架构解析

1.MySQL体系架构 1.1.MySQL的分支与变种 MySQL变种有好几个，主要有三个久经考验的主流变种：Percona Server，MariaDB和 Drizzle。它们都有活跃的用户社区和一些商业支持，均由独立的服务供应商支持。同时还有几个优秀的开源关系数据库，值得我们了解一下。 1.1.1.Drizzle …
阅读更多...
YOLOv10改进 | Conv篇 | 利用YOLO-MS的MSBlock轻量化网络结构（既轻量又长点）

YOLOv10改进 | Conv篇 | 利用YOLO-MS的MSBlock轻量化网络结构（既轻量又长点）

一、本文介绍 本文给大家带来的改进机制是利用YOLO-MS提出的一种针对于实时目标检测的MSBlock模块(其其实不能算是Conv但是其应该是一整个模块)&#xff0c;我们将其用于C2f中组合出一种新的结构&#xff0c;来替换我们网络中的模块可以达到一种轻量化的作用&#xff0c;我将其…
阅读更多...
ENSP软件中DHCP的相关配置以及终端通过域名访问服务器

ENSP软件中DHCP的相关配置以及终端通过域名访问服务器

新建拓扑 配置路由器网关IP 设备配置命令&#xff1a;<Huawei> Huawei部分为设备名 <>代表当下所在的模式&#xff0c;不同模式下具有不同的配置权限<Huawei> 第一级模式&#xff0c;最低级模式 查看所有参数<Huawei>system-view 键入系统视图…
阅读更多...
通过 tomcat 让手机访问到电脑写的 html 网页

通过 tomcat 让手机访问到电脑写的 html 网页

之前实现的 html 小项目只能在自己的电脑上展示&#xff0c;如果要在其他电脑或者在手机上就看不到网页了 想要在手机上访问自己写的网页&#xff0c;我们可以借助 tomcat 首先我们可以从官网下载 tomcat 官网链接&#xff1a;apache官网 我们拉到最底部&#xff0c;找到 a…
阅读更多...
C. Earning on Bets

C. Earning on Bets

题目 个人补充&#xff1a; #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 #define ll long longconst int maxn 1e6 5, in…
阅读更多...
Apache Hadoop之历史服务器日志聚集配置

Apache Hadoop之历史服务器日志聚集配置

上篇介绍了Apache Hadoop的分布式集群环境搭建&#xff0c;并测试了MapReduce分布式计算案例。但集群历史做了哪些任务&#xff0c;任务执行日志等信息还需要配置历史服务器和日志聚集才能更好的查看。 配置历史服务器 在Yarn中运行的任务产生的日志数据不能查看&#xff0c;…
阅读更多...
Qt：15.布局管理器(QVBoxLayout-垂直布局、QHBoxLayout-水平布局、QGridLayout-网格布局、拉伸系数，控制控件显示的大小)

Qt：15.布局管理器(QVBoxLayout-垂直布局、QHBoxLayout-水平布局、QGridLayout-网格布局、拉伸系数，控制控件显示的大小)

目录 一、QVBoxLayout-垂直布局&#xff1a; 1.1QVBoxLayout介绍&#xff1a; 1.2 属性介绍&#xff1a; 1.3细节理解&#xff1a; 二、QHBoxLayout-水平布局&#xff1a; 三、QGridLayout-网格布局&#xff1a; 3.1QGridLayout介绍&#xff1a; 3.2常用方法&#xff1a…
阅读更多...
YOLOv10改进 | Conv篇 | 利用CVPR2024-DynamicConv提出的GhostModule改进C2f（全网独家首发）

YOLOv10改进 | Conv篇 | 利用CVPR2024-DynamicConv提出的GhostModule改进C2f（全网独家首发）

一、本文介绍 本文给大家带来的改进机制是CVPR2024的最新改进机制DynamicConv其是CVPR2024的最新改进机制&#xff0c;这个论文中介绍了一个名为ParameterNet的新型设计原则&#xff0c;它旨在在大规模视觉预训练模型中增加参数数量&#xff0c;同时尽量不增加浮点运算&#x…
阅读更多...
MAVAE

MAVAE

1 自动下载项目所需要的jar包&#xff0c;统一管理jar包之间的依赖关系 2完成项目构建 maven的安装与配置 ​ 安装jdk环境&#xff1a;maven的运行需要依赖jdk。 下载maven。官网下载&#xff1a;Maven – Download Apache Maven 将下载的maven压缩包直接解压到本地磁盘即可。…
阅读更多...
最新文章

Copyright @ 2022~2023