数据结构-栈和队列力扣题

目录

有效的括号

用队列实现栈

 用栈实现队列

 设计循环队列

有效的括号

题目链接：力扣（LeetCode）

思路： 这道题可以用栈来解决，先让字符串中的左括号' ( '，' [ '，' { '入栈，s指向字符串下一个字符，如果该字符也是左括号，那就继续入栈，如果是右括号，那就让其与栈顶元素相匹配（每次都要弹出栈顶元素），匹配上了，继续循环，匹配不上就返回false，注意在每次返回false之前都要销毁栈。

还要考虑极端情况，如果全是左括号，我们要在代码最后进行判空，不为空，返回false，同时，这次判空也能解决前面几对都匹配上，只有最后一个左括号没匹配上的问题（例如："()[]{}{"）。

如果全是右括号，说明整个过程中没有入栈元素，此时判空，如果为空返回false，同时，这次判空也能解决前面几对都匹配上，只有最后一个右括号没匹配上的问题（例如："()[]{}}"）。

如果用C语言来解题的话，栈需要自己写。

代码如下：

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

//初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

//入栈
void STPush(ST* pst, STDatatype x)
{
	//开辟空间
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//插入
	pst->a[pst->top] = x;
	pst->top++;
}
//判空函数
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
//获取栈顶元素
STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
//获取栈中有效数据的个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//销毁栈
void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}


bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {

        if(*s=='('||*s=='['||*s=='{')
        {
            STPush(&st,*s);
        }

        else
        {

            if(STEmpty(&st))
			{
			   STDestory(&st);
               return false;
			}


			char top=STTop(&st);
			STPop(&st);
						
            if((top!='('&&*s==')')
              ||(top!='['&&*s==']')
              ||(top!='{'&&*s=='}'))
            {

                STDestory(&st);
                return false;
            
            }
        }
				 ++s;
    }

	bool ret=STEmpty(&st);
	STDestory(&st);
    return ret;
}

用队列实现栈

题目链接：力扣（LeetCode）

 思路：队列是先入先出，栈是先入后出，要用队列实现栈，我们可以定义两个栈q1和q2，当它们都为空时，随便选一个存入数据，假设q1中有数据1 2 3 4，我们可以把q1中的1 2 3 push进q2中，然后把q1中的4 pop出去，接着把q2中的1 2 push进q1，然后把q2中的3 pop出去，这样循环在q1和q2中倒数据，就实现了4 3 2 1依次出栈，即先入后出。

当我们在出栈的同时，想要入栈，就把数据push进有数据的队列即可。

想要用C语言做这道题，队列的实现代码也要自己写。

注意，我们下列代码是结构体的三层嵌套，所以销毁时要先销毁q1和q2，再销毁obj，如果只销毁obj，由于我们的队列q1和q2中分别有两个头尾指针还有节点，会造成内存泄漏的问题。

它们的关系图如下：

代码如下：

typedef int QDatatype;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

//队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->phead = pq->ptail=newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

//判空函数
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size ==0 ;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个节点
	//多个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail= NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

//获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

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

//销毁队列
void DestoryQueue(Queue* pq)
{
	assert(pq);
	while (pq->phead)
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}


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


MyStack* myStackCreate() {

    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));

    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    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);
    }
}

int myStackPop(MyStack* obj) {

    Queue* pemptyq=&obj->q1;
    Queue* pnoemptyq=&obj->q2;

    if(!QueueEmpty(&obj->q1))
    {
        pemptyq=&obj->q2;
        pnoemptyq=&obj->q1;
    }

    while(Queuesize(pnoemptyq)>1)
    {
        QueuePush(pemptyq,QueueFront(pnoemptyq));
		QueuePop(pnoemptyq);
    }

    int top=QueueFront(pnoemptyq);
    QueuePop(pnoemptyq);
    return top;

}

int myStackTop(MyStack* obj) {

    if(!QueueEmpty(&obj->q1))
        return QueueBack(&obj->q1);
	else
		return QueueBack(&obj->q2);

}

bool myStackEmpty(MyStack* obj) {

    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) {

   	DestoryQueue(&obj->q1);
	DestoryQueue(&obj->q2);
    free(obj);
}

 用栈实现队列

题目链接：力扣（LeetCode）

思路：这道题用上道题的思路也能实现，但是过于复杂。

简单思路：我们定义两个栈pushst和popst，栈中数据遵循先入后出的原则，如果在pushst中push进去1 2 3 4，那他从栈顶到栈底依次是 4 3 2 1 ，但是如果我们把pushst中的数据再push进popst中，那popst中从栈顶到栈底依次是 1 2 3 4，此时我们只要将popst中的数据按照栈本身先入后出的原则pop出去，就是1 2 3 4，这样就实现了先入先出。如下图：

当我们在出队列的同时，想要入队列，要先等popst中的数据出完才行，所以当popst为空，pushst不为空时，才能把pushst中的数据往popst中push。

代码如下：

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

//初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

//入栈
void STPush(ST* pst, STDatatype x)
{
	//开辟空间
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//插入
	pst->a[pst->top] = x;
	pst->top++;
}
//判空函数
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
//获取栈顶元素
STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
//获取栈中有效数据的个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
//销毁栈
void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

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

int myQueuePop(MyQueue* obj) {
   int front= myQueuePeek(obj);
   STPop(&obj->popst);
   return front;
}

int myQueuePeek(MyQueue* 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) {
    STDestory(&obj->pushst);
    STDestory(&obj->popst);
    free(obj);
}

 设计循环队列

题目链接：力扣（LeetCode）

思路： 本题用数组队列和链表队列都能实现，在这里我们使用数组队列，首先，要设计一个循环队列，我们就要知道队列什么时候满，什么时候空，空很容易判断，当front=rear时就为空，问题是当我们循环一圈以后，队列已经满了，但此时front也等于rear，所以为了不发生混淆，我们在开辟空间时多开辟一块，假设要存7个数据就开辟8个空间：

此时当rear+1==front时就为满。但这只是上图为了形象展示，实际上在数组中，每存一个数，rear++，但是数组首尾并没有相连，不能用rear+1==front判断是否满了，我们可以用下标rear，当(rear+1)%(k+1)==front时就说明队列满了。

而要在队列中插入数据，每次插入之后下标rear++，但是当队列满了之后，rear就是数组中最后一个下标，这时如果我们在队头出了两个数据，想再往队列里插数据，就要让rear回到开始的位置，所以每次rear++后，让rear=rear%(k+1)，此时再插入，就形成了一个完美的循环，同理，删除数据也一样，每次删完都让front=front%(k+1)。

obj->a[(obj->rear+obj->k)%(obj->k+1)]这段代码是为了返回队尾元素。

代码如下：

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


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

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

    return obj->front==obj->rear;
}

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

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

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

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

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

栈与队列的内容到这里就结束了，下节开始学习堆与二叉树，

未完待续。。。 

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

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

相关文章

U-Mail信创邮件系统解决方案

U-Mail信创邮件系统解决方案

近年来，在国家政策的大力引导和自身数字化转型需求驱动下，国产化成为国内数字化发展道路上的关键词，企业不断加强自主创新能力，进行信创建设，实现软硬件系统国产化替代，已成为大势所趋。邮件系统作为企业管…
阅读更多...
代码随想录训练营Day1:二分查找与移除元素

代码随想录训练营Day1:二分查找与移除元素

本专栏内容为：代码随想录训练营学习专栏，用于记录训练营的学习经验分享与总结。 文档讲解：代码随想录 视频讲解：二分查找与移除元素 💓博主csdn个人主页：小小unicorn ⏩专栏分类：C &#x1f69a…
阅读更多...
某卢小说网站登录密码逆向

某卢小说网站登录密码逆向

js逆向，今晚找了一个小说网站，分析一下登录密码的解密逆向过程，过程不是很难，分享下 学习网站aHR0cHM6Ly91LmZhbG9vLmNvbS9yZWdpc3QvbG9naW4uYXNweA 这个就是加密后的密码，今晚就逆向它，其他参数暂时不研究…
阅读更多...
python+pytorch人脸表情识别

python+pytorch人脸表情识别

概述 基于深度学习的人脸表情识别，数据集采用公开数据集fer2013，可直接运行，效果良好，可根据需求修改训练代码，自己训练模型。 详细 一、概述 本项目以PyTorch为框架，搭建卷积神经网络模型，训…
阅读更多...
【中间件篇-Redis缓存数据库02】Redis高级特性和应用(慢查询、Pipeline、事务、Lua)

【中间件篇-Redis缓存数据库02】Redis高级特性和应用(慢查询、Pipeline、事务、Lua)

Redis高级特性和应用(慢查询、Pipeline、事务、Lua) Redis的慢查询 许多存储系统（例如 MySQL)提供慢查询日志帮助开发和运维人员定位系统存在的慢操作。所谓慢查询日志就是系统在命令执行前后计算每条命令的执行时间，当超过预设阀值,就将这条命令的相关…
阅读更多...
腾讯云双11优惠活动有哪些？详细攻略来了！

腾讯云双11优惠活动有哪些？详细攻略来了！

2023年腾讯云双11大促活动正在火热进行中，百款热门云产品11.11云上盛惠，领折上折代金券最高再省9999元，助力开发者轻松上云！ 一、腾讯云双11活动入口 活动地址：点此直达 二、腾讯云双11活动时间 即日起至2023-11-30…
阅读更多...
基于SSM的电动车上牌管理系统设计与实现

基于SSM的电动车上牌管理系统设计与实现

末尾获取源码 开发语言：Java Java开发工具：JDK1.8 后端框架：SSM 前端：采用JSP技术开发 数据库：MySQL5.7和Navicat管理工具结合 服务器：Tomcat8.5 开发软件：IDEA / Eclipse 是否Maven项目&#x…
阅读更多...
2012年计网408

2012年计网408

第33题 在 TCP/IP 体系结构中, 直接为 ICMP 提供服务的协议是()A. PPPB. IPC. UDPD. TCP 本题考察TCP/IP体系结构中直接为ICMP协议提供服务的协议。如图所示。这是TCP/IP的四层体系结构。网际层的IP协议是整个体系结构中的核心协议，用于网络互联。网际控制报文协议…
阅读更多...
MongoDB副本集特点验证

MongoDB副本集特点验证

MongoDB副本集特点验证 mogodb副本集概述副本集搭建副本集结构验证结果源码地址 mogodb副本集概述 MongoDB副本集是将数据同步在多个服务器的过程。 复制提供了数据的冗余备份，并在多个服务器上存储数据副本，提高了数据的可用性， 并可以保证…
阅读更多...
To create the 45th Olympic logo by using CSS

To create the 45th Olympic logo by using CSS

You are required to create the 45th Olympic logo by using CSS. The logo is composed of five rings and three rectangles with rounded corners. The HTML code has been given. It is not allowed to add, edit, or delete any HTML elements. 私信完整源码 <!DOCT…
阅读更多...
MFC-TCP网络编程服务端-Socket

MFC-TCP网络编程服务端-Socket

目录 1、通过Socket建立服务端&#xff1a; 2、UI设计&#xff1a; 3、代码的实现&#xff1a; &#xff08;1&#xff09;、CListenSocket类 &#xff08;2&#xff09;、CConnectSocket类 &#xff08;3&#xff09;、CTcpServerDlg类 1、通过Socket建立服务端&#xff…
阅读更多...
分享一本让你真正理解深度学习的书

分享一本让你真正理解深度学习的书

关注微信公众号&#xff1a;人工智能大讲堂&#xff0c;后台回复udl获取pdf文档。 今天要分享的书是Understanding Deep Learning&#xff0c;作者是西蒙普林斯&#xff0c;英国巴斯大学的荣誉教授&#xff0c;其个人学术能力相当强大&#xff0c;在AI领域有着深厚的学术造诣。…
阅读更多...
网络唤醒（Wake-on-LAN, WOL)

网络唤醒（Wake-on-LAN, WOL)

远程唤醒最简单的方法&#xff1a;DDNSTOOpenwrt网络唤醒&#xff0c;完美实现。 原帖-远程唤醒_超详细windows设置远程唤醒wol远程连接&#xff08;远程开机&#xff09; WOL Web# 访问 Wake on Lan Over The Interweb by Depicus 可以无需借助软件很方便的从网页前端唤醒远…
阅读更多...
MATLAB / Simulink HDL 快速入门

MATLAB / Simulink HDL 快速入门

MATLAB / Simulink HDL 快速入门 我们将使用实例讲解MATLAB / Simulink HDL 使用入门。 开始这个项目&#xff0c;首先需要创建一个包含 Stateflow 的新 Simulink 。只需单击画布中的任意位置并开始输入 Stateflow。 此时应该能在画布上看到 Stateflow 图标。双击图标进行编辑。…
阅读更多...
使用xlwings获取excel表的行和列以及指定单元格的值

使用xlwings获取excel表的行和列以及指定单元格的值

import xlwings as xw app xw.App(visibleFalse) # 隐藏Excel wb app.books.open(文档1.xlsx) # 打开工作簿sht wb.sheets[Sheet1] # 实例化工作表1#获取行数和列数 rows_countsht.range(1, 1).expand().shape[0] cols_countsht.range(1, 1).expand().shape[1] print(row…
阅读更多...
Unity 利用UGUI制作圆形进度条

Unity 利用UGUI制作圆形进度条

在Unity中使用Image和Text组件就可以制作简单的进度条。 1、首先准备好一张环状的PNG图&#xff0c;如下图。 2、把该图导入Unity中并转换成精灵。 3、在场景中创建Image和Text组件&#xff0c;并把上图中的精灵拖到Image的Source Image中&#xff0c;其中Image组件中的Image …
阅读更多...
数据采集中的基本参数

数据采集中的基本参数

分辨率(resolution) 分度数量越多则分辨率越高&#xff0c;测量精度也越高 区间(range) 模数转换所能处理模拟信号电平的极限 应尽量使输入与此区间匹配&#xff0c;物尽其用 信号极限幅度集合 所测信号的最大值和最小值 应与输入信号的最大值和最小值相接近 LSB 最低有效…
阅读更多...
[云原生案例2.2 ] Kubernetes的部署安装 【单master集群架构 ---- （二进制安装部署）】网络插件部分

[云原生案例2.2 ] Kubernetes的部署安装 【单master集群架构 ---- （二进制安装部署）】网络插件部分

文章目录 1. Kubernetes的网络类别2. Kubernetes的接口类型3. CNI网络插件 ---- Flannel的介绍及部署3.1 简介3.2 flannel的三种模式3.3 flannel的UDP模式工作原理3.4 flannel的VXLAN模式工作原理3.5 Flannel CNI 网络插件部署3.5.1 上传flannel镜像文件和插件包到node节点3.5.…
阅读更多...
springboot内容协商

springboot内容协商

1.基于请求头 Accept: application/json Accept: application/xml Accept: application/xxx 自定义数据 发的请求头的数据类型 期望返回的数据类型 2.通过请求参数 例如 /football?formatjson 一般respondbody 默认以json方式进行返回 如何请求同一个接口&#xff0c;可以…
阅读更多...
软件测试Triangle练习题

软件测试Triangle练习题

软件测试Triangle练习题 待测类如下： package net.mooctest; public class Triangle {protected long lborderA = 0;protected long lborderB = 0;
阅读更多...
最新文章

Copyright @ 2022~2023