具备教学意义的实操(用栈实现队列)

具备教学意义的实操(用队列实现栈)-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/Jason_from_China/article/details/138729955

 具备教学意义的实操(用栈实现队列)

 题目

 232. 用栈实现队列 - 力扣(LeetCode)

逻辑​​​ 

 核心逻辑

代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a; // 首元素的地址
	int _top;		// 栈顶,初始化为0,也就是等同于size,初始化为-1,等同于下标
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈尾元素
STDataType StackTail(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 初始化栈 
void StackInit(Stack* ps)
{
	ps->_a = NULL;
	
	// 这里栈顶初始化为-1和初始化为0是不一样的
	//    0 0 0 0 0 0 0 0 数组
	// -1 0 0 0 0 0 0 0 0 初始化为-1
	//    0 0 0 0 0 0 0 0 初始化为0
    // 初始化为0,也就是等同于size,初始化为-1,等同于下标
	ps->_capacity = ps->_top = 0;
}
//销毁
void StackDestroy(Stack* ps) {
    if (ps != NULL) { // 检查指针是否非空
        free(ps->_a);
        ps->_a = NULL;
        ps->_capacity = 0;
        ps->_top = -1; // 将栈顶指针设置为-1,表示栈为空
    }
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	//首先判断容量是多少,然后进行扩容
	if (ps->_capacity == ps->_top)
	{
		//扩容
		int newapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("StackPush:tmp:error:");
			exit(1);
		}
		//改变容量大小,指向新空间的头第一个元素位置的地址
		ps->_capacity = newapacity;
		ps->_a = tmp;
	}
	//插入数值
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	// 判断为不为空,判断里面有没有数值
	assert(ps && ps->_top);
	ps->_top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
    assert(ps && ps->_top >= 0);
    return ps->_a[ps->_top-1];
}
// 获取栈尾元素 
STDataType StackTail(Stack* ps)
{
	assert(ps && ps->_top);
	return ps->_a[0];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps && ps->_top);
	return ps->_top - 1;
}
// 检测栈是否为空,如果为空返回非零结果(1),如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
	// 所以,ps->_top == 0 这个表达式的作用是比较栈顶位置 ps->_top 是否等于 0。
	// 如果相等,说明栈为空,表达式结果为 true(在C语言中用 1 表示);
	// 如果不相等,说明栈不为空,表达式结果为 false(在C语言中用 0 表示)
}

typedef struct 
{   
    Stack Q1;
    Stack Q2;
} MyQueue;

//初始化
MyQueue* myQueueCreate() 
{     
    MyQueue* ps = (MyQueue*)malloc(sizeof(MyQueue));
    if(ps == NULL)
    {
        perror("ps");
        exit(1);
    }
    StackInit(&(ps->Q1));
    StackInit(&(ps->Q2));
    return ps;
}
//入数据
void myQueuePush(MyQueue* obj, int x) 
{   
    StackPush(&(obj->Q1),x); 
}

//获取栈顶数据
int myQueuePeek(MyQueue* obj)
{
    //队列是先进后出,栈是先进先出
    if(StackEmpty(&(obj->Q2)))
    {
        while(!StackEmpty(&(obj->Q1)))
        {
           StackPush(&(obj->Q2),StackTop(&(obj->Q1)));
           StackPop(&(obj->Q1));
        }
    }
    return StackTop(&(obj->Q2));
}
//删除栈顶数据
int myQueuePop(MyQueue* obj) 
{
    int ret = myQueuePeek(obj);
    StackPop(&(obj->Q2));
    return ret;
}
//判空
bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&(obj->Q1)) && StackEmpty(&(obj->Q2));
}
//释放
void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&(obj->Q1));
    StackDestroy(&(obj->Q2));
    free(obj);
}
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

代码解释

  1. StackInit: 初始化一个栈,设置栈的容量和栈顶指针为0,同时初始化栈的数组为NULL。

  2. StackDestroy: 销毁栈,释放栈的内存,并将栈的指针和容量设置为0,栈顶指针设置为-1。

  3. StackPush: 向栈中压入一个元素。如果栈的容量等于栈顶指针(意味着栈已满),则先进行扩容,然后将数据压入栈顶。

  4. StackPop: 从栈中弹出一个元素。由于栈顶指针指向栈顶元素的下一个位置,所以直接减少栈顶指针的值。

  5. StackTop: 返回栈顶元素的值,但不移除它。

  6. StackTail: 返回栈尾元素的值,但不移除它。

  7. StackSize: 返回栈中元素的数量。

  8. StackEmpty: 判断栈是否为空,如果栈顶指针为0,表示栈为空。

  9. myQueueCreate: 创建并初始化队列,分配内存给 MyQueue 结构体,并初始化其两个栈 Q1Q2

  10. myQueuePush: 向队列中添加一个元素。由于队列使用栈 Q1 来模拟入队操作,所以直接将元素压入 Q1

  11. myQueuePeek: 返回队列的第一个元素,即队列的前端元素。由于队列是先进先出的,而栈是先进后出的,所以如果出队栈 Q2 为空,需要将 Q1 中的所有元素依次弹出并压入 Q2,这样 Q2 的底部就成为队列的前端。然后返回 Q2 的栈顶元素。

  12. myQueuePop: 移除并返回队列的第一个元素。它首先调用 myQueuePeek 获取队列前端的元素,然后调用 StackPopQ2 中移除该元素,并返回它。

  13. myQueueEmpty: 判断队列是否为空。如果 Q1Q2 都为空,则队列为空。

  14. myQueueFree: 释放队列占用的内存,销毁两个栈,释放 MyQueue 结构体的内存。

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

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

相关文章

一、VIsual Studio下的Qt环境配置(Visual Studio 2022 + Qt 5.12.10)

一、下载编译器Visual Studio2022和Qt 5.12.10 Visual Studio 2022 社区版就够学习使用了 Qt5.12.10 安装教程网上搜&#xff0c;一大堆 也很简单&#xff0c;配置直接选默认&#xff0c;路径留意一下即可 二、配置环境 Ⅰ&#xff0c;配置Qt环境变量 系统变量下的Path&a…

C++的数据结构(五):树和存储结构及示例

在计算机科学中&#xff0c;树是一种抽象数据类型&#xff08;ADT&#xff09;或是实现这种抽象数据类型的数据结构&#xff0c;用来模拟具有树状结构性质的数据集合。这种数据结构以一系列连接的节点来形成树形结构。在C中&#xff0c;树的概念和存储结构是实现各种复杂算法和…

Golang | Leetcode Golang题解之第87题扰乱字符串

题目&#xff1a; 题解&#xff1a; func isScramble(s1, s2 string) bool {n : len(s1)dp : make([][][]int8, n)for i : range dp {dp[i] make([][]int8, n)for j : range dp[i] {dp[i][j] make([]int8, n1)for k : range dp[i][j] {dp[i][j][k] -1}}}// 第一个字符串从 …

61、内蒙古工业大学、内蒙科学技术研究院:CBAM-CNN用于SSVEP - BCI的分类方法[脑机二区还是好发的]

前言&#xff1a; 之前写过一篇对CBAM模型改进的博客&#xff0c;在CBAM中引入了ECANet结构&#xff0c;对CBAM中的CAM、SAM模块逐一改进&#xff0c;并提出ECA-CBAM单链双链结构&#xff0c;我的这个小的想法已经被一些同学实现了&#xff0c;并进行了有效的验证&#xff0c;…

算法-卡尔曼滤波之为什么要使用卡尔曼滤波器

假设使用雷达来预测飞行器的位置&#xff1b; 预先的假设条件条件: 1.激光雷达的激光束每5s发射一次&#xff1b; 2.通过接受的激光束&#xff0c;雷达估计目标当前时刻的位置和速度&#xff1b; 3.同时雷达要预测下一时刻的位置和速度 根据速度&#xff0c;加速度和位移的…

ROS2 - 创建项目 (Ubuntu22.04)

本文简述&#xff1a;在 Ubuntu22.04 系统中使用 VS CODE 来搭建一个ROS2开发项目。 1. 创建工作空间 本文使用 Ubuntu 22.04&#xff0c; 已安装配置完成 VS Code&#xff0c;C 环境&#xff08;g/gdb&#xff09; 1.1 创建目录 选择文件夹作为工作空间&#xff0c;并在这…

Django开发实战之定制管理后台界面及知识梳理(下)

接上一篇&#xff1a;Django开发实战之定制管理后台界面及知识梳理&#xff08;中&#xff09; 1、前台设置 1、隐藏路由 当你输入一个错误地址时&#xff0c;可以看到这样的报错&#xff1a; 从这样的报错中&#xff0c;我们可以看到&#xff0c;这个报错页面暴漏了路由&a…

数据结构-题目

1.已知一颗完全二叉树的第6曾&#xff08;设根为第1层&#xff09;&#xff0c;有8个结点&#xff0c;则完全二叉树的结点个数&#xff0c;最少和最多分别是多少&#xff1f; 因此最少为39&#xff0c;最多为111 2.假设一棵三叉树的结点数为50&#xff0c;则它的最小高度为&…

【数据结构与算法 刷题系列】合并两个有序链表

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;数据结构与算法刷题系列&#xff08;C语言&#xff09; 目录 一、问题描述 二、解题思路详解 合并两个有序链表的思路 解题的步…

[PythonWeb:Django框架]:前后端请求调用;

文章目录 接着上篇项目app包下面创建static包&#xff0c;引入jquery&#xff0c;bootstrap 相关js文件views.py编写apicompute文件夹下面的urls.py路由模块引入views.py刚刚定义的函数html发送ajax请求 接着上篇 https://blog.csdn.net/Abraxs/article/details/138739727?sp…

【pouchdb-可视化工具 】

最近使用pouchdb&#xff0c;想找个其对应的可视化工具&#xff0c;可以对数据库进行操作。 找了好久才找到&#xff0c;网上有说先同步到couchdb&#xff0c;再用couchdb的可视化工具查看&#xff0c;其实没有那么麻烦&#xff0c;pouchdb的可视化工具其实藏在另外的pouchdb-…

让创意在幻觉中肆虐: 认识Illusion Diffusion AI

人工智能新境界 在不断发展的人工智能领域,一款非凡的新工具应运而生,它能将普通照片转化为绚丽的艺术品。敬请关注Illusion Diffusion,这是一个将现实与想象力完美融合的AI驱动平台,可创造出迷人的视错觉和超现实意境。 AI算法的魔力所在 Illusion Diffusion 的核心是借助先进…

react Effect副作用 - 避免滥用Effect

react Effect副作用 - 避免滥用Effect react Effect副作用基础概率什么是纯函数? 什么是副作用函数?纯函数副作用函数 什么时候使用Effect如何使用Effect 避免滥用Effect根据 props 或 state 来更新 state当 props 变化时重置所有 state将数据传递给父组件获取异步数据 react…

持续集成-Git

重要步骤命令 git init (初始化一个仓库) git add [文件名] (添加新的文件) git commit -m [关于本次提交的相关说明] (提交) git status (查看文件状态) git diff (如果文件改变&#xff0c;比较两个文件内容) git add[文件名] || git commit -a -m [关于本次提交的相关说…

RiProV2主题美化【支付页弹窗增加价格提示语】Ritheme主题美化RiProV2-网站WordPress美化二开

背景: 楼主的网站是用WordPress搭建的,并使用了正版主题RiProV2,但RiProV2在支付弹窗页没有价格,只在文章详情页会展示价格。本文就是美化这个支付弹窗,在支付弹窗页把价格字段加上,如下图所示: 美化前: 美化后 美化步骤: (1)定位到文件:/www/wwwroot/www.uu2i…

免费思维13招之九:时间型思维

免费思维13招之九:时间型思维 免费思维的另一大战略思维——时间型思维。 什么是时间型思维呢?就是在某一个规定的时间内对消费者进行免费,比如一个月中的某一天,或一周中的某一天或一天中的某一个时间段对消费者进行免费。 就在去年,有一个电影院老板弟子,他的电影院营…

增强型植被指数EVI、ndvi数据、NPP数据、GPP数据、土地利用数据、植被类型数据、降雨量数据

引言 多种卫星遥感数据反演增强型植被指数&#xff08;EVI&#xff09;产品是地理遥感生态网推出的生态环境类数据产品之一&#xff0c;产品包括1986-2021年度月度数据&#xff0c;数据类型tif栅格数据。该产品经过专家组验证&#xff0c;质量良好。 正文 栅格数据源 数据名…

【JavaEE】Web服务器与请求响应流程:深入了解如何处理Web请求

目录 Web服务器请求响应流程分析小结 Web服务器 浏览器和服务器两端进⾏数据交互, 使⽤的就是HTTP协议 前⾯我们已经学习了 HTTP 协议, 知道了 HTTP 协议就是 HTTP 客⼾端和 HTTP 服务器之间的交互数据的格式. Web 服务器就是对HTTP协议进⾏封装, 程序员不需要直接对协议进⾏…

开关电源功率测试方法:输入、输出功率测试步骤

在现代电子设备中&#xff0c;开关电源扮演着至关重要的角色&#xff0c;其效率和稳定性直接影响到整个系统的性能。因此&#xff0c;对开关电源进行功率测试成为了电源管理的重要环节。本文将详细介绍如何使用DC-DC电源模块测试系统对开关电源的输入输出功率进行准确测量&…

快速对比 找出2个名单不同之处

import pandas as pd# 读取两个Excel文件 df1 pd.read_excel(1.xlsx) df2 pd.read_excel(2.xlsx)# 检查两个DataFrame的列是否相同 if list(df1.columns) ! list(df2.columns):print("两个Excel文件的列不一致。")print("文件1的列&#xff1a;", df1.co…