leetcode栈和队列三剑客

在这里插入图片描述
用队列实现栈

在这里插入图片描述
队列是先进先出的,而栈是只能在栈顶进行出栈和入栈,那我们这道题要用队列来实现栈的话,这里给的思路是两个队列,因为两个队列的话就可以相互导数据,比如我们来实现这个题目的push函数,我们的栈是只能在栈顶进行操作,那其实插入就也可以在队列的尾部进行插入,但是我们是两个队列,我们不能在空的队列进行插入,这样顺序就会乱,所以我们这里需要做的就是在不是空的队列进行插入操作。

在这里插入图片描述
那如果我们的栈要实现出栈该怎么做呢,我们先来看一下下面的这个图。

在这里插入图片描述
我们这里的出栈不是出第一个元素1,而是想办法把我们这里第一个队列的4出去,那因为队列只能在头上进行pop那我们这里可以先把第一个队列的前三个数据导入到第二个队列中,然会在pop第一个队列就可以了。代码实现就是下面这个图

在这里插入图片描述
我们的队列是始终保持一个是有数据的,一个是为空的,比如我们如果是取栈顶的元素,这里我们是确保取出不为空的队列数据的front,所以这个函数来实现也是特别的简单。

在这里插入图片描述
这道题的整个代码思路就是下面(我们这里用的是C语言,所以要自己实现一个队列)


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;

typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	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 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);







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


}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = data;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;

	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size >= 0);
	assert(q->head != NULL);
	QNode* del = q->head;
	q->head = q->head->next;
	free(del);
	del = NULL;
	if (q->head == NULL)
		q->tail = NULL;
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->head->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->tail->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

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


MyStack* myStackCreate() {
    MyStack* q = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&q->q1);
    QueueInit(&q->q2);
    return q;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if(QueueEmpty(nonempty))
    {
        empty = &obj->q2;
        nonempty = &obj->q1;
    }
    while(QueueSize(nonempty) > 1)
    {
        QueuePush(empty, QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int ret = QueueFront(nonempty);
    QueuePop(nonempty);
    return ret;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
       return QueueEmpty(&obj->q1) &&  QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);

}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

用栈实现队列

在这里插入图片描述
有了前面的思路,我们知道栈的实现是要有两个队列才可以实现的,那同样我们如果要用栈实现队列的话,也得用两个栈来实现,这里我们的两个栈就有主要的区别,我们一个栈可以来当pop栈,还有一个栈可以当成push栈,这样的话,我们就有了分工的作用,后续在插入的时候我们只要在pop栈进行插入就可以了。

那我们先来实现一下我们该怎么初始化,初始化我们直接给两个栈

在这里插入图片描述
这里记住我们去初始化这俩个栈的时候我们是不知道该去怎么初始化,我们直接调用他们的函数就可以了,就不用去记住他们是怎么的一个样子。

在这里插入图片描述
那我们push就需要在push栈中push就可以了

在这里插入图片描述
这里的pop需要注意一些东西
如果popST为空,则将pushST的数据倒过来,就符合先进先出的顺序,如果不为空直接在栈顶进行pop就ok,但是我们这里如果一开始pop为空的,我们需要先把数据倒过来之后才可以进行下一部,我们前面就说过只有pop栈是pop的,push只是push,那我们就要进行判断,然会进行导数据这个操作。

在这里插入图片描述
下一个取出队列的元素,这个就很简单,就是复用上面的代码就可以,只是我们是取出来,不需要进行pop

那这道题就完成了,下面的就口函数我就直接给代码了(这里还是要自己实现一下栈)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

静态实现(固定数组的长度)
//struct Stack
//{
//	int a[N];
//	int top; //栈顶的位置
//};


typedef int  STDataType;
//动态实现(固定数组的长度)
typedef struct Stack
{
	STDataType* a;   //传递数组地址,可以动态的进行扩容
	int top;   //栈顶的位置
	int capacity;   //容量
}ST;

//初始化
void StackInit(ST* ps);

//销毁
void StackDestory(ST* ps);

//压栈
void StackPush(ST* ps, STDataType x);

//出栈
void StackPop(ST* ps);

//判断栈是否为空
bool StackEmpty(ST* ps);

//计算栈的大小
int StackSize(ST* ps);

//初始化
void StackInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;  //初始化top为0,则相当于从栈顶的下一个位置开始,则先赋值,再进行++操作
}


//销毁
void StackDestory(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;

	ps->capacity = 0;
	ps->top = 0;
}

//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	
	//如果当前的空间不够就需要进行扩容
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		//当前的空间等于新的空间的大小
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
	

}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;  //判断它的顶部是否为0

}

//计算栈的大小
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;   //返回栈顶就是元素的个数
}

//获取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	return ps->a[ps->top - 1];   //top是栈顶的下一个元素,想找栈顶元素则进行减一的操作
}

//获取栈顶元素
STDataType StackTop(ST* ps);
typedef struct {
     ST pushST;
     ST popST;

} MyQueue;


MyQueue* myQueueCreate() {
   MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
   assert(obj);
   StackInit(&obj->pushST);
   StackInit(&obj->popST);

   return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST,x);

}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    //如果popST为空,则将pushST的数据倒过来,就符合先进先出的顺序
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }

    }
    int front =  StackTop(&obj->popST);
    StackPop(&obj->popST);

    return front;

}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //如果popST为空,则将pushST的数据倒过来,就符合先进先出的顺序
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }

    }

    return  StackTop(&obj->popST);;

}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);

}

void myQueueFree(MyQueue* obj) {
     assert(obj);
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);

    free(obj);

}
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

后面这个题比前面两道简单一点,是关于栈的。。

有效的括号

在这里插入图片描述
这个题我们用栈来实现,为什么用栈是因为这样时间复杂度就是O(N)我们只要遍历一遍就可以了,但是我们这个题目要知道考什么,一个我们必须数量进行匹配,另一个是顺序匹配,比如左括号( 得和右)进行匹配,所以我们这里需要做的就是左括号这些入栈,然后右括号进行匹配,如果匹配成功的化原来里的括号要进行出栈,然会字符s往后继续++,但是如果有一个括号比右括号不是和我们的左括号匹配的话,我们需要进行的操作就是直接返回false就可以了,如果匹配成功的话出循环就是空栈,所以我们这里就可以直接返回true,但是还是有一个问题就是,在循环里面的时候,会出现越界访问

在这里插入图片描述
越界访问出现的情况就是有右括号,然后没有一个左括号在栈里面,我们这个取top的时候就可以直接返回。

下面是这个题的代码。


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;


void Init(ST* ps);

void Push(ST* ps, STDateType x);

void Pop(ST* ps);

STDateType Top(ST* ps);

void Dstory(ST* ps);

bool Empty(ST* ps);

int Size(ST* ps);


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

void Push(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top + 1 == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* tmp =(STDateType*) realloc(ps->a, sizeof(STDateType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
		ps->top++;

	ps->a[ps->top] = x;

}


void Pop(ST* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	ps->top--;
}


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

STDateType Top(ST* ps)
{
	assert(ps);
	assert(ps->top>=0);
	return ps->a[ps->top];
}


bool Empty(ST* ps)
{
	assert(ps);
	return ps->top == -1;
}




int Size(ST* ps)
{
	assert(ps);
	return ps->top + 1;
}

bool isValid(char* s) {
    ST st;
    Init(&st);
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            Push(&st, *s);
            s++;
        }
        else
        {
					if(Empty(&st))
					{
						return false;
					}
          char top = Top(&st);
					 Pop(&st);
					 if((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{'))
            {
                return false;
            }
            s++;
        }
    }
    if(Empty(&st))
        return true;


    return false;
}

那今天三剑客就分享到这里,我们下次再见。

在这里插入图片描述

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

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

相关文章

根据店铺ID/店铺链接/店铺昵称获取京东店铺所有商品数据接口|京东店铺所有商品数据接口|京东API接口

要获取京东店铺的所有商品数据&#xff0c;您需要使用京东开放平台提供的API接口。以下是一些可能有用的API接口&#xff1a; 商品SKU列表接口&#xff1a;该接口可以获取指定店铺下的所有商品SKU列表&#xff0c;包括商品ID、名称、价格等信息。您可以使用该接口来获取店铺中…

springMvc中的拦截器【巩固】

先实现下想要的拦截器功能 package com.hmdp.utils;import com.hmdp.entity.User; import org.springframework.web.servlet.HandlerInterceptor;import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; import javax.servlet.http.Ht…

python_主动调用其他类的成员

# 主动调用其他类的成员 # 方式一: class Base(object):def f1(self):print("5个功能") class Foo(object):def f1(self):print("3个功能")# Base.实例方法(自己传self),与继承无关Base.f1(self)obj Foo() obj.f1()print("#"*20)# 方式二:按照类…

jbase虚拟M层的设计

对于只是自己产品内部使用的打印程序来说&#xff08;比如打印收费单&#xff0c;打印结算单等&#xff09;&#xff0c;打印逻辑写在js&#xff0c;获取其他层都是没毛病的。但是对于类型检验报告这种打印来说&#xff0c;打印格式控制逻辑写在js层是百分百不行的。因为检验报…

【proverif】proverif的语法-各种密码原语的介绍和具体编码

proverif-系列文章目录 【proverif】proverif的下载安装和初使用【proverif】proverif的语法-解决中间人攻击-代码详解【proverif】proverif的语法2-各种密码原语的编码 &#xff08;本文&#xff09; 文章目录 proverif-系列文章目录前言铺垫知识一、对称加密二、非对称加密三…

大模型幻觉成应用落地难题 最新评测文心一言解决幻觉能力最好

大模型中的幻觉问题 “林黛玉倒拔垂杨柳”、“月球上面有桂树”、“宋江字武松”……相信经常使用大语言模型都会遇到这样“一本正经胡说八道”的情况。这其实是大模型的“幻觉”问题&#xff0c;是大模型行业落地的核心挑战之一。例如幻觉会影响生成内容的可靠性&#xff0c;…

大数据基础设施搭建 - Hadoop

文章目录 一、下载安装包二、上传压缩包三、解压压缩包四、配置环境变量五、测试Hadoop5.1 测试hadoop命令5.2 测试wordcount案例5.2.1 创建wordcount输入文本信息5.2.2 执行程序5.2.3 查看结果 六、分发压缩包到集群中其他机器6.1 分发压缩包6.2 解压压缩包6.3 配置环境变量 七…

TDengine Restful Authorization 自定义Token

Restful 接口是 TDengine 最常用的接口&#xff0c;仅次于 JDBC。TDengine 支持 HTTP 和 HTTPS&#xff0c;但通常情况下&#xff0c;大家不想搞证书&#xff0c;又在内网环境中&#xff0c;采用 HTTP 方式比较多。但 HTTP 是明文传输&#xff0c;只要抓个包就知道账号密码了。…

2.4 矩阵的运算法则

矩阵是数字或 “元素” 的矩形阵列。当矩阵 A A A 有 m m m 行 n n n 列&#xff0c;则是一个 m n m\times n mn 的矩阵。如果矩阵的形状相同&#xff0c;则它们可以相加。矩阵也可以乘上任意常数 c c c。以下是 A B AB AB 和 2 A 2A 2A 的例子&#xff0c;它们都是 …

YOLOv5项目实战(4)— 简单三步,教你按比例划分数据集

前言:Hello大家好,我是小哥谈。本节课就教大家如何去按照比例去划分数据集,希望大家学习之后可以有所收获!~🌈 前期回顾: YOLOv5项目实战(1)— 如何去训练模型 YOLOv5项目

万字长文:从 C# 入门学会 RabbitMQ 消息队列编程

RabbitMQ 简介 RabbitMQ 是一个实现了 AMQP 协议的消息队列&#xff0c;AMQP 被定义为作为消息传递中间件的开放标准的应用层协议。它代表高级消息队列协议&#xff0c;具有消息定位、路由、队列、安全性和可靠性等特点。 目前社区上比较流行的消息队列有 kafka、ActiveMQ、Pul…

freeRTOS--软件定时器

一、什么是定时器&#xff1a; 简单可以理解为闹钟&#xff0c;到达指定一段时间后&#xff0c;就会响铃。STM32 芯片自带硬件定时器&#xff0c;精度较高、达到定时时间后会触发中断&#xff0c;也可以生成 PWM 、输入捕获、输出比较&#xff0c;等等&#xff0c;功能强大&am…

基于黄金正弦算法优化概率神经网络PNN的分类预测 - 附代码

基于黄金正弦算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于黄金正弦算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于黄金正弦优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…

从0开始学习数据结构 C语言实现 1.前篇及二分查找算法

一、前篇 1、什么是数据结构&#xff1f; 数据结构是带有结构特性的数据元素的集合&#xff0c;它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系 2、时间复杂度与空间复杂度 大O符号是用于描述函数渐进行为的数学符号 常用函数的增长表 阶乘O(n!) > 指数…

基于蝠鲼觅食算法优化概率神经网络PNN的分类预测 - 附代码

基于蝠鲼觅食算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于蝠鲼觅食算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于蝠鲼觅食优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…

Spring Boot 中使用 ResourceLoader 加载资源的完整示例

ResourceLoader 是 Spring 框架中用于加载资源的接口。它定义了一系列用于获取资源的方法&#xff0c;可以处理各种资源&#xff0c;包括类路径资源、文件系统资源、URL 资源等。 以下是 ResourceLoader 接口的主要方法&#xff1a; Resource getResource(String location)&am…

VSCode 运行java程序中文乱码

现象描述 java文件中包含中文&#xff0c;运行java程序后&#xff0c;乱码报错。 解决方法 原本运行指令为 cd "d:\programProjects\Java_proj\" ; if ($?) { javac Solution.java } ; if ($?) { java Solution } 需要添加 编码格式 -encoding utf8 cd &quo…

python数据处理作业6:随机生产一个服从正态分布长度为1000的数组,将这个数组划分为25个区间,画出数组的直方图和密度图

每日小语 我只有忘掉自己&#xff0c;才能津津有味地进行沉思和遐想。——卢梭 gpt代码 import numpy as np import matplotlib.pyplot as plt from scipy.stats import norm# 随机生成一个服从正态分布的长度为1000的数组 data np.random.randn(1000)# 划分为25个区间 num_…

【Linux】U盘安装的cfg引导文件配置

isolinux.cfg文件 default vesamenu.c32 timeout 600display boot.msg# Clear the screen when exiting the menu, instead of leaving the menu displayed. # For vesamenu, this means the graphical background is still displayed without # the menu itself for as long …

什么是好用的HR人才测评?

对于HR来说&#xff0c;选用一个合适的测评工具&#xff0c;我想不外乎以下几点&#xff1a; 1、成本可控 不是所有的HR都能申请到足够的资金&#xff0c;去做专业的人才测评&#xff0c;尤其是中小企业&#xff0c;这可是一笔不小 的开支。即使是基层普通岗位的成本&#xf…