【栈和队列OJ题】

栈和队列OJ题

文章目录

  • 栈和队列OJ题
    • 1. 用队列实现栈
    • 2. 用栈实现队列
    • 3. 括号匹配问题
    • 4. 循环队列

1. 用队列实现栈

OJ链接：225. 用队列实现栈 - 力扣（LeetCode）

好的，我们一起来看一下题目，题目是这样说的

在这里插入图片描述

思路：使用两个队列，始终保持一个队列为空。当我们需要进行进栈操作时，将数据进入不为空的队列中（若两个都为空，则随便压入一个队列）。当需要进行出栈操作时，将不为空的队列中的数据导入空队列，仅留下一个数据，这时将这个数据返回并且删除即可。判断栈是否为空，即判断两个队列是否同时为空

举个例子，我们将 1，2，3，4 进栈，实际上就是进入其中一个队列 q1 中

在这里插入图片描述

如果我们要出栈是不是就是按照 4，3，2，1 的顺序，我们将 1，2，3 push 到第二个队列 q2 中，然后在 q1 中 pop 4 就完成出栈的一步操作

在这里插入图片描述

然后我们就可以 push q2 中的 1，2 到 q1 ，这样就可以留一个 3 在 q2 然后 pop q2 就可以完成 3 的出栈操作

在这里插入图片描述

以此循环就可以完成出栈的全部操作

在这里插入图片描述

下面就是代码实现：

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

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

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->size = 0;
	pq->head = pq->tail = NULL;
}

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

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

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

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!(QueueEmpty(pq)));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
	pq->size--;
}


QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!(QueueEmpty(pq)));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!(QueueEmpty(pq)));

	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}


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

}

int myStackPop(MyStack* obj) {
	Queue* empty = &obj->q1;
	Queue* noEmpty = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		empty = &obj->q2;
		noEmpty = &obj->q1;
	}

	while (QueueSize(noEmpty) > 1)
	{
		QueuePush(empty, QueueFront(noEmpty));
		QueuePop(noEmpty);
	}
	int top = QueueFront(noEmpty);
	QueuePop(noEmpty);

	return top;
}

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) {
	QueueDestory(&obj->q1);
	QueueDestory(&obj->q2);
	free(obj);
}

2. 用栈实现队列

OJ链接：232. 用栈实现队列 - 力扣（LeetCode）

好的，我们一起来看一下题目，题目是这样说的

在这里插入图片描述

思路：使用两个栈，第一个栈只用于数据的输入，第二个栈只用于数据的输出。当需要输出数据，但第二个栈为空时，先将第一个栈中的数据一个一个导入到第二个栈，然后第二个栈再输出数据即可

举个例子 ，我想要按照 1，2，3，4 的顺序入队列，那就是要按照 1，2，3，4 的顺序出队列，我们可以先入一个栈，然后将第一个栈中的数据一个一个导入到第二个栈，输入即可

在这里插入图片描述

下面就是代码实现：

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top; // 栈顶
	int _capacity; // 容量
}Stack;

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

// 入栈
void StackPush(Stack* ps, STDataType data);

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

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

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

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

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

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->_a[ps->_top - 1];
}

void StackInit(Stack* ps)
{
	assert(ps);

	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
		if (NULL == tmp)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->_a = tmp;
		ps->_capacity = newCapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	ps->_top--;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

typedef struct {
	Stack pushST;
	Stack popST;
} MyQueue;


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

	return obj;
}

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

void PushSTToPopST(MyQueue* obj)
{
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}
}

int myQueuePop(MyQueue* obj) {
	PushSTToPopST(obj);
	int front = StackTop(&obj->popST);
	StackPop(&obj->popST);
	return front;
}



int myQueuePeek(MyQueue* obj) {
	PushSTToPopST(obj);
	int front = StackTop(&obj->popST);
	return front;
}

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

}

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->pushST);
	StackDestroy(&obj->popST);
	free(obj);
}

3. 括号匹配问题

OJ链接：20. 有效的括号 - 力扣（LeetCode）

好的，我们一起来看一下题目，题目是这样说的

在这里插入图片描述

思路：该题是栈的典型应用，满足后进先出的规则（后入栈的前括号将优先与先出现的后括号相匹配）。遍历字符串，遇到前括号直接入栈。遇到后括号，判断该后括号与栈顶的前括号是否匹配（若此时栈为空，则字符串无效），若不匹配则字符串无效；若匹配则删除栈顶元素，继续遍历字符串，直到字符串遍历完毕。当字符串遍历完后，检测栈是否为空，若为空，则字符串有效，若不为空，说明有前括号未匹配，字符串无效

typedef char STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top; // 栈顶
	int _capacity; // 容量
}Stack;

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

// 入栈
void StackPush(Stack* ps, STDataType data);

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

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

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

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

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

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->_a[ps->_top - 1];
}

void StackInit(Stack* ps)
{
	assert(ps);

	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));
		if (NULL == tmp)
		{
			perror("malloc fail");
			exit(-1);
		}
		ps->_a = tmp;
		ps->_capacity = newCapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	ps->_top--;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

bool isValid(char * s){
    Stack st;
    StackInit(&st);

    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st, *s);
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                if((*s == ')' && StackTop(&st) != '(')
                || (*s == ']' && StackTop(&st) != '[')
                || (*s == '}' && StackTop(&st) != '{'))
                {
                    StackDestroy(&st);
                    return false;
                }
                StackPop(&st);
            }
            
        }
        ++s;
    }
    if(!StackEmpty(&st))
    {
        StackDestroy(&st);
        return false;
    }
    return true;
}

4. 循环队列

OJ链接：622. 设计循环队列 - 力扣（LeetCode）

好的，我们一起来看一下题目，题目是这样说的

在这里插入图片描述

思路：在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。
注意：环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满。
在这里插入图片描述

实现代码如下：

typedef struct {
    int* a;
    int head;
    int tail;
    int size;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail + 1) % obj->size == obj->head;
}

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

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

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->head++;
        obj->head %= obj->size;
        return true;
    }
}

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

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



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

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

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

相关文章

【斯坦福因果推断课程全集】2_无混淆和倾向分1

【斯坦福因果推断课程全集】2_无混淆和倾向分1

目录 Beyond a single randomized controlled trial Aggregating difference-in-means estimators Continuous X and the propensity score 随机试验的一个最简单的扩展是无约束下的干预效果估计。从定性上讲，当我们想估计一种并非随机的治疗效果，但一…
阅读更多...
PyTorch | 加速模型训练的妙招

PyTorch | 加速模型训练的妙招

引言 提升机器学习模型的训练速度是每位机器学习工程师的共同追求。训练速度的提升意味着实验周期的缩短，进而加速产品的迭代过程。同时，这也表示在进行单一模型训练时，所需的资源将会减少。简而言之，我们追求的是效率。 熟悉 PyT…
阅读更多...
mybatis的拦截器

mybatis的拦截器

文章目录 第三个是参数拦截器第四个是结果集拦截器mybatis拦截器-笔试题1.笔试题 JDBC的执行流程3.执行sql语句,返回执行结果 mybatis的四种拦截器 第一个是执行拦截器: Executor（执行器拦截器）： 用途：拦截MyBatis执行器方法的…
阅读更多...
AI版Siri要明年见，研究表明ChatGPT暂无法取代程序员，Kimi推出浏览器插件

AI版Siri要明年见，研究表明ChatGPT暂无法取代程序员，Kimi推出浏览器插件

ChatGPT狂飙160天，世界已经不是之前的样子。 更多资源欢迎关注 根据彭博社记者马克古尔曼的最新消息，苹果公司今年不会推出全新的Apple Intelligence驱动的Siri，该公司计划在明年1月开始测试，并在iOS 18.4中才推出正式版本。 此前…
阅读更多...
未来工业革命：区块链在工业4.0中的角色与应用

未来工业革命：区块链在工业4.0中的角色与应用

随着科技的迅猛发展，人类社会正在逐步迈向工业4.0时代。在这一新时代的背景下，区块链技术作为一种创新性的分布式账本技术，正逐步在工业领域展示其独特的价值和潜力。本文将深入探讨区块链在工业4.0中的角色与应用，分析其对工业生…
阅读更多...
windows安装Docker Desktop及国内镜像

windows安装Docker Desktop及国内镜像

简介 Docker 是一个开源的应用容器引擎，它让开发者可以打包他们的应用以及依赖包到一个可移植的容器中，然后发布到任何流行的 Linux 机器上，也可以实现虚拟化。通过Docker工具，简化了应用的部署、配置和管理过程，提高…
阅读更多...
dataX入门

dataX入门

下载dataX https://datax-opensource.oss-cn-hangzhou.aliyuncs.com/202308/datax.tar.gz 然后 下载后解压至本地某个目录，进入bin目录，即可运行同步作业： $ cd {YOUR_DATAX_HOME}/bin $ python datax.py {YOUR_JOB.json} 要求你有python…
阅读更多...
FPGA上板项目（一）——点灯熟悉完整开发流程、ILA在线调试

FPGA上板项目（一）——点灯熟悉完整开发流程、ILA在线调试

目录 创建工程创建 HDL 代码仿真添加管脚约束添加时序约束生成 bit 文件下载ILA 在线调试 创建工程 型号选择：以 AXU9EG 开发板为例，芯片选择 xczu9eg-ffvb1156-2-i 创建 HDL 代码 注意：由于输入时钟为 200MHz 的差分时钟，因此…
阅读更多...
【Python】已解决：ModuleNotFoundError: No module named ‘nltk’

【Python】已解决：ModuleNotFoundError: No module named ‘nltk’

文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确代码示例五、注意事项 已解决：ModuleNotFoundError: No module named ‘nltk’ 一、分析问题背景 在使用Python进行自然语言处理或文本分析时，我们经常会用到各种库来辅助我们的工…
阅读更多...
【ACM 独立出版，高录用EI稳检索】2024年大数据与数字化管理国际学术会议 (ICBDDM 2024，8月16-18)

【ACM 独立出版，高录用EI稳检索】2024年大数据与数字化管理国际学术会议 (ICBDDM 2024，8月16-18)

2024年大数据与数字化管理国际学术会议 (ICBDDM 2024)，将于2024年8月16-18日在中国上海召开。 “大数据与数字化管理”作为会议主题，旨在聚焦这一跨学科领域中最新的理论研究、技术进展、实践案例和未来趋势。本主题探讨的研究方向涵盖了大数据的收集、…
阅读更多...
GD32F303RET6读取SGM58031电压值

GD32F303RET6读取SGM58031电压值

1、SGM58031芯片详解 （1）SGM58031是一款低功耗，16位精度，delta-sigma (ΔΣ)模数转换器(ADC)。它从3V到5.5V供电。 （2）SGM58031包含一个片上参考和振荡器。它有一个I2C兼容接口，可以选择四个I2…
阅读更多...
15、电科院FTU检测标准学习笔记-基本性能

15、电科院FTU检测标准学习笔记-基本性能

作者简介： 本人从事电力系统多年，岗位包含研发，测试，工程等，具有丰富的经验 在配电自动化验收测试以及电科院测试中，本人全程参与，积累了不少现场的经验 ———————————————————…
阅读更多...
Nginx七层（应用层）反向代理：SCGI代理scgi_pass篇

Nginx七层（应用层）反向代理：SCGI代理scgi_pass篇

Nginx七层（应用层）反向代理 SCGI代理scgi_pass篇 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite：http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this art…
阅读更多...
利用Altair One 云平台，轻松实现全球企业产品研发创新与优化

利用Altair One 云平台，轻松实现全球企业产品研发创新与优化

在过去的几十年里，工程师和数据科学家引入了大量改变世界的技术，但他们的工作方式却出人意料地停滞不前。技术的革新也带来了效率的不断提升。 面对众多企业的同样难题，Altair整合产品，创造出了用于协作工程、数据工程和分析应用程…
阅读更多...
数列分块＜2＞

数列分块＜2＞

本期是数列分块入门<2>。该系列的所有题目来自hzwer在LOJ上提供的数列分块入门系列。 Blog:http://hzwer.com/8053.html sto hzwer orz %%% [转载] 好像上面的链接↑打不开&#xff0c;放一个转载:https://www.cnblogs.…
阅读更多...
【C++】C++-机房收费管理系统（源码+注释）【独一无二】

【C++】C++-机房收费管理系统（源码+注释）【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…
阅读更多...
RK3568平台开发系列讲解（内存篇）Linux进程内存的消耗统计

RK3568平台开发系列讲解（内存篇）Linux进程内存的消耗统计

🚀返回专栏总目录 文章目录 一、VSS（Virtual Set Size）二、RSS（Resident Set Size）三、PSS（Proportional Set Size）四、USS（Unique Set Size）五、其他工具Linux 提供了多种进程内存占用的度量指标, 它们反映了不同的内存使用特征: VSS 反映进程虚拟内存总需求, 包括未…
阅读更多...
Oracle基础以及一些‘方言’（一）

Oracle基础以及一些‘方言’（一）

1、什么是Oracle ORACLE数据库系统是美国ORACLE公司&#xff08;甲骨文&#xff09;提供的以分布式数据库为核心的一组软件产品&#xff0c;是最流行的客户/服务器(CLIENT/SERVER)或B/S体系结构的数据库之一。 ORACLE 通常应用于大型系统的数据库产品。 ORACLE 数据库是目前世界…
阅读更多...
企业内多个系统如何实现单点登录/SSO统一认证

企业内多个系统如何实现单点登录/SSO统一认证

背景 在现代化企业中&#xff0c;随着业务的不断扩展和技术的不断进步&#xff0c;企业通常会使用多个系统来支持其日常运营&#xff0c;如OA、HR、CRM、研发应用&#xff08;Git、Jira等&#xff09;、财务系统、档案管理系统等。然而&#xff0c;这些系统往往各自为政&#…
阅读更多...
基于Spring Boot的高校后勤餐饮管理系统

基于Spring Boot的高校后勤餐饮管理系统

1 项目介绍 1.1 研究背景 “互联网”时代的到来&#xff0c;既给高校后勤管理发展带来了机遇&#xff0c;也带来了更大的挑战。信息化应用已经开始普及&#xff0c;传统的高校后勤餐饮管理模式往往存在着效率低下、信息不透明、资源浪费等问题&#xff0c;已经难以满足现代高…
阅读更多...
最新文章

Copyright @ 2022~2023