LeetCode 热题100——栈与队列专题（三）

一、有效的括号

20.有效的括号（题目链接）

思路：

1）括号的顺序匹配：用栈实现，遇到左括号入，遇到右括号出（保证所出的左括号与右括号对应），否则顺序不匹配。

2）括号的数量匹配：

1>左括号大于右括号：用栈实现，遇到左括号入，遇到右括号出，遍历完字符数组，此时栈不为空，则说明左括号数量大于右括号；

2>右括号大于左括号：遇到右括号出时，判断栈是否为空，若此时栈为空，说明右括号数量大于左括号；

typedef char  SDateType;
typedef struct Stack
{
	SDateType* a;
	int top;
	int capacity;

}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void DestoryStack(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;

}

//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{
	assert(ps);
	//扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
	//尾插
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//只少有一个元素，才能删除
	ps->top--;
}

//栈的有效个数和栈顶元素
int  StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
int   StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

//栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
int isValid(char* s) {
	Stack ps;
	InitStack(&ps);

	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			StackPush(&ps, *s);
			s++;
		}
		else

		{
			if (StackEmpty(&ps))
			{
				return false;
			}
			char tmp = StackTop(&ps);
			StackPop(&ps);
			if ((*s == ']' && tmp != '[') ||
				(*s == '}' && tmp != '{') ||
				(*s == ')' && tmp != '('))
			{
				return false;
			}

			s++;

		}
	}
	if (!StackEmpty(&ps))
	{
		return false;
	}
	else {
		return true;
	}
	DestoryStack(&ps);
}

二、用队列实现栈 

225. 用队列复制栈（题目链接）

 

思路： 栈是后进先出，队列是先进先出。

用俩队列实现栈

1）入栈时，选择有数据的队列入数据；

2）出栈时，将有数据队列中前k-1个数据出队列，并入到空队列中，返回并出有数据队列的最后一个数据

typedef int QDateType;
typedef struct QueueNode
{
	QDateType val;
	struct QueueNode * next;
}QueueNode;
typedef struct Queue
{
	QueueNode *head;
	QueueNode *tail;
	QDateType size;
}Queue;

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

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	
	node->val = x;
	node->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = node;
		pq->size++;
	}
	else
	{
		pq->tail->next = node;
		pq->tail = node;
		pq->size++;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//只少保证一个节点
	QueueNode* del = pq->head;
	pq->head = pq->head->next;
	free(del);
	del = NULL;
	pq->size--;
	if (pq->head == NULL)//只有一个节点处理
	{
		pq->tail = NULL;
	}
}

// 返回队头和队尾
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->head->val;
}
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->tail->val;
}

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}



bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head==NULL;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;

}
typedef struct {
    Queue q1;
     Queue q2;

} MyStack;


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

}

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

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

int myStackTop(MyStack* obj) {
     assert(!myStackEmpty(obj));
    Queue * empty=&obj->q1;
    Queue * nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    return QueueBack(nonempty);
}



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

}

三、用栈实现队列 

225. 用栈实现队列（题目链接）

思路： 栈是后进先出，队列是先进先出。

1）入队列：s1栈用来在栈顶入数据；

2）出队列：s2栈用来出栈顶数据，如果s2为空，则从s1出数据入到s2中去（比如;s1中的数据为1，2，3，入到s2变为3，2，1），再出s2的栈顶数据，这样就满足队列的性质了

 

typedef int  SDateType;
typedef struct Stack
{
	SDateType* a;
	int top;
	int capacity;

}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void DestoryStack(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;

}

//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{
	assert(ps);
	//扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
	//尾插
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//只少有一个元素，才能删除
	ps->top--;
}

//栈的有效个数和栈顶元素
int  StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
int   StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

//栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}



typedef struct {
    Stack s1;
    Stack s2;
    
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue* )malloc(sizeof(MyQueue));
    InitStack(&obj->s1);
    InitStack(&obj->s2);
    return obj;

}

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

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);
}

int myQueuePop(MyQueue* obj) {
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->s2))
    {
       while(!StackEmpty(&obj->s1))
       {
          int tmp= StackTop(&obj->s1);
          StackPush(&obj->s2,tmp);
          StackPop(&obj->s1);
       }
      
    }
     int tmp= StackTop(&obj->s2);
       StackPop(&obj->s2);
       return tmp;
}

int myQueuePeek(MyQueue* obj) {
     assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->s2))
    {
       while(!StackEmpty(&obj->s1))
       {
          int tmp= StackTop(&obj->s1);
          StackPush(&obj->s2,tmp);
          StackPop(&obj->s1);
       }
       
    }
    return StackTop(&obj->s2);
}



void myQueueFree(MyQueue* obj) {
    
   DestoryStack(&obj->s1);
   DestoryStack(&obj->s2);
   free(obj);



}

 四、设计循环队列

622.设计循环队列（题目链接） 

思路一：数组

以front为队列头下标，tail为队列尾下一个元素下标，一共k个数据，开辟k+1个整型大小空间，方便区分队列为空、为满以及一个元素的情况

1）队列为空，front=tail

2）队列为1个元素，front+1=tail

3)   队列为满，（tail+1)%(k+1)==front

 

typedef struct {
    int *a;
    int front;
    int rear;
    int n;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int * tmp=(int *)malloc(sizeof(int)*(k+1));
    obj->a=tmp;
    obj->front=0;
    obj->rear=0;
    obj->n=k;
    return obj;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear+1)%(obj->n+1)==obj->front)
    {
        return true;
    }
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull( obj))
    {
        return false;
    }
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear=obj->rear%(obj->n+1);
    return true;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
    {
        return true;
    }
    return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return false;
    }
    obj->front++;
    obj->front=obj->front%(obj->n+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return  obj->a[(obj->rear-1+obj->n+1)%(obj->n+1)];
}




void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

 

思路二：单向循环链表

以head为队列头节点，tail为队列尾尾节点的下一个节点，一共k个数据，开辟k+1个节点的循环单向链表，方便区分队列为空、为满以及一个元素的情况

1）队列为空，head=tail

2）队列为1个元素，head->next=tail

3)   队列为满，tail->next=head

 

typedef struct QueueNode
{
	int val;
	struct QueueNode * next;
}QueueNode;

QueueNode* BuyNode(int x)
{
    QueueNode* node=(QueueNode*)malloc(sizeof(QueueNode));
    node->val=x;
    node->next=NULL;
    return node;
}
typedef struct MyCircularQueue{
   QueueNode *head;
	QueueNode *tail;
    QueueNode * pretail;
	int n;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    QueueNode* node=BuyNode(0);
    obj->pretail=NULL;
    obj->head=obj->tail=node;
    obj->n=(k+1);
    QueueNode* cur=obj->tail;
    while(k--)
    {
       QueueNode* node=BuyNode(0);
     
      cur->next=node;
        cur= cur->next;
    }
   
   cur->next=obj->head;
    return obj;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->tail->next==obj->head)
    {
        return true;
    }
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull( obj))
    {
        return false;
    }
    obj->tail->val=value;
    obj->pretail=obj->tail;
    obj->tail=obj->tail->next;
   
     
    return true;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->head==obj->tail)
    {
        return true;
    }
    return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return false;
    }
    obj->head=obj->head->next;
   
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return obj->head->val;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return  obj->pretail->val;
}




void myCircularQueueFree(MyCircularQueue* obj) {
   while(obj->n--)
   {
       QueueNode*next=obj->head->next;
       free(obj->head);
       obj->head=next;
   }
   obj->head=NULL;
    free(obj);
}

 

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

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

相关文章

opencv-简单图像处理

opencv-简单图像处理

图像像素存储形式 　对于只有黑白颜色的灰度图，为单通道，一个像素块对应矩阵中一个数字，数值为0到255, 其中0表示最暗（黑色） ，255表示最亮（白色） 对于采用RGB模式的彩色图片&#…
阅读更多...
C++使用Tensorflow2.6训练好的模型进行预测

C++使用Tensorflow2.6训练好的模型进行预测

要在C语言中调用训练好的TensorFlow模型，需要使用TensorFlow C API。 https://tensorflow.google.cn/install/lang_c?hl=zh-cnten TensorFlow 提供了一个 C API，该 API 可用于为其他语言构建绑定。该 API 在 c_api.h 中定义，旨在实现简洁性和一致性，而不是便利性。 下载…
阅读更多...
3.计算机网络

3.计算机网络

1.重点概念 MSL（Maximum segment lifetime）：TCP 报⽂最⼤⽣存时间。它是任何 TCP 报⽂在⽹络上存在的 最⻓时间，超过这个时间报⽂将被丢弃。实际应⽤中常⽤的设置是 30 秒，1 分钟和 2 分钟。 TTL（Time to …
阅读更多...
Qt 基于海康相机的视频绘图

Qt 基于海康相机的视频绘图

需求 在视频窗口上进行绘图，包括圆，矩形，扇形等 效果： 思路： 自己取图然后转成QImage ，再向QWidget 进行渲染，根据以往的经验，无法达到很高的帧率。因此决定使用相机SDK自带的渲染…
阅读更多...
DAY60 84.柱状图中最大的矩形

DAY60 84.柱状图中最大的矩形

84.柱状图中最大的矩形 题目要求：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 思路 单调栈 本地单调栈的解法和接雨水的题目是遥相呼…
阅读更多...
【DevOps】Git 图文详解（七）：标签管理

【DevOps】Git 图文详解（七）：标签管理

Git 图文详解（七）：标签管理 标签（Tags）指的是某个分支某个特定时间点的状态，是对某一个提交记录的 固定 “指针” 引用。一经创建，不可移动，存储在工作区根目录下 .git\refs\tags。可…
阅读更多...
智能座舱架构与芯片- (4) 硬件篇 中

智能座舱架构与芯片- (4) 硬件篇 中

2.4 高速视频传输(GMSL) 为了解决未来汽车系统所面临的问题，美信(Maxim)推出了全新下一代GMSL技术，即吉比特多媒体串行链路(GMSL)串行器和解串器，用来支持未来ADAS和信息娱乐系统要求的宽带、互联复杂度和数据完整性的要求。 GMSL技术可以支…
阅读更多...
Stock接口_节假日(1)

Stock接口_节假日(1)

节假日 文章目录 节假日一. 查询最近十天的交易日日期列表二. 查询日期段内的交易日日期列表三. 查询假期信息 一. 查询最近十天的交易日日期列表 接口描述: 接口地址:/StockApi/holidayCalendar/getTenTradeDay 请求方式：GET consumes: produces:["*/*&q…
阅读更多...
【C++】类和对象一

【C++】类和对象一

今天来到了类和对象部分，我们知道C语言是面向过程编程，而C是面向对象编程，那么怎么个具体实现方法呢？简单来说，就是C语言对结构体的定义和对结构体的操作是分开的，这样就显得过程很独立；而C是把…
阅读更多...
Javaweb之Axios的详细解析

Javaweb之Axios的详细解析

1.3 Axios 上述原生的Ajax请求的代码编写起来还是比较繁琐的，所以接下来我们学习一门更加简单的发送Ajax请求的技术Axios 。Axios是对原生的AJAX进行封装，简化书写。Axios官网是：https://www.axios-http.cn 1.3.1 Axios的基本使用 Axios的…
阅读更多...
知识库文档处理

知识库文档处理

知识库文档处理 1 知识库设计2 文档加载2.1 PDF文档2.2 MD文档2.3 MP4视频 3 文档分割4 文档词向量化 本项目是一个个人知识库助手项目，旨在帮助用户根据个人知识库内容，回答用户问题。个人知识库应当能够支持各种类型的数据，支持用户便捷地导…
阅读更多...
【Java程序员面试专栏 专业技能篇】Java SE核心面试指引（二）：面向对象思想

【Java程序员面试专栏 专业技能篇】Java SE核心面试指引（二）：面向对象思想

关于Java SE部分的核心知识进行一网打尽，包括四部分：基础知识考察、面向对象思想、核心机制策略、Java新特性，通过一篇文章串联面试重点，并且帮助加强日常基础知识的理解，全局思维导图如下所示 本篇Blog为第二部分：面向对象思想，子节点表示追问或同级提问 面向对象基…
阅读更多...
【用unity实现100个游戏之16】Unity程序化生成随机2D地牢游戏3（附项目源码）

【用unity实现100个游戏之16】Unity程序化生成随机2D地牢游戏3（附项目源码）

文章目录 先本文看看最终效果前言二叉空间分割算法房间优先生成使用走廊连接各个房间BSP和随机游走源码完结 先本文看看最终效果 前言 前两期我们使用了随机游走算法已经实现了地牢的生成，本期再说另外一种生成地牢的方法，使用二叉空间分割算法&#xf…
阅读更多...
Git——分布式版本控制工具

Git——分布式版本控制工具

一、概述 1.开发中的实际场景 备份代码还原协同开发追溯问题代码的编写人和编写时间 2.版本控制器的方式 集中式版本控制工具 集中式版本控制工具，版本库是集中存放在中央服务器的，team里每个人work时从中央服务器下载代码，是必须联网才能…
阅读更多...
nodejs微信小程序 +python＋PHP- 校园志愿者管理系统的设计与实现-计算机毕业设计推荐

nodejs微信小程序 +python＋PHP- 校园志愿者管理系统的设计与实现-计算机毕业设计推荐

目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1 1.1背景及意义 1 1.2 国内外研究概况 1 1.3 研究的内容 1 第2章 相关技术 3 2.1 nodejs简介 4 2.2 express框架介绍 6 2.4 MySQL数据库 4 第3章 系统分析 5 3.1 需求分析 5 3.2 系统可行性分析 5 3.2.1技术可行性：…
阅读更多...
Go 语言中 For 循环：语法、使用方法和实例教程

Go 语言中 For 循环：语法、使用方法和实例教程

for循环用于多次执行特定的代码块，每次都可以使用不同的值。每次循环执行都称为一次迭代。for循环可以包含最多三个语句： 语法 for 语句1; 语句2; 语句3 {// 每次迭代要执行的代码 }语句1：初始化循环计数器的值。语句2：对每次循环…
阅读更多...
微信小程序如何使用scss，less

微信小程序如何使用scss，less

搜到很多都是先VSCode安装好…插件…。这都是很久之前的方法了，所以想写这篇文章 一、修改project.config.json配置文件 "setting": {"useCompilerPlugins": ["sass"]},二、然后就可以删除 .wxss 文件了，就用 .scss 文件…
阅读更多...
腾讯极光盒子A4021增强版_线刷官方

腾讯极光盒子A4021增强版_线刷官方

1、用USB_Burning_Tool线刷提供的线刷包，所需资料地址在最后 1）打开USB_Burning_Tool，选择资料里的A4021_line_flash_root.img（文件夹最好没有中文字符和空格），然后点击【开始】。 2）盒子准备好…
阅读更多...
mac添加Chrome插件的方法

mac添加Chrome插件的方法

如果是.crx的插件 更改后缀crx为zip 后续步骤同下文.zip文件 如果是.zip的插件 使用终端进行解压 注意不要用解压工具解压，一定要用终端，命令行解压 // 进入到“插件名.zip”文件的目录下，输入下面命令： unzip 插件名.zip -…
阅读更多...
LeetCode209.长度最小的子数组（滑动窗口法、暴力法）

LeetCode209.长度最小的子数组（滑动窗口法、暴力法）

LeetCode209.长度最小的子数组 1.问题描述2.解题思路3.代码4.知识点 1.问题描述 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] ，并返回其长度。如果…
阅读更多...
最新文章

Copyright @ 2022~2023