用队列实现栈oj题——225

在这里插入图片描述在这里插入图片描述

.

个人主页：晓风飞
专栏：LeetCode刷题|数据结构|Linux
路漫漫其修远兮，吾将上下而求索

文章目录

  • 题目要求：
    • 实现 MyStack 类：
    • 注意：
    • 示例：
    • 解释：
    • 提示：
  • 解题核心
  • 数据结构的定义
  • 初始化栈
  • 入栈（Push）操作
  • 出栈（Pop）操作
  • 获取栈顶元素（Top）：
  • 检查栈是否为空（Empty）：
  • 销毁栈（Free）：
  • 以下是队列的实现:
  • 以下是本题的实现:

要做题目的点击这里–>栈和队列oj题——225. 用队列实现栈

题目要求：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。
在这里插入图片描述
myStackCreate - 创建栈

解题核心

这个问题的核心思路在于使用两个队列（Queue）来模拟一个栈（Stack）的行为。栈是一种后进先出（LIFO, Last In First Out）的数据结构，而队列是一种先进先出（FIFO, First In First Out）的数据结构。要用队列模拟栈的行为，关键在于如何实现栈的两个主要操作：入栈（push）和出栈（pop）。

数据结构的定义

初始化两个队列，这两个队列将用于模拟栈的行为。

// 定义一个使用两个队列模拟的栈的结构体
typedef struct
{
    Queue q1; // 第一个队列
    Queue q2; // 第二个队列
} MyStack;

初始化栈

动态分配内存给新的栈,如果内存分配失败，输出错误信息并退出。

// 创建一个新的栈
MyStack* myStackCreate() 
{
    // 动态分配内存给新栈
    MyStack* newStack =(MyStack*)malloc(sizeof(MyStack));
    if (!newStack)
    {
        perror("malloc fail"); // 如果内存分配失败，输出错误信息并退出
        exit(-1);
    }

    // 初始化两个队列
    QInit(&(newStack->q1));
    QInit(&(newStack->q2));
    return newStack;  
}

入栈（Push）操作

在栈中，最新添加的元素总是被存储在栈的顶部。在使用两个队列模拟栈时，入栈操作相对直接：
选择一个非空队列进行操作：如果两个队列都是空的，可以选择任意一个队列进行操作。如果有一个非空队列，总是将新元素入队到这个非空队列。

// 将一个元素推入栈中
void myStackPush(MyStack* obj, int x) 
{
    assert(obj); // 确保栈对象非空
    // 总是将元素推入非空队列中
    if(!QueueEmpty(&obj->q1))
    {
        QPush(&obj->q1, x);
    }
    else
    {
        QPush(&obj->q2, x);
    }
}

出栈（Pop）操作

确定非空队列和空队列：首先识别出哪个队列是非空的（存有栈元素的队列），哪个队列是空的。

// 从栈中弹出一个元素
int myStackPop(MyStack* obj) 
{ 
    assert(obj); // 确保栈对象非空
    Queue* empty = &obj->q1; // 一个指向可能为空的队列的指针
    Queue* noEmpty = &obj->q2; // 一个指向非空队列的指针
    // 确定哪个队列是空的，哪个是非空的
    if(!QueueEmpty(empty))
    {
        empty = &obj->q2;
        noEmpty = &obj->q1;
    }
    // 将元素从非空队列转移到空队列，直到只剩下一个元素
    while(QueueSize(noEmpty) > 1)
    {
        QPush(empty, QueueFront(noEmpty));
        QPop(noEmpty);
    }
    // 弹出并返回最后一个元素
    int top = QueueFront(noEmpty);
    QPop(noEmpty);
    return top;
}

获取栈顶元素（Top）：

栈顶元素对应于最后进入非空队列的元素。可以通过查看非空队列的尾部元素来得知栈顶元素。

// 获取栈顶元素
int myStackTop(MyStack* obj)
{
    assert(obj); // 确保栈对象非空
    // 返回非空队列的尾部元素（栈顶元素）
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

检查栈是否为空（Empty）：

如果两个队列都为空，那么栈为空。

// 检查栈是否为空
bool myStackEmpty(MyStack* obj) 
{  
    assert(obj); // 确保栈对象非空
    // 如果两个队列都为空，栈为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

销毁栈（Free）：

释放栈所使用的资源，包括两个队列和栈本身的内存。

// 释放栈所占用的资源
void myStackFree(MyStack* obj) 
{
    assert(obj); // 确保栈对象非空
    // 销毁两个队列
    QDestroy(&obj->q1);
    QDestroy(&obj->q2);
    // 释放栈对象所占用的内存
    free(obj);
}

以下是队列的实现:

typedef int QDataType; // 定义队列数据类型为int

// 队列节点的结构体定义
typedef struct QueueNode
{
  QDataType val; // 节点存储的数据
  struct QueueNode* next; // 指向下一个节点的指针
} QNode;

// 队列的结构体定义
typedef struct Queue
{
  QNode* phead; // 指向队列头部的指针
  QNode* ptail; // 指向队列尾部的指针
  int size; // 队列的大小
} Queue;

// 函数声明
void QInit(Queue* pq); // 初始化队列
void QDestroy(Queue* pq); // 销毁队列

void QPush(Queue* pq, QDataType x); // 向队列中添加元素
void QPop(Queue* pq); // 从队列中移除元素

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

bool QueueEmpty(Queue* pq); // 检查队列是否为空
int QueueSize(Queue* pq); // 获取队列的大小

// 初始化队列
void QInit(Queue* pq)
{
  assert(pq); // 断言队列指针非空
  pq->phead = pq->ptail = NULL; // 将头指针和尾指针都设为NULL
  pq->size = 0; // 将队列大小设置为0
}

// 销毁队列
void QDestroy(Queue* pq)
{
  assert(pq); // 断言队列指针非空
  QNode* cur = pq->phead;
  while (cur)
  {
    QNode* next = cur->next; // 保存下一个节点
    free(cur); // 释放当前节点
    cur = next; // 移动到下一个节点
  }
  pq->phead = NULL; // 将头指针设为NULL
  pq->ptail = NULL; // 将尾指针设为NULL
  pq->size = 0; // 将队列大小设置为0
}

// 向队列中添加元素
void QPush(Queue* pq, QDataType x)
{
  assert(pq); // 断言队列指针非空
  QNode* newNode = (QNode*)malloc(sizeof(QNode)); // 分配新节点内存
  if (newNode == NULL)
  {
    perror("malloc fail"); // 内存分配失败处理
    exit(-1);
  }

  newNode->val = x; // 设置新节点的值
  newNode->next = NULL; // 新节点的下一个节点为NULL
  if (pq->ptail == NULL) // 如果队列为空
  {
    pq->phead = pq->ptail = newNode; // 队列头尾都指向新节点
  }
  else
  {
    pq->ptail->next = newNode; // 将新节点接到队列尾部
    pq->ptail = newNode; // 更新尾指针
  }
  pq->size++; // 队列大小增加
}

// 从队列中移除元素
void QPop(Queue* pq)
{
  assert(pq); // 断言队列指针非空
  assert(pq->phead); // 断言队列不为空
  QNode* Del = pq->phead; // 保存要删除的节点
  pq->phead = pq->phead->next; // 更新头指针
  free(Del); // 释放节点内存
  if (pq->phead == NULL) // 如果队列变空
  {
    pq->ptail = NULL; // 更新尾指针
  }
  pq->size--; // 队列大小减少
}

// 获取队列头部元素的值
QDataType QueueFront(Queue* pq)
{
  assert(pq); // 断言队列指针非空
  assert(pq->phead); // 断言队列不为空
  return pq->phead->val; // 返回头部元素的值
}

// 获取队列尾部元素的值
QDataType QueueBack(Queue* pq)
{
  assert(pq); // 断言队列指针非空
  assert(pq->ptail); // 断言队列不为空
  return pq->ptail->val; // 返回尾部元素的值
}

// 检查队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq); // 断言队列指针非空
  return pq->phead == NULL; // 如果头指针为NULL，则队列为空
}

// 获取队列的大小
int QueueSize(Queue* pq)
{
  return pq->size; // 返回队列的大小
}

以下是本题的实现:

// 定义一个使用两个队列模拟的栈的结构体
typedef struct
{
    Queue q1; // 第一个队列
    Queue q2; // 第二个队列
} MyStack;

// 创建一个新的栈
MyStack* myStackCreate() 
{
    // 动态分配内存给新栈
    MyStack* newStack =(MyStack*)malloc(sizeof(MyStack));
    if (!newStack)
    {
        perror("malloc fail"); // 如果内存分配失败，输出错误信息并退出
        exit(-1);
    }

    // 初始化两个队列
    QInit(&(newStack->q1));
    QInit(&(newStack->q2));
    return newStack;  
}

// 将一个元素推入栈中
void myStackPush(MyStack* obj, int x) 
{
    assert(obj); // 确保栈对象非空
    // 总是将元素推入非空队列中
    if(!QueueEmpty(&obj->q1))
    {
        QPush(&obj->q1, x);
    }
    else
    {
        QPush(&obj->q2, x);
    }
}

// 从栈中弹出一个元素
int myStackPop(MyStack* obj) 
{ 
    assert(obj); // 确保栈对象非空
    Queue* empty = &obj->q1; // 一个指向可能为空的队列的指针
    Queue* noEmpty = &obj->q2; // 一个指向非空队列的指针
    // 确定哪个队列是空的，哪个是非空的
    if(!QueueEmpty(empty))
    {
        empty = &obj->q2;
        noEmpty = &obj->q1;
    }
    // 将元素从非空队列转移到空队列，直到只剩下一个元素
    while(QueueSize(noEmpty) > 1)
    {
        QPush(empty, QueueFront(noEmpty));
        QPop(noEmpty);
    }
    // 弹出并返回最后一个元素
    int top = QueueFront(noEmpty);
    QPop(noEmpty);
    return top;
}

// 获取栈顶元素
int myStackTop(MyStack* obj)
{
    assert(obj); // 确保栈对象非空
    // 返回非空队列的尾部元素（栈顶元素）
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

// 检查栈是否为空
bool myStackEmpty(MyStack* obj) 
{  
    assert(obj); // 确保栈对象非空
    // 如果两个队列都为空，栈为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

// 释放栈所占用的资源
void myStackFree(MyStack* obj) 
{
    assert(obj); // 确保栈对象非空
    // 销毁两个队列
    QDestroy(&obj->q1);
    QDestroy(&obj->q2);
    // 释放栈对象所占用的内存
    free(obj);
}

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

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

相关文章

Redis概览

Redis概览

Redis存储是Key-Value结构的数据&#xff0c;其中Key是字符串类型&#xff0c;Value有5种常见的数据类型 字符串 String 哈希 hash 列表 list 集合 set 有序集合 sorted set / zset 各种数据类型的特性 字符串操作命令 : ● SET ke…
阅读更多...
Go-gin-example 添加注释 第一部分 新建项目及api编写

Go-gin-example 添加注释 第一部分 新建项目及api编写

文章目录 go-gin-example环境准备初始化 Go Modules基础使用 gin 安装测试gin是否引入 gin搭建Blog APIsgo-ini简述配置文件 阶段目标 编写简单API错误码包 完成一个demo初始化项目初始化项目数据库编写项目配置包拉取go-ini配置包在conf目录下新建app.ini文件&#xff0c;写入…
阅读更多...
数据结构排序（一.基本概念、插入排序和希尔排序实现）

数据结构排序（一.基本概念、插入排序和希尔排序实现）

前段时间也是结束了二叉树的知识梳理&#xff08;大家想必满脑子都是递归了&#xff09;&#xff1a;二叉树链式结构的实现(二叉树的遍历以及各种常用功能函数的实现) 今天也要迈向全新的篇章了——排序。这次就先大概讲解一下排序&#xff0c;然后插入排序和希尔排序的介绍和实…
阅读更多...
R304S 指纹识别模块功能实现示例

R304S 指纹识别模块功能实现示例

1 基本通信流程 1.1 UART 命令包的处理过程 1.2 UART 数据包的发送过程 UART 传输数据包前&#xff0c;首先要接收到传输数据包的指令包&#xff0c;做好传输准备后发送成功应答包&#xff0c;最后才开始传输数据包。数据包主要包括&#xff1a;包头、设备地址、包标识、包长…
阅读更多...
Spring IOC的四种手动注入方法

Spring IOC的四种手动注入方法

手动注入 1.Set方法注入-五种类型的注入1.1 业务对象JavaBean第一步&#xff1a;创建dao包下的UserDao类第二步&#xff1a;属性字段提供set⽅法第三步&#xff1a;配置⽂件的bean标签设置property标签第四步&#xff1a;测试 1.2 常用对象String&#xff08;日期类型&#xff…
阅读更多...
【AI视野·今日CV 计算机视觉论文速览 第282期】Wed, 3 Jan 2024

【AI视野·今日CV 计算机视觉论文速览 第282期】Wed, 3 Jan 2024

AI视野今日CS.CV 计算机视觉论文速览 Wed, 3 Jan 2024 Totally 70 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers Street Gaussians for Modeling Dynamic Urban Scenes Authors Yunzhi Yan, Haotong Lin, Chenxu Zhou, Weijie Wang, Haiya…
阅读更多...
togaf 9.2中文版

togaf 9.2中文版

尊敬的读者朋友们&#xff0c;本专栏为togaf 9.2 的个人学习笔记&#xff0c;我会尽量将信息完整地传递给大家&#xff0c;以便更多对 togaf 感兴趣的朋友不用花费巨资去购买相关资料。本文档不需要读者具备企业架构的预备知识。 专栏受众&#xff1a;企业架构师、业务架构师、…
阅读更多...
Android WiFi 连接

Android WiFi 连接

Android WiFi 连接 1、设置中WiFi显示2、WiFi 连接流程2.1 获取PrimaryClientModeManager2.2 ClientModeImpl状态机ConnectableState2.3 ISupplicantStaNetworkCallback 回调监听 3、 简要时序图4、原生低层驱动5、关键日志 1、设置中WiFi显示 Android WiFi基础概览 packages/a…
阅读更多...
阿里云服务器可用区是什么？

阿里云服务器可用区是什么？

阿里云服务器地域和可用区怎么选择&#xff1f;地域是指云服务器所在物理数据中心的位置&#xff0c;地域选择就近选择&#xff0c;访客距离地域所在城市越近网络延迟越低&#xff0c;速度就越快&#xff1b;可用区是指同一个地域下&#xff0c;网络和电力相互独立的区域&#…
阅读更多...
天津最新web前端培训班 如何提升web技能？

天津最新web前端培训班 如何提升web技能？

随着互联网的迅猛发展&#xff0c;web前端成为了一个热门的职业方向。越来越多的人希望能够通过学习web前端技术来提升自己的就业竞争力。为了满足市场的需求&#xff0c;许多培训机构纷纷推出了web前端培训课程。 什么是WEB前端 web前端就是web给用户展示的东西&#xff0c;…
阅读更多...
DataFunSummit：2023年知识图谱在线峰会-核心PPT资料下载

DataFunSummit：2023年知识图谱在线峰会-核心PPT资料下载

一、峰会简介 AIGC&#xff0c;ChatGPT以及发布的GPT-4相信已经给大家带来足够的冲击&#xff0c;那么对于知识图谱的应用产生哪些变化和变革&#xff1f;知识图谱在其中如何发挥作用呢&#xff1f;通过LLM是否有可能辅助创建通用大规模知识图谱&#xff1f;AIGC时代下行业知识…
阅读更多...
http缓存

http缓存

http缓存 header里缓存相关的属性 Expires 响应头,代表该资源的过期时间&#xff0c;在http1.0引入Cache-control 请求/响应头&#xff0c;可以配置缓存策略&#xff0c;在http1.1引入&#xff0c;与Expires同时存在时&#xff0c;优先使用Cache-controlIf-Modified-Since …
阅读更多...
实现在一个文件夹中找到特定名称特点格式的文件

实现在一个文件夹中找到特定名称特点格式的文件

当你要在一个文件夹中查找特定名称和格式的文件时&#xff0c;你可以使用 Python 的 os 和 fnmatch 模块。以下是一个简单的脚本示例&#xff0c;它可以在指定目录中查找文件&#xff1a; import os import fnmatchdef find_files(directory, pattern):"""在指…
阅读更多...
关于图像分割任务中按照比例将数据集随机划分成训练集和测试集

关于图像分割任务中按照比例将数据集随机划分成训练集和测试集

1. 前言 之前写了分类和检测任务划分数据集的脚本&#xff0c;三大任务实现了俩&#xff0c;基于强迫症&#xff0c;也实现一下图像分割的划分脚本 分类划分数据&#xff1a;关于图像分类任务中划分数据集&#xff0c;并且生成分类类别的josn字典文件 检测划分数据&#xff…
阅读更多...
【IDEA】 解决在idea中连接 Mysql8.0，驱动无法下载问题

【IDEA】 解决在idea中连接 Mysql8.0，驱动无法下载问题

本篇继【idea】解决sprintboot项目创建遇到的问题2-CSDN博客 目录 一、Failed to download https://download.jetbrains.com/idea/jdbc-drivers/MySQL/8/LICENSE.txt:Remote host terminated the handshake 二、no dirver files provided com.mysql.cj.jdbc.Driver 三、Serv…
阅读更多...
leetcode“位运算”——只出现一次的数字

leetcode“位运算”——只出现一次的数字

只出现一次的数字i&#xff1a; https://leetcode.cn/problems/single-number/ 给你一个非空整数数组 nums&#xff0c;除了某个元素只出现一次以外&#xff0c;其余每个元素均出现两次。找出那个只出现一次的元素。 class Solution { public:int singleNumber(vector<i…
阅读更多...
flink table view datastream互转

flink table view datastream互转

case class outer(f1:String,f2:Inner) case class outerV1(f1:String,f2:Inner,f3:Int) case class Inner(f3:String,f4:Int) 测试代码 package com.yy.table.convertimport org.apache.flink.streaming.api.scala.StreamExecutionEnvironment import org.apache.flink.tabl…
阅读更多...
强化学习的数学原理学习笔记 - 基于模型（Model-based）

强化学习的数学原理学习笔记 - 基于模型（Model-based）

文章目录 概览&#xff1a;RL方法分类基于模型&#xff08;Model-Based&#xff09;值迭代&#xff08;Value Iteration&#xff09;&#x1f7e6;策略迭代&#xff08;Policy Iteration&#xff09;&#x1f7e1;截断策略迭代&#xff08;Truncated Policy Iteration&#xff…
阅读更多...
从新手到大师：四大编程范式解锁你的编码力！

从新手到大师：四大编程范式解锁你的编码力！

编程&#xff0c;就是用代码跟计算机交流&#xff0c;告诉它我们想要它做什么。不同的编程范式就是不同的交流方式&#xff0c;每种方式都有自己独特的语法和规则。 今天&#xff0c;我们就来聊聊这四种主要的编程范式&#xff0c;它们分别是命令式、函数式、面向对象和声明式…
阅读更多...
cube生成电机库，启用了RTOS，编译报错[0xc43ed8:5050106] in osSignalWait

cube生成电机库，启用了RTOS，编译报错[0xc43ed8:5050106] in osSignalWait

cube生成电机库&#xff0c;启用了RTOS&#xff0c;编译报错[0xc43ed8:5050106&#xff0c;解决办法] in osSignalWait 1.现象 编译报错[0xc43ed8:5050106] in osSignalWait 导致链接失败 2.解决办法 将keil5的版本升级到5.18.00&#xff0c;我的版本也是5.14.00。
阅读更多...
最新文章

Copyright @ 2022~2023