栈和队列OJ题讲解

💓博主个人主页:不是笨小孩👀
⏩专栏分类:数据结构与算法👀 刷题专栏👀 C语言👀
🚚代码仓库:笨小孩的代码库👀
⏩社区：不是笨小孩👀
🌹欢迎大家三连关注，一起学习，一起进步！！💓

在这里插入图片描述

OJ题

  • 用队列实现栈
  • 用栈实现队列
  • 设计循环队列

用队列实现栈

在这里插入图片描述

队列是先进先出，而栈是先进后出，那我们怎么用两个队列来实现一个栈呢？

我们想要出数据的话，由于要实现的是栈，所以要后进先出，所以我们需要出4，但是由于他是队列，只能出1，但是我们有两个队列，我们假设队列一中有size个数据，那我们只需要将size-1个都放到另一个队列里面，然后在出掉最后一个就可以了。

在这里插入图片描述

如果需要入数据的话，我们就在不为空的那个队列后面入数据。
大概思想知道以后，我们就可以上手写代码了。（由于C语言没有队列，所以我们需要先拷贝一份我们之前写好的队列）

typedef int QDataType;

typedef struct QNode
{
	QDataType date;
	struct QNode* next;
}QNode;


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDataType x);

//出队列
void QueuePop(Queue* pq);

//获取队头的元素
QDataType QueueFront(Queue* pq);

//获取队头尾的元素
QDataType QueueBack(Queue* pq);

//获取队列中有效数据的个数
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//销毁队列
void QueuDestroy(Queue* pq);

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

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->date = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}	

	pq->size--;
}

//获取队头的元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->date;
}

//获取队头尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->date;
}

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

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

//销毁队列
void QueuDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;

}

//上面是我们自己的队列
//
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) 
{
	//Push到不为空的队列中
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) 
{
	//假设q1不为空
	Queue* noEmpty = &obj->q1;
	Queue* Empty = &obj->q2;
	//如果假设错误，修改
	if(QueueEmpty(&obj->q1))
	{
			noEmpty = &obj->q2;
			Empty = &obj->q1;
	}
	//到数据
	int x = QueueFront(noEmpty);
	while(noEmpty->size>1)
	{
			QueuePush(Empty,x);
			QueuePop(noEmpty);
			x = QueueFront(noEmpty);
	}
	//此时x就保存了最后一个数据，pop掉，返回就可以
	QueuePop(noEmpty);
	return x;
}

int myStackTop(MyStack* obj) 
{
	//返回不为空的队列的尾
	if(QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q2);
	}
	else
	{
		return QueueBack(&obj->q1);
	}
}

bool myStackEmpty(MyStack* obj) 
{
	//两个队列都为空，栈才为空
	return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

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

本题逻辑比较简单，但是结构很强，需要好好理解消化。

用栈实现队列

在这里插入图片描述

这个题和第一个题很相似，是用两个栈实现一个队列。

那这又怎么操作呢？

我们同样push数据时，如果两个都为空的话都可以push，但是如果出数据的话，由于需要先进先出，所以需要将不为空的那个栈的数据放到另一个栈中。

在这里插入图片描述

接下来另一个栈的数据是不是就满足我们需要的顺序了，正好1先进的1先出，接着是2,3,4,那如果没出的话接着push数据呢，我们只需要将数据还push到原来的呢个栈，这是我们不难发现只要当第二个栈的数据出完之后，然后将原本那个栈的数据倒过来就可以了。这个个队列不一样的是，不用每次都倒数据，我们可以将第一个栈叫push栈，第二个栈叫pop栈，然后当pop栈为空时，就将数据倒过来，接着出就可以了，如果两个栈都空了，那说明我们的队列就空了。

代码如下;

typedef int STDateType;

typedef struct Stack
{
	STDateType* arr;
	int top;
	int capacity;
}Stack;

// 初始化栈
void StackInit(Stack* ps);

// 入栈
void StackPush(Stack* ps, STDateType x);

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

// 获取栈顶元素
STDateType StackTop(Stack* ps);

// 获取栈中有效元素个数
int StackSize(Stack* ps);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);

// 销毁栈
void StackDestroy(Stack* ps);

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

// 入栈
void StackPush(Stack* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));
		if (ps == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = pa;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top] = x;
	ps->top++;
}

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

// 获取栈顶元素
STDateType StackTop(Stack* ps)
{
	assert(ps);

	return ps->arr[ps->top - 1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

// 检测栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0 ? true : false;
}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//我们自己的栈
/
typedef struct 
{
    Stack Stackpush;
    Stack Stackpop;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* obj= (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->Stackpush);
    StackInit(&obj->Stackpop);
    return obj;
}

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

int myQueuePeek(MyQueue* obj) 
{
	//如果Pop栈为空就倒数据
    if(StackEmpty(&obj->Stackpop))
    {
        while(!StackEmpty(&obj->Stackpush))
        {
            StackPush(&obj->Stackpop,StackTop(&obj->Stackpush));
            StackPop(&obj->Stackpush);
        }
    }
    return StackTop(&obj->Stackpop);
}

int myQueuePop(MyQueue* obj) 
{
    //调用返回队头的元素，并且判断了Pop栈是否为空
    int x = myQueuePeek(obj);
    StackPop(&obj->Stackpop);
    return x;
}



bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->Stackpop)&&StackEmpty(&obj->Stackpush);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->Stackpop);
    StackDestroy(&obj->Stackpush);
    free(obj);
}

这两个题逻辑非常简单，但是都对我们对结构的了解有很大的挑战。

设计循环队列

在这里插入图片描述

循环队列我们也可以用数组实现，也可以用链表实现，但是使用链表我们构造链表也是一件很麻烦的事情，而且当队列满时和队列空时情况一样，我们会很难区分，但是用链表也是可以实现的，但是我们这里介绍用数组实现。

我们这里需要K个空间，但是我们多开一个空间不存储数据，方便我们来区别空和满的情况。

在这里插入图片描述
我们可以看到空队列时front是和rear相等的。

在这里插入图片描述
当满队列时rear+1就等于front了。

设计这个循环队列，当rear超过K+1是我们就要让他回到0出，我们可以用if判断，也可以用取模操作。我们入数据就在rear位置入，出数据只需要将front++就可以了但是front也可能会越界。所以也需要取模操作。

在这里插入图片描述
这种情况front就可能越界，所以在写代码是要控制好边界。

代码如下：

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


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


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++;
    //防止front越界
    obj->front = obj->front%(obj->k+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;
    }
   //obj->read==0的话应该是返回k那个位置的
    return obj->rear==0?obj->a[obj->k]:obj->a[obj->rear-1];
}


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

今天的分享就到这里结束了，感谢大家的关注和支持。

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

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

相关文章

vue3多条件搜索功能

vue3多条件搜索功能

搜索功能在后台管理页面中非常常见&#xff0c;本篇就着重讲一下vue3-admin-element框架中如何实现一个顶部多条件搜索功能 一、首先需要在vue页面的<template></template>中写入对应的结构 <!-- 搜索 --><div style"display: flex; justify-content…
阅读更多...
【大数据】Flink 从入门到实践（一）：初步介绍

【大数据】Flink 从入门到实践（一）：初步介绍

Flink 从入门到实践&#xff08;一&#xff09;&#xff1a;初步介绍 Apache Flink 是一个框架和分布式处理引擎&#xff0c;用于在 无边界 和 有边界 数据流上进行 有状态 的计算。Flink 能在所有常见集群环境中运行&#xff0c;并能以内存速度和任意规模进行计算。 1.架构 1…
阅读更多...
[mongo]应用场景及选型

[mongo]应用场景及选型

应用场景及选型 MongoDB 数据库定位 OLTP 数据库横向扩展能力&#xff0c;数据量或并发量增加时候架构可以自动扩展灵活模型&#xff0c;适合迭代开发&#xff0c;数据模型多变场景JSON 数据结构&#xff0c;适合微服务/REST API基于功能选择 MongoDB 关系型数据库迁移 从基…
阅读更多...
测试人员该怎样写软件缺陷报告？

测试人员该怎样写软件缺陷报告？

软件测试过程中&#xff0c;每个公司都制订了软件的缺陷处理流程&#xff0c;每个公司的软件缺陷处理流程不尽相同&#xff0c;但是它们遵循的最基本流程是一样的&#xff0c;都要经过提交、分配、确认、处理、复测、关闭等环节&#xff0c;如图1所示。 缺陷处理流程 关于图1所…
阅读更多...
Windows环境下通过 系统定时 执行脚本方式 压缩并备份文件夹 到其他数据盘

Windows环境下通过 系统定时 执行脚本方式 压缩并备份文件夹 到其他数据盘

环境配置 压缩时需要使用7-zip进行调用&#xff0c;因此根据自己电脑进行安装 官网&#xff1a;https://www.7-zip.org/ 脚本文件 新建记事本文件&#xff0c;重命名为git_back_up.bat echo off rem 设置utf-8可以正常显示中文 chcp 65001 > nulrem 获取当前日期和时间&…
阅读更多...
系统架构设计师-系统可靠性分析与设计

系统架构设计师-系统可靠性分析与设计

目录 一、可靠性相关基本概念 二、可靠性指标 1、串联系统与并联系统可靠性指标计算 2、混合系统 三、可靠性设计 1、影响软件可靠性的主要因素&#xff1a; 2、增加可靠性的解决方案 2.1 避错技术 2.2 降低复杂度设计 2.3 检错技术 2.4 容错技术 3、双机容错 一、可靠性相关…
阅读更多...
【算法|数组】滑动窗口

【算法|数组】滑动窗口

算法|数组——滑动窗口 引入 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度**。**如果不存在符合条件的子数组&#xff0c;返回 0 。 示例…
阅读更多...
Vue [Day5]

Vue [Day5]

自定义指令 全局注册 和 局部注册 inserted在指令所在的元素 被插入到页面中时&#xff0c;触发 main.js import Vue from vue import App from ./App.vueVue.config.productionTip false// 1.全局注册指令 Vue.directive(focus, {// inserted在指令所在的元素 被插入到页…
阅读更多...
机器学习中训练数据的重要性

机器学习中训练数据的重要性

人工智能技术发展至今&#xff0c;训练数据的重要性已经是我们老生常谈的问题。在重声训练数据为什么重要之前&#xff0c;我们先重新回顾下AI技术大爆炸的三大初始概念&#xff1a;机器学习是什么&#xff1f;人工智能是什么&#xff1f;训练数据又是什么&#xff1f; 机器学…
阅读更多...
阿里云内容审核服务使用（图片审核）

阿里云内容审核服务使用（图片审核）

说明&#xff1a;在项目中&#xff0c;我们经常会对用户上传的内容&#xff08;如文字、图片&#xff09;等资源内容进行审核&#xff0c;审核包括两方面&#xff0c;一方面是内容与描述不符&#xff0c;一方面是违反法律法规。本文介绍使用阿里提供的内容审核服务&#xff0c;…
阅读更多...
4、Rocketmq之存储原理

4、Rocketmq之存储原理

CommitLog ~ MappedFileQueue ~ MappedFile集合 正常情况下&#xff0c;RocketMQ支持消息体字节数最多为1个G。注意该消息体并不单单是消息体body。如果生产的消息其字节数超过1个G则该消息是无法被落盘处理的。因为没有一个MapperFile文件可以承载该消息所有的字节数。 1.All…
阅读更多...
智慧工地源码 智慧工地云平台源码 智慧工地APP源码

智慧工地源码 智慧工地云平台源码 智慧工地APP源码

智慧工地的核心是数字化&#xff0c;它通过传感器、监控设备、智能终端等技术手段&#xff0c;实现对工地各个环节的实时数据采集和传输&#xff0c;如环境温度、湿度、噪音等数据信息&#xff0c;将数据汇集到云端进行处理和分析&#xff0c;生成各种报表、图表和预警信息&…
阅读更多...
windows10开启远程连接

windows10开启远程连接

目录 开启远程连接远程连接 开启远程连接 右击电脑图标->属性 点击 远程设置 远程连接 找到 远程桌面连接 点击 远程桌面连接 输入远程ip 10.0.8.5 然后点击连接 4.输入默认用户名new的密码&#xff0c;然后确定&#xff0c;搞定。
阅读更多...
网络加速与文件传输软件：如何通过优化网络提升文件传输速度

网络加速与文件传输软件：如何通过优化网络提升文件传输速度

在信息化社会&#xff0c;文件传输是人们生活和工作中必不可少的一个环节。但是&#xff0c;由于网络环境的多样性和传输过程中可能出现的各种问题&#xff0c;文件传输速度经常受到影响。因此&#xff0c;如何优化网络以提高文件传输速度成为了一个重要的课题。本文将探讨网络…
阅读更多...
SQL SERVER 异地备份到远程共享文件夹异常处理

SQL SERVER 异地备份到远程共享文件夹异常处理

SQL SERVER 异地备份到远程共享文件夹异常处理 SQL Server 异地备份到远程共享文件夹异常处理 - 灰信网&#xff08;软件开发博客聚合&#xff09; -- 允许配置高级选项 EXEC sp_configure show advanced options, 1 GO -- 重新配置 RECONFIGURE GO -- 启用xp_cmdshell EXEC sp…
阅读更多...
正则表达式的使用

正则表达式的使用

1、正则表达式-教程 正则表达式&#xff1a;文本模式&#xff0c;包括普通字符&#xff08;例如&#xff0c;a到z之间的字母&#xff09;和特殊字符&#xff08;称为元字符&#xff09;。 正则表达式使用单个字符串来描述&#xff0c;匹配一系列匹配某个句法规则的字符串。 2、…
阅读更多...
如何卸载SOLIDWORKS软件？

如何卸载SOLIDWORKS软件？

本文将为您提供一份简易指南&#xff0c;介绍如何正确卸载SOLIDWORKS软件&#xff0c;并分享一些注意事项&#xff0c;确保您的卸载过程顺利进行。 SOLIDWORKS软件作为一款强大的三维设计和工程分析工具&#xff0c;为许多工程师提供了优良的创作平台。然而&#xff0c;有时候我…
阅读更多...
Redis-简单动态字符串(SDS)

Redis-简单动态字符串(SDS)

文章目录 文章概要SDS数据结构定义SDS和C字符串的区别总结参考 文章概要 本篇文章&#xff0c;我们来学习Redis字符串的编码格式SDS编码&#xff0c;文章将将从以下几个方面介绍SDS&#xff1a; SDS的底层数据结构定义Redis是C写的&#xff0c;那SDS和C中的字符串的区别是什么…
阅读更多...
OpenMV 自适应颜色阈值

OpenMV 自适应颜色阈值

目录 演示视频 思路讲解 OprnMV代码 演示视频 备战2023电赛~openmv自适应颜色阈值&#xff08;附源代码网盘链接&#xff09; 思路讲解 1. 参考openmv官方例程讲解10-Color-Tracking->image_statistics_info图像统计信息https://book.openmv.cc/example/10-Color-Trackin…
阅读更多...
【Linux】gcc编译器的使用和介绍

【Linux】gcc编译器的使用和介绍

目录 一&#xff0c;GCC简介 二&#xff0c;GCC的主要组件 三&#xff0c;GCC的工作流程 四&#xff0c;GCC的一些重要特性和功能 五&#xff0c;GCC常用的编译选项 六&#xff0c;GCC的输入输出选项的具体用法 七&#xff0c;GCC的参考文档 一&#xff0c;GCC简介 GCC&…
阅读更多...
最新文章

Copyright @ 2022~2023