栈与队列OJ题【括号适配问题】【用队列实现栈】【用栈实现队列】【设计循环队列】

 一.有效的括号

​​​OJ链接

 这一道题我们就可以用栈来解决：

不了解栈的可以看我的上一篇博客。

typedef char STDataType;
//用数组来实现栈
typedef struct stack
{
	STDataType* a;
	int capacity;
	int top;
}ST;
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
    pst->capacity = 0;
	//在后面往栈里面放元素的时候，最后的top是在栈顶的下一个位置
	pst->top = 0;
	//如果是-1，那么代表的就是下标
	//pst->top = -1;
}
void STDestory(ST* pst)
{
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)//如果top的数值刚好等于栈的总容量，那么栈就是满了,包含为0的情况。
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);//用realloc改变我们申请动态存储空间的大小
		if (tmp == NULL)
		{
			perror("STPush::relloc");
			return;
		}
		pst->a = tmp;//成功改变了空间，就赋值给栈里的a。
	
		pst->capacity = newcapacity;//总体的容量也随之变化。

	}
	pst->a[pst->top] = x;
	pst->top++;//因为我们的top的栈顶的位置，所以在每一次赋值完毕后就递增。
}

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

//读取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[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 p;
    STInit(&p);//初始化栈
    int sz=strlen(s);//求出栈里的总元素
    for(int i=0;i<sz;i++)
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')
        {
            STPush(&p,s[i]);//如果与三种左括号匹配上了，就入栈
        }
        else//否则就是右括号的情况
        {
            if(STEmpty(&p))//这里有一个判空，目的就是我们的栈里必须要有左括号，不然我们已经进入else了，这里就只有可能是右括号，而这个右括号就不可能与左括号匹配上了
            {
                STDestory(&p);//如果进入了这个if语句，就说明不可能匹配上了
                return false;
            }
            char top=STTop(&p);//取出都是左括号栈里的头栈元素
            STPop(&p);
            if((top=='('&&s[i]!=')')
            ||(top=='['&&s[i]!=']')
            ||(top=='{'&&s[i]!='}'))
            {
                STDestory(&p);//这个if语句就是，虽然栈里有左括号，同时也匹配到了右括号，但是括号直接不匹配的问题
                return false;
            }
        }
    }
    bool ret=STEmpty(&p);//如果栈为空了，就是说所以的括号都匹配上了
    STDestory(&p);
    return ret;
}

这个题主要需要注意的地方就是我们入栈入的都是左括号，右括号就单独的一个一个的与栈里的左括号相匹配。总的来说不算难，就是让我们了解一下栈的应用。

二.用队列实现栈

OJ链接

 简单的说呢，就是我们使用队列的先进先出的特点来完成栈的先进后出的特点。对于队列不熟悉的朋友，也可以看我们上一篇博客。

//先来完成队列的实现
typedef int QDataType;
typedef struct QNode//我们用链表来实现队列
{
	QDataType val;
	struct QNode* next;
}QNode;
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//队列初始化
void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//队列的销毁
void QDestroy(Queue* pq)
{
	assert(pq);
	QNode* pcur = pq->phead;
	while (pcur)//遍历整个链表
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队
void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;
	if (pq->size == 0)//链表没有节点
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;//用size记录链表节点的个数，也就是队列里元素的个数
}
//出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);//出队列之前队列里一定要有元素

	if (pq->phead == pq->ptail)//一个节点
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else//多个节点
	{
		QNode* pcur = pq->phead->next;
		free(pq->phead);
		pq->phead = pcur;
	}
	pq->size--;//出一个，减一个
}
//取队头元素
QDataType QTop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
//取队尾元素
QDataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
//求队列里元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
//判空
bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

//开始写题
typedef struct {
	Queue q1;
	Queue q2;
} MyStack;//创建两个队列

//初始化栈
MyStack* myStackCreate()
{
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QInit(&(pst->q1));
	QInit(&(pst->q2));//因为pst->q是队列，所以调用上面写的初始化队列的函数
	return pst;
}
//入栈
void myStackPush(MyStack* obj, int x) {
	if (!QEmpty(&(obj->q1)))//这里的入队列，我们入的队列是为空的那一个
	{
		QPush(&(obj->q1), x);
	}
	else
	{
		QPush(&(obj->q2), x);
	}
}
//出栈
int myStackPop(MyStack* obj)
{
    //假设法，创建两个新的队列，一个为空队列，一个不为空
	Queue* empty = &(obj->q1);
	Queue* noempty = &(obj->q2);

	if (!QEmpty(&(obj->q1)))
	{
		empty = &(obj->q2);
		noempty = &(obj->q1);
	}
    //假设法完成后我们就只需要对empty和noempty进行改变
	while (QSize(noempty) > 1)//这里的循环和大于1的意思是，我们要把非空的队列入到为空的队列里，但是要剩余一个元素。
	{
		QPush(empty, QTop(noempty));
		QPop(noempty);
	}
	int top = QTop(noempty);//上面我们剩余的那个元素就是作为栈先进后出的那个元素（后面再单独解释一下）
	QPop(noempty);
	return top;
}
//提取栈顶元素
int myStackTop(MyStack* obj) {
	if (!QEmpty(&(obj->q1)))
	{
		return QBack(&(obj->q1));//队尾实际上就是栈顶
	}
	else
	{
		return QBack(&(obj->q2));
	}
}
//判空
bool myStackEmpty(MyStack* obj) {
	return QEmpty(&(obj->q1)) && QEmpty(&(obj->q2));
}

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

	free(obj);
}

不能理解的可以看一下图：

相对于队列来说，如果要实现先进后出的特点，就要不断的往空队列移动元素，且移动的时候一定要保留一个，这个保留的元素相对于栈来说，就是我们要出栈的第一个元素。 

三.用栈实现队列

OJ链接

同样的，解决这道题，依然要先实现一下栈。

typedef int SLTDataType;
typedef struct Stack
{
	SLTDataType* a;
	int top;
	int capacity;
}ST;
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	//top的位置在栈顶的后面的一个位置
	pst->top = 0;
}
void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
void STPush(ST* pst, SLTDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		SLTDataType* tmp = (SLTDataType*)realloc(pst->a, newcapacity * sizeof(SLTDataType));
		if (tmp == NULL)
		{
			perror("STPush::realloc");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
SLTDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

//正式开始实现队列
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;

//初始化队列
MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));

    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}
//入队
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->pushst,x);//把需要入队的元素全部放在pushst里
}
//出队+删除
int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);//调用下面的Peek函数，取出要出队的元素
    STPop(&obj->popst);然后删除
    return front;
}
//出队
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))//判断要popst是否为空
    {
        while(!STEmpty(&obj->pushst))//popst为空了并且pushst里面有元素
        {
            int top=STTop(&obj->pushst);//提取pushst里的元素
            STPush(&obj->popst,top);//放到popst里面
            STPop(&obj->pushst);//删除刚刚出去的pushst里的栈顶元素
        }
    }
    //这里的if语句和while语句的作用就是把pushst里的元素反过来放入到popst里面
    return STTop(&obj->popst);//最后在返回出栈的值，这个值就是我们要的先进先出的值
}
//判空
bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
//释放
void myQueueFree(MyQueue* obj) {
    STDestory(&obj->pushst);
    STDestory(&obj->popst);
    free(obj);
}

这道题的思路就是先创建两个栈，一个专门用来入，一个专门用来出。要出栈的话就用popst。

等到我们把所有的元素都移动到popst里面的时候，再用栈的性质出栈，此时出来的元素的顺序将会是1,2,3,4。符合我们需要的特性，大家也可以试试入栈什么的。

四.设计循环队列

OJ链接




typedef struct {
    int* a;
    int head;
    int tail;//指向尾的下一个
    int k;//k是队列里所有的元素个数的总数
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    obj->a = (int*)malloc(sizeof(int) * (k + 1));//多创建一个sizeof(int)
    obj->head = 0;
    obj->tail = 0;
    obj->k = k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->tail == obj->head;//如果head==tail就说明没有元素
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail + 1) % (obj->k + 1) == obj->head;//这里取了一个模，是为了避免tail在k位置时的情况
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))//满了就不能入了
        return false;

    obj->a[obj->tail] = value;//tail指向的是队尾的下一个位置
    obj->tail++;//可以分为正常情况和tail在k位置上的情况

    obj->tail %= (obj->k + 1);//有这个主要是为了避免tail在K位置上的情况
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->head++;//删除队头的元素，直接head++就行了
    obj->head %= (obj->k + 1);//跟tail在k位置是同一个道理
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->head];//直接返回队头元素
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->tail + obj->k) % (obj->k + 1)];//因为tail指向的是队尾的下一个位置，所以要小心一下tail在k位置的情况
}


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

这里需要单独解释一下一个东西：

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->tail + obj->k) % (obj->k + 1)];//因为tail指向的是队尾的下一个位置，所以要小心一下tail在k位置的情况
}

注意我return的是什么：(obj->tail + obj->k) % (obj->k + 1)这个东西又可以写成(obj->tail-1 + obj->k+1) % (obj->k + 1)。obj->tail-1加上一个obj->k + 1再取obj->k + 1的余。最后的结果不会有改变，但是多加了这一步就完美的避免了，tail在0位置的情况。如果直接return的是tail-1会存在访问越界的问题。

到这里这四个OJ题就结束了，感谢大家的观看，如有错误，还请多多指出。 

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

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

相关文章

基于SSM的理发店会员管理系统的设计和实现（有报告）。Javaee项目。ssm项目。

基于SSM的理发店会员管理系统的设计和实现（有报告）。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的理发店会员管理系统的设计和实现&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0…
阅读更多...
泛微E9开发 添加多个多选框，实现单选框的效果

泛微E9开发 添加多个多选框，实现单选框的效果

利用多个多选框实现单选框的效果 1、功能背景2、展示效果3、实现效果 1、功能背景 如下图所示&#xff0c;在表单中新增四个“选择框-复选框”类型的字段&#xff0c;并且设置其中的选项&#xff0c;每个多选框都只有一个选项&#xff0c;通过代码块实现单选框的效果 1.显示模…
阅读更多...
ICode国际青少年编程竞赛- Python-5级训练场-综合练习7

ICode国际青少年编程竞赛- Python-5级训练场-综合练习7

ICode国际青少年编程竞赛- Python-5级训练场-综合练习7 1、 for i in range(6):while not Flyer[i].disappear():wait()Spaceship.step(2 2 * i)Spaceship.turnRight()2、 def get(a, b, c, d):for i in (a, b, c, d):Dev.step(i)if i ! 0:Dev.turnRight() get(3, 3, 5, -4)…
阅读更多...
【CSP CCF记录】202206-2 寻宝！大冒险！

【CSP CCF记录】202206-2 寻宝！大冒险！

题目 过程 思路 1.绿化图坐标边界太大&#xff0c;不能直接用矩阵表示&#xff0c;可以用一个二维数组存储有树坐标的x,y值。 定义两个数组&#xff1a;绿化图arr[1005][2]、宝藏图数组b[55][55] 2. 依据条件&#xff0c;从绿化图中第一棵树的坐标开始区域遍历。统计绿化图…
阅读更多...
spring cloud微服务example 入门第一个例子

spring cloud微服务example 入门第一个例子

新建Maven工程 删除src目录&#xff0c;修改poml.xml <modelVersion>4.0.0</modelVersion><groupId>org.example</groupId> <artifactId>SpringCloud_example</artifactId> <version>1.0-SNAPSHOT</version> <packaging&g…
阅读更多...
物联网五层架构分析

物联网五层架构分析

物联网五层架构分析 随着科技的迅速发展&#xff0c;物联网&#xff08;IoT&#xff09;作为日常生活中不可或缺的一部分&#xff0c;已融入人们的生活和工作中。物联网五层架构&#xff0c;包括感知层、网络层、数据层、应用层和业务层&#xff0c;扮演着关键的角色。 感知层 …
阅读更多...
WIFI模块的AT指令联网数据交互--第十天

WIFI模块的AT指令联网数据交互--第十天

1.1.蓝牙&#xff0c;ESP-01s&#xff0c;Zigbee, NB-Iot等通信模块都是基于AT指令的设计 初始配置和验证 ESP-01s出厂波特率正常是115200, 注意&#xff1a;AT指令&#xff0c;控制类都要加回车&#xff0c;数据传输时不加回车 1.2.上电后&#xff0c;通过串口输出一串系统…
阅读更多...
【运维】如何安装ubuntu-24.04？ 如何分区？

【运维】如何安装ubuntu-24.04？ 如何分区？

如何安装ubuntu-24.04&#xff1f;如何分区 经过一系列折腾&#xff0c;我总结了这几点&#xff1a; &#xff08;1&#xff09;在BIOS启动设置里&#xff0c;如果是GPT的硬盘格式&#xff0c;那么对应的就是UEFI的启动方式&#xff1b;如果是MBR的硬盘格式&#xff0c;那么对…
阅读更多...
【Spring】GoF 之代理模式

【Spring】GoF 之代理模式

一、代理模式 在 Java 程序中的代理模式的作用&#xff1a; 当一个对象需要受到保护的时候&#xff0c;可以考虑使用代理对象去完成某个行为 需要给某个对象的功能进行功能增强的时候&#xff0c;可以考虑找一个代理进行增强 A 对象无法和 B 对象直接交互时&#xff0c;也可以…
阅读更多...
C# 使用Queue高效检索树行数据符合条件的数据，并返回完整树形数据示例

C# 使用Queue高效检索树行数据符合条件的数据，并返回完整树形数据示例

最近有项目需要加载大型树数据&#xff0c;数据大概3W条 后端使用C# NET6 前端使用Vue3 elementuiplus 虚拟tree 》解决大型树数据加载 遇到的问题是后端在检索数据时&#xff0c;要返回匹配数据的完整树目录 1.因为单条数据没有存放完整路径&#xff0c;需要通过父级ID逐…
阅读更多...
【ARM Cortex-M 系列 2.1 -- Cortex-M7 Debug system registers】

【ARM Cortex-M 系列 2.1 -- Cortex-M7 Debug system registers】

请阅读【嵌入式开发学习必备专栏】 文章目录 Debug system registers中断控制状态寄存器&#xff08;ICSR&#xff09;Debug Halting Control and Status Register, DHCSR Debug 寄存器DCRSR与DCRDRCPU 寄存器读操作CPU 寄存器写操作CPU 寄存器选择CPU 寄存器读写示例 调试故障…
阅读更多...
Ubuntu安装VScode

Ubuntu安装VScode

Ubuntu安装VScode 前言&#xff1a; 1、Ubuntu安装VScode比较方便 2、我更喜欢source insight 1、获取到linux版本的VScode安装包 VSCode 下载地址是&#xff1a;https://code.visualstudio.com/ 2、得到安装包 3、复制到ubuntu中&#xff0c;使用命令安装 sudo dpkg -i cod…
阅读更多...
安卓短视频一键搬运软件_V1.5.2 高级版

安卓短视频一键搬运软件_V1.5.2 高级版

短视频一键搬运app是一款非常实用的视频处理软件&#xff0c;拥有各种各样的视频处理功能&#xff0c;可以帮助用户进行视频的多项处理&#xff0c;首先用户可以在这里为视频去除水印&#xff0c;打开视频文件过后&#xff0c;再把视频里面的水印内容框选出来&#xff0c;这样就…
阅读更多...
第三课，python基础语法（二），基本算术运算符、3种数据类型、变量命名规则

第三课，python基础语法（二），基本算术运算符、3种数据类型、变量命名规则

一&#xff0c;基本算术运算 数学中&#xff1a;&#xff0c;-&#xff0c;&#xff0c; *小练习 请在程序中&#xff0c;定义如下变量&#xff1a; 钱包余额(变量名&#xff1a;money)&#xff0c;初始余额50 请通过程序计算&#xff0c;再购买了&#xff1a; 冰淇淋10元可…
阅读更多...
【C语言/数据结构】栈：从概念到两种存储结构的实现

【C语言/数据结构】栈：从概念到两种存储结构的实现

目录 一、栈的概念 二、栈的两种实现方式 1.顺序表实现栈 2.链表实现栈 三、栈的顺序存储结构及其实现 1.栈的声明 2.栈的初始化 3.栈的销毁 4.栈的压栈 5.栈的弹栈 6.栈的判空 7.返回栈顶元素 8.返回栈的长度 四、栈的链式存储结构及其实现 1.栈的声明 2.栈的…
阅读更多...
[C++核心编程-03]----C++函数提高学习

[C++核心编程-03]----C++函数提高学习

目录 引言 正文 01-函数提升简介 02-函数默认参数 03-函数占位参数 04-函数重载 05-函数重载的注意事项 总结 引言 函数在C编程中扮演着至关重要的角色&#xff0c;通过合理使用函数&#xff0c;可以提高程序的结构性、灵活性、可读性和维护性。因此&…
阅读更多...
汇昌联信：拼多多入驻条件是哪些？

汇昌联信：拼多多入驻条件是哪些？

在电商领域&#xff0c;拼多多以其独特的团购模式迅速崛起&#xff0c;吸引了众多商家的目光。想要在拼多多上开店&#xff0c;了解其入驻条件是必不可少的第一步。下面将详细解读拼多多的入驻条件&#xff0c;帮助有意加入的商家们做好准备。 一、企业资质要求 想要成功入驻拼…
阅读更多...
STM32（GPIO）

STM32（GPIO）

GPIO简介 GPIO&#xff08;General Purpose Input Output&#xff09;通用输入输出口 引脚电平&#xff1a;0V~3.3V&#xff0c;部分引脚可容忍5V 输出模式下可控制端口输出高低电平&#xff0c;用以驱动LED、控制蜂鸣器、模拟通信协议输出时序等 输入模式下可读取端口的高低电…
阅读更多...
【C++】继承与多态的一些练习题

【C++】继承与多态的一些练习题

学习完了继承与多态&#xff0c;当然要来点练习题啦~ 第一题&#xff1a; class Base1 { public: int _b1; }; class Base2 { public: int _b2; }; class Derive : public Base1, public Base2 { public: int _d; }; int main(){ Derive d; Base1* p1 &d; Base2* p2…
阅读更多...
Day_4

Day_4

1. 地址簿功能 查询地址列表 属于常规方案 新增地址 属于常规方案 修改地址 删除地址 设置默认地址 2. 用户下单业务 数据库分析 订单表和订单明细表的关系&#xff1a;一对多 代码开发 controller 层 service 层 异常处理&#xff08;收货地址为空、超出配送范围、购物…
阅读更多...
最新文章

Copyright @ 2022~2023