leetcode刷题之用栈实现队列（C语言版）

leetcode刷题之用栈实现队列（C语言版）

  • 一、题目描述
  • 二、题目要求
  • 三、题目解析
    • Ⅰ、typedef struct
    • Ⅱ、MyQueue* myQueueCreate
    • Ⅲ、void myQueuePush(MyQueue* obj, int x)
    • Ⅳ、int myQueuePeek(MyQueue* obj)
    • Ⅴ、int myQueuePop(MyQueue* obj)
    • Ⅶ、bool myQueueEmpty(MyQueue* obj)
    • Ⅷ、void myQueueFree(MyQueue* obj)
  • 四、完整代码

一、题目描述

232、用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

①、void push(int x) 将元素 x 推到队列的末尾
②、int pop() 从队列的开头移除并返回元素
③、int peek() 返回队列开头的元素
④、boolean empty() 如果队列为空，返回 true ；否则，返回 false

二、题目要求

①、你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
②、你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

三、题目解析

看到这道题目，我们首先要了解一些基础的知识，例如栈和队列的一些相关特性，比如栈是先进后出，队列是先进先出。如果有小伙伴还没有掌握这两种数据结构，建议先看一下博主之前有关栈和队列的文章，《数据结构——栈的详细介绍》和《数据结构——看完这篇保证你学会队列》，相信大家看完之后会有一个更深的了解。
首先解决这个问题我们 需要先用C语言完成一个栈的基本实现，其功能接口包括栈的创建，栈的销毁，压栈，出栈等基本操作。代码如下：

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


void InitStack(ST* pos);
void DestoryStack(ST* pos);
void PushStack(ST* pos,StDatatype x);
void PopStack(ST* pos);
StDatatype TopStack(ST* pos);
bool STEmpty(ST* pos);
int SizeST(ST* pos);
void InitStack(ST* pos)
{
	//断言
	assert(pos);
	pos->a = NULL;
	pos->top = 0;//指向栈顶元素的下一个
	          //pos->top=-1为指向栈顶元素
	pos->capacity = 0;
}
void DestoryStack(ST* pos)
{
	assert(pos);
	free(pos->a);
	pos->a = NULL;
	pos->capacity = pos->top = 0;
}
void PushStack(ST* pos, StDatatype x)
{
	assert(pos);
	if (pos->top == pos->capacity)
	{
		int newcapacity = pos->capacity == 0 ? 4 : pos->capacity * 2;
		StDatatype* tmp = (StDatatype*)realloc(pos->a, newcapacity * sizeof(StDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pos->a = tmp;
		pos->capacity = newcapacity;
	}

	//插入数据
	pos->a[pos->top] = x;
	pos->top++;

}
void PopStack(ST* pos)
{
	assert(pos);
	assert(!STEmpty(pos));
	pos->top--;
}
StDatatype TopStack(ST* pos)
{
	assert(pos);
	assert(!STEmpty(pos));
	return pos->a[pos->top - 1];
}
bool STEmpty(ST* pos)
{
	assert(pos);
	return pos->top == 0;
}
int SizeST(ST* pos)
{
	assert(pos);
	return pos->top;
}

接着我们便可以通过我们构建的栈的相关功能，通过我们的分析，用栈来构造一个属于我们自己的队列。
解决本题的基本思路便是：
①、通过上述代码，构建两个栈。一个为进数据的栈，一个为出数据的栈。
②、通过分析，完成题目中的上述接口。
在这里插入图片描述

Ⅰ、typedef struct

通过上述的分析，我们知道，我们需要用两个栈来完成我们的队列构造。所以我们将在结构体内构造两个栈。

typedef struct {
    ST pushst;
    ST popst;
} MyQueue;

Ⅱ、MyQueue* myQueueCreate

这部分的函数主要是我们队列的创建，我们需要在内存中开辟空间，来完成两个栈的初始化。我们直接调用栈里面的接口便可以完成本次的初始化。

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

Ⅲ、void myQueuePush(MyQueue* obj, int x)

通过前面的分析，我们可以知道，我们可以直接将需要压栈的数据压入pushst
代码如下：

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

Ⅳ、int myQueuePeek(MyQueue* obj)

首先我们需要对popst进行判空操作，如果其栈内不为空（有数据的话),我们便可以直接对其进行出栈操作，如果其中没有数据，我们便需要对其进行到数据，将Pushst内的数据，导入popst内。代码如下：

int myQueuePeek(MyQueue* obj)
{
  if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))
        {
            PushStack(&obj->popst,TopStack(&obj->pushst));
            PopStack(&obj->pushst);
        }
    }  
    return TopStack(&obj->popst);  
}

Ⅴ、int myQueuePop(MyQueue* obj)

我们直接对myQueuePeek函数进行复用，然后对popst进行出栈操作，最后直接返回即可。

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

Ⅶ、bool myQueueEmpty(MyQueue* obj)

判空操作，需要满足popst和pushst都为空，才能保证队列为空。

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
    
}

Ⅷ、void myQueueFree(MyQueue* obj)

在freeobj之前,我们需要对两个栈进行销毁操作，以防止内存的泄漏。

void myQueueFree(MyQueue* obj) {
    DestoryStack(&obj->popst);
    DestoryStack(&obj->pushst);
    free(obj);    
}

四、完整代码




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


void InitStack(ST* pos);
void DestoryStack(ST* pos);
void PushStack(ST* pos,StDatatype x);
void PopStack(ST* pos);
StDatatype TopStack(ST* pos);
bool STEmpty(ST* pos);
int SizeST(ST* pos);
void InitStack(ST* pos)
{
	//断言
	assert(pos);
	pos->a = NULL;
	pos->top = 0;//指向栈顶元素的下一个
	          //pos->top=-1为指向栈顶元素
	pos->capacity = 0;
}
void DestoryStack(ST* pos)
{
	assert(pos);
	free(pos->a);
	pos->a = NULL;
	pos->capacity = pos->top = 0;
}
void PushStack(ST* pos, StDatatype x)
{
	assert(pos);
	if (pos->top == pos->capacity)
	{
		int newcapacity = pos->capacity == 0 ? 4 : pos->capacity * 2;
		StDatatype* tmp = (StDatatype*)realloc(pos->a, newcapacity * sizeof(StDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pos->a = tmp;
		pos->capacity = newcapacity;
	}

	//插入数据
	pos->a[pos->top] = x;
	pos->top++;

}
void PopStack(ST* pos)
{
	assert(pos);
	assert(!STEmpty(pos));
	pos->top--;
}
StDatatype TopStack(ST* pos)
{
	assert(pos);
	assert(!STEmpty(pos));
	return pos->a[pos->top - 1];
}
bool STEmpty(ST* pos)
{
	assert(pos);
	return pos->top == 0;
}
int SizeST(ST* pos)
{
	assert(pos);
	return pos->top;
}


typedef struct {
    ST pushst;
    ST popst;
} MyQueue;


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

void myQueuePush(MyQueue* obj, int x) 
{
    PushStack(&obj->pushst,x);
}
int myQueuePeek(MyQueue* obj)
{
  if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))
        {
            PushStack(&obj->popst,TopStack(&obj->pushst));
            PopStack(&obj->pushst);
        }
    }  
    return TopStack(&obj->popst);  
}
int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    PopStack(&obj->popst);
    return front;
    
}



bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
    DestoryStack(&obj->popst);
    DestoryStack(&obj->pushst);
    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);
*/

在这里插入图片描述

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

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

相关文章

编译器核心技术概览

编译器核心技术概览

编译技术是一门庞大的学科，我们无法对其做完善的讲解。但不同用途的编译器或编译技术的难度可能相差很大，对知识的掌握要求也会相差很多。如果你要实现诸如 C、JavaScript 这类通用用途语言（general purpose language）&#xff0c…
阅读更多...
[shader] 光照入门（未完结。。。

[shader] 光照入门（未完结。。。

反射 漫反射：而当物体表面粗糙时，我们把物体表面看作无数不同方向的微小镜面，则这些镜面反射出的光方向均不相同，这就是漫反射。 高光反射：我们假定物体表面光滑，只有一个镜面，那么所有的光都…
阅读更多...
微信小程序前端环境搭建

微信小程序前端环境搭建

搭建微信小程序前端环境 申请小程序测试账号 访问路径 使用微信扫描二维码进行申请，申请成功之后，进入界面，获取小程序ID(AppID)和秘钥(AppSecret) 安装微信web开发者工具 访问路径 选择稳定开发的版本 需要在小程序的设置中将默认关闭…
阅读更多...
深入理解JVM 类加载机制

深入理解JVM 类加载机制

深入理解JVM 类加载机制 虚拟机如何加载Class文件？ Class文件中的信息进入到虚拟机后会发生什么变化？ 类加载机制就是Java虚拟机把描述类的数据从Class文件加载到内存，并对数据进行校验、转换解析和初始化，最终形成可以被虚拟机…
阅读更多...
AMEYA360：瑞萨面向高端工业传感器系统推出高精度模拟前端的32位RX MCU

AMEYA360：瑞萨面向高端工业传感器系统推出高精度模拟前端的32位RX MCU

全球半导体解决方案供应商瑞萨电子（TSE：6723）宣布面向高端工业传感器系统推出一款全新RX产品——RX23E-B，扩展32位微控制器（MCU）产品线。新产品作为广受欢迎的RX产品家族的一员，具有高精度模拟前…
阅读更多...
3D火山图绘制教程

3D火山图绘制教程

一边学习，一边总结，一边分享！ 本期教程内容 **注：**本教程详细内容 Volcano3D绘制3D火山图 一、前言 火山图是做差异分析中最常用到的图形，在前面的推文中，我们也推出了好几期火山图的绘制教程&#xff0…
阅读更多...
如何通过宝塔面板搭建一个本地MySQL数据库服务并实现远程访问

如何通过宝塔面板搭建一个本地MySQL数据库服务并实现远程访问

宝塔安装MySQL数据库，并内网穿透实现公网远程访问 文章目录 宝塔安装MySQL数据库，并内网穿透实现公网远程访问前言1.Mysql服务安装2.创建数据库3.安装cpolar3.2 创建HTTP隧道 4.远程连接5.固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网…
阅读更多...
Axios 通过a标签下载文件 跨域下载

Axios 通过a标签下载文件 跨域下载

<!-- a标签占位 --><a ref"down" ></a>getTest() {this.$axios.request({url: https://cnv13.55.la/download?file_key3695fa9461a0ae59cf3148581e4fe339&handle_typeexcel2pdf,method: get,responseType: blob, // 切记类型 blob}).then(re…
阅读更多...
java：CommandLineRunner命令行操作

java：CommandLineRunner命令行操作

背景 CommandLineRunner是一个SpringBoot提供的接口&#xff0c;这个接口可以让我们在SpringBoot启动之后&#xff0c;执行一些特定的命令行操作。 实现CommandLineRunner接口后&#xff0c;SpringBoot在启动的时候会自动执行run方法。通常&#xff0c;我们可以在run方法中进…
阅读更多...
TableStructureRec: 表格结构识别推理库来了

TableStructureRec: 表格结构识别推理库来了

目录 引言lineless_table_rec: 无线表格识别库安装使用结果 wired_table_rec&#xff1a;有线表格识别库安装使用结果 写在最后 引言 TableStructureRec 仓库是用来对文档中表格做结构化识别的推理库&#xff0c;包括来自 PaddleOCR 的表格结构识别算法模型、来自阿里读光有线…
阅读更多...
Python监控服务进程及自启动服务方法与实践

Python监控服务进程及自启动服务方法与实践

1. 需求概述 当我们在Windows Server环境中部署XX系统的实际应用中&#xff0c;往往会遇到一些运维管理的挑战。为了确保系统的持续稳定运行&#xff0c;特别是在服务程序因各种原因突然关闭的情况下&#xff0c;我们可以借助Python的强大生态系统来构建一个监控与自动重启的管…
阅读更多...
Linux下载工具XDM下载安装与使用

Linux下载工具XDM下载安装与使用

Windows上IDM多线程下载非常强大&#xff0c;即能捕捉页面上的视频、图片、音频&#xff0c;又能作为浏览器下载器使用&#xff0c;但是IDM无法在Linux下使用&#xff0c;除非使用wine。不过我们可以在Linux中用XDM(Xtreme Download Manager)代替IDM。 1、XDM下载 Xtreme Dow…
阅读更多...
线性回归中的函数求导

线性回归中的函数求导

在线性回归中&#xff0c;函数求导是一个重要的数学工具&#xff0c;用于计算损失函数关于模型参数的导数。通过求导&#xff0c;我们可以找到最优的参数值&#xff0c;以实现更好的线性回归拟合。 本文将介绍线性回归的基本原理&#xff0c;以及如何通过函数求导来优化线性回…
阅读更多...
C++设计模式之工厂模式（下）——抽象工厂模式

C++设计模式之工厂模式（下）——抽象工厂模式

抽象工厂模式 介绍示例示例使用运行结果抽象工厂模式的优缺点优点缺点 总结 介绍 抽象工厂模式是一种创建型设计模式&#xff0c;它提供了一种封装一组相关或相互依赖对象的方式&#xff0c;而无需指定它们具体的类。它允许客户端使用抽象接口来创建一系列相关的对象&#xff…
阅读更多...
Java常用类

Java常用类

目录 包装类 装箱和拆箱 包装类型和String的转换&#xff0c;包装类的常用方法 包装类 装箱和拆箱 package com.edu.wrapper;public class Interger01 {//演示int<-->Integer的装箱和拆箱//手动装箱int n1100;Integer integer new Integer(n1);Integer integer01 In…
阅读更多...
UML建模图文详解教程01——Enterprise Architect的安装与使用

UML建模图文详解教程01——Enterprise Architect的安装与使用

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Enterprise Architect概述 官方网站&#xff1a;https://www.sparxsystems.cn/products/ea/&#xff1b;图示如下&#xff1a; Enterprise Architect是一个全功能的、基于…
阅读更多...
【数据结构(四)】前缀、中缀、后缀表达式(逆波兰表达式)和逆波兰计算器的代码实现（2）

【数据结构(四)】前缀、中缀、后缀表达式(逆波兰表达式)和逆波兰计算器的代码实现（2）

文章目录 1. 前缀表达式(波兰表达式)1.1. 前缀表达式的计算机求值 2. 中缀表达式3. 后缀表达式(逆波兰表达式)3.1. 后缀表达式的计算机求值3.2. 逆波兰计算器的实现 4. 中缀表达式 转 后缀表达式4.1. 思路分析4.2. 代码实现 5. 逆波兰计算器的完整版 1. 前缀表达式(波兰表达式)…
阅读更多...
Django（十、中间件）

Django（十、中间件）

文章目录 一、中间件的介绍中间件有什么用中间件功能自定义中间中间件的顺序 一、中间件的介绍 中间件顾名思义&#xff0c;是介于request与response处理之间的一道处理过程&#xff0c;相对比较轻量级&#xff0c;并且在全局上改变django的输入与输出。因为改变的是全局&…
阅读更多...
【精选】​​深度学习：构建卷积神经网络的表情识别系统（源码＆教程）

【精选】​​深度学习：构建卷积神经网络的表情识别系统（源码＆教程）

1.研究背景与意义 随着社交媒体和在线通信的普及&#xff0c;人们越来越多地使用表情符号来表达情感和情绪。表情识别系统的发展成为一个重要的研究领域&#xff0c;旨在通过计算机自动识别和理解人类的表情&#xff0c;从而提高人机交互的效果和用户体验。 传统的表情识别方…
阅读更多...
Java之《ATM自动取款机》(面向对象)

Java之《ATM自动取款机》(面向对象)

《JAVA编程基础》项目说明 一、项目名称&#xff1a; 基于JAVA控制台版本银行自动取款机 项目要求&#xff1a; 实现银行自动取款机的以下基本操作功能&#xff1a;读卡、取款、查询。&#xff08;自动取款机中转账、修改密码不作要求&#xff09; 具体要求&#xff1a; 读卡…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站