用队列实现栈
目录
- 题目
- 题目要求
- 示例
- 解答
- 方法一、
- 实现思路
- 时间复杂度和空间复杂度
- 代码
- 方法二、
- 实现思路
- 时间复杂度和空间复杂度
- 代码
- 方法三、
- 实现思路
- 时间复杂度和空间复杂度
- 代码
- 总结
题目
用队列实现栈
题目要求
题目链接
示例
解答
方法一、
使用两个队列来实现栈。
实现思路
题目说了使用两个队列来实现栈的操作,我们知道栈结构的特点是元素后进先出,而队列的特点是先进先出。即栈的操作是尾插尾删,而队列的操作是尾插头删,所以我们可以将一个队列中按顺序将数据入队来模仿元素进栈。
当元素出栈时,我们可以将有元素的队列q1的数据依次出队,并且依次进入到另一个空的队列q2,当队列q1中只有一个元素时,我们停止将这个元素入队q2,因为这个元素就相当于栈顶元素。
此时我们将这个元素的空间释放即完成了栈中元素的出栈操作,并且此时队列q1也为空队列了,当有元素需要入栈时,将元素进入到不是空队列的队列中即可,当再需要出栈时,还重复上面的操作,将队列中的元素都进入到另一个队列,然后将最后一个结点释放即可。
时间复杂度和空间复杂度
时间复杂度:出栈为O(N),其余为O(1)
空间复杂度:O(N)
代码
include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDataType;
//队列的结点设计
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//创建一个Queue结构体变量,就相当于创建了一个队列,该结构体变量中存的有该队列的头结点地址,尾结点地址
//所以当有该结构体变量的地址时,可以通过该地址改变队列的头结点地址和尾结点地址,即改变head指针和tail指针。
typedef struct Queue
{QNode* head;QNode* tail;int size; //用来记录队列长度
}Queue;//队列初始化
void QueueInit(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//队列的销毁
void QueueDestroy(Queue* pq);//元素的入栈
void QueuePush(Queue* pq, QDataType x);//元素的出栈
void QueuePop(Queue* pq);//返回队头结点的数据
QDataType QueueFront(Queue* pq);//返回队尾结点的数据
QDataType QueueBack(Queue* pq);//返回队列的长度
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}bool QueueEmpty(Queue* pq)
{assert(pq);/*if (pq->head == NULL){return true;}else{return false;}*/return pq->head == NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->data = x;newNode->next = NULL;if (pq->head == NULL){pq->head = newNode;pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//当队列中只有一个结点时,该结点出队后队列就为空了//所以需要将队列的头指针和尾指针都置为NULLif (pq->head->next == NULL){free(pq->head);pq->head = NULL;//虽然按照下面的处理pq->head也会为NULL,//但tail指针还指向已经释放空间的最后一个结点的地址,所以此时tail为野指针,所以需要特别处理,将tail置为NULLpq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}}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);int size = 0;QNode* curr = pq->head;while (curr != NULL){size++;curr = curr->next;}return size;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* curr = pq->head;while (curr){QNode* next = curr->next;free(curr);curr = next;}pq->head = NULL;pq->tail = NULL;//在这里面将pq置为空没用,因为pq只是临时创建的一个Queue*类型的结构体指针//pq里面存的是Queue结构体变量的地址,在函数里面将pq置为NULL对外面没有影响。//只是让pq指向不了这个结构体变量了,但是这个结构体变量还存在,
}//该结构体采用了匿名结构体,然后将这个匿名结构体重命名为MyStack
typedef struct {//创建两个队列Queue q1;Queue q2;
} MyStack;
bool myStackEmpty(MyStack* obj);MyStack* myStackCreate() {//此时MyStack就相当于一个栈,当我们要使用一个栈时,先申请空间创建一个MyStack的结点MyStack* stack = (MyStack*)malloc(sizeof(MyStack));//然后我们初始化两个队列,因为我们定义的QueueInit函数的形参为Queue*类型的指针,//而MyStack结构体中定义的成员变量q1和q2为Queue类型,所以要将q1和q2的地址传过去。//如果传的是stack->q1的话,那么函数会临时创建一个Queue类型的变量tmp,然后函数里面tmp改变//但是stack结构体里面的q1不会改变。QueueInit(&(stack->q1));QueueInit(&(stack->q2));return stack;
}void myStackPush(MyStack* obj, int x) {assert(obj);//先设q1为空队列,q2为非空队列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空,说明设错了,则改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}QueuePush(noemptyQ,x);
}int myStackPop(MyStack* obj) {//先判断栈是否为空,如果为空则不可以出栈assert(obj);assert(!myStackEmpty(obj));//先设q1为空队列,q2为非空队列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空,说明设错了,则改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}//将非空队列的除了最后一个元素外的元素都进入到空队列中,while(QueueSize(noemptyQ)>1){QueuePush(emptyQ,QueueFront(noemptyQ));QueuePop(noemptyQ);}//将非空队列中最后一个元素返回int top = QueueFront(noemptyQ);//将队列中最后一个元素出队。此时非空队列变为空队列QueuePop(noemptyQ);//返回栈顶元素的数据return top;
}int myStackTop(MyStack* obj) {assert(obj);//返回栈顶元素就相当于返回非空队列的队尾结点的元素。//判断栈非空assert(!myStackEmpty(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);//先释放两个队列的空间,然后再释放obj的空间QueueDestroy(&(obj->q1));QueueDestroy(&(obj->q2));free(obj);
}
方法二、
使用两个队列来实现栈。
实现思路
第一种方法是入栈的元素直接入队,当出栈时才进行转换,将栈顶元素出栈。而这个方法是在入栈时就将队列中的元素排好出栈的顺序。
当元素入栈时,将元素进入一个空队列中,然后将另一个非空队列noempty的元素都进入空队列empty中,这样空队列empty中元素的出队顺序刚好和在栈中出栈的顺序一致。
当再有元素入栈时,重复上述操作即可。
时间复杂度和空间复杂度
时间复杂度:入栈为O(N),其余为O(1)
空间复杂度:O(N)
代码
该方法只有入栈和出栈还有返回栈顶元素的函数和第一种方法不同,只需将这三个函数改变即可。
void myStackPush(MyStack* obj, int x) {assert(obj);//先设q1为空队列,q2为非空队列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空,说明设错了,则改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}QueuePush(emptyQ,x);//将非空队列中的元素都进入空队列中while(QueueSize(noemptyQ)>0){QueuePush(emptyQ,QueueFront(noemptyQ));QueuePop(noemptyQ);}}int myStackPop(MyStack* obj) {//先判断栈是否为空,如果为空则不可以出栈assert(obj);assert(!myStackEmpty(obj));//先设q1为空队列,q2为非空队列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空,说明设错了,则改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}int top = QueueFront(noemptyQ);QueuePop(noemptyQ);return top;
}int myStackTop(MyStack* obj) {assert(obj);//此时非空队列中元素的顺序和出栈顺序一致,所以栈顶元素在队头assert(!myStackEmpty(obj));if(!QueueEmpty(&(obj->q1))){return QueueFront(&(obj->q1));}else{return QueueFront(&(obj->q2));}
}
方法三、
使用一个队列来实现栈。
实现思路
该方法只需要一个队列即可,当有元素要入栈时,在队列中的操作是将该元素先入队列,然后将该队列的队尾结点之前的结点都依次出队列再入队列,此时刚进入栈的元素即在队列的队头中,当要出栈时,直接将队头元素出队即可。
时间复杂度和空间复杂度
时间复杂度:入栈为O(N),其余为O(1)
空间复杂度:O(1)
代码
该方法因为只用了一个结构体,所以栈结构体中只创建了一个队列
/该结构体采用了匿名结构体,然后将这个匿名结构体重命名为MyStack
typedef struct {//创建一个队列Queue q1;
} MyStack;
bool myStackEmpty(MyStack* obj);MyStack* myStackCreate() {//此时MyStack就相当于一个栈,当我们要使用一个栈时,先申请空间创建一个MyStack的结点MyStack* stack = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(stack->q1));return stack;
}void myStackPush(MyStack* obj, int x) {assert(obj);//先将元素入队QueuePush(&(obj->q1),x);//然后将队列中队尾元素之前的结点都出队再入队int k = QueueSize(&(obj->q1))-1;while(k){QueuePush(&(obj->q1),QueueFront(&(obj->q1)));QueuePop(&(obj->q1));k--;}}int myStackPop(MyStack* obj) {//先判断栈是否为空,如果为空则不可以出栈assert(obj);assert(!myStackEmpty(obj));//此时队列中的队头元素即为栈顶元素int top = QueueFront(&(obj->q1));QueuePop(&(obj->q1));return top;
}int myStackTop(MyStack* obj) {assert(obj);//此时队列中的队头元素即为栈顶元素assert(!myStackEmpty(obj));return QueueFront(&(obj->q1));
}bool myStackEmpty(MyStack* obj) {assert(obj);//判断栈空就是判断队列是否为空return QueueEmpty(&(obj->q1));
}void myStackFree(MyStack* obj) {assert(obj);//先释放队列的空间,然后再释放obj的空间QueueDestroy(&(obj->q1));free(obj);
}
总结
用队列实现栈的第一种方法和第二种方法类似,不过一个是在入栈时进行处理,一个是在出栈时处理。而第三种方法只使用了一个队列,在入栈时做处理。
相关文章:

用队列实现栈
目录 题目题目要求示例 解答方法一、实现思路时间复杂度和空间复杂度代码 方法二、实现思路时间复杂度和空间复杂度代码 方法三、实现思路时间复杂度和空间复杂度代码 总结 题目 用队列实现栈 题目要求 题目链接 示例 解答 方法一、 使用两个队列来实现栈。 实现思路 题…...

Anolis 8.6 下 Redis 7.2.0 集群搭建和配置
Redis 7.2.0 搭建和集群配置 一.Redis 下载与单机部署1.Redis 下载2.虚拟机配置3.Redis 单机源码安装和测试4.Java 单机连接测试1.Pom 依赖2.配置文件3.启动类4.配置类5.单元测试6.测试结果 二.Redis 集群部署1.主从1.从节点配置2.Java 测试 2.哨兵1.哨兵节点配置2.复制一个哨兵…...

综合能源系统(8)——综合能源系统支撑技术
综合能源系统关键技术与典型案例 何泽家,李德智主编 1、大数据技术 1.1、大数据技术概述 大数据是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高…...
MySQL5.7数据目录结构
以CentOS7为例,数据目录为/var/lib/mysql/,其内容如下: [rootscentos szc]# ll /var/lib/mysql/ total 122952 -rw-r----- 1 mysql mysql 56 Jan 15 16:02 auto.cnf -rw------- 1 mysql mysql 1680 Jan 15 16:02 ca-key.pem -rw-r…...

Python Opencv实践 - 图像直方图均衡化
import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/pomeranian.png", cv.IMREAD_COLOR) print(img.shape)#图像直方图计算 #cv.calcHist(images, channels, mask, histSize, ranges, hist, accumulate) #images&…...

GAN:对抗生成网络,前向传播和后巷传播的区别
目录 GAN:对抗生成网络 损失函数 判别器开始波动很大,先调整判别器 生成样本和真实样本的统一:真假难辨编辑 文字专图片编辑 头像转表情包编辑 头像转3D编辑 后向传播 1. 前向传播(forward) 2. 反向传播&…...

压力变送器的功能与应用
压力变送器是用于测量气体或者液体等介质压力的设备,能够将压力转化为4 G信号传输到监控平台,工作人员可以在电脑或者手机上登录平台查看监测到的数据,并根据数据制定下一步的计划。 压力变送器的功能: 压力变送器采用了高性能感…...

排序算法:选择排序
选择排序的思想是:双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。 public static void selectionSort(int[] arr) {int minIndex;for (int i 0; i < arr.length - 1; i) {minIndex i;for (int j i …...

Windows运行Spark所需的Hadoop安装
解压文件 复制bin目录 找到winutils-master文件hadoop对应的bin目录版本 全部复制替换掉hadoop的bin目录文件 复制hadoop.dll文件 将bin目录下的hadoop.dll文件复制到System32目录下 配置环境变量 修改hadoop-env.cmd配置文件 注意jdk装在非C盘则完全没问题,如果装在…...

KusionStack使用文档
下载安装 1. 安装 Kusionup 如果想自定义默认安装版本,可以运行下述命令(将最后的 openlatest 替换为你想要默认安装的版本号就就行): curl -s "http://kusion-public.oss-cn-hzfinance.aliyuncs.com/cli/kusionup/script…...

ONLYOFFICE 文档如何与 Alfresco 进行集成
ONLYOFFICE 文档是一款开源办公套件,其是包含文本文档、电子表格、演示文稿、数字表单、PDF 查看器和转换工具的协作性编辑工具。要在 Alfresco 中使用 ONLYOFFICE 协作功能,可以将他们连接集成。阅读本文,了解这如何实现。 关于 ONLYOFFICE…...

PostgreSQL下载路径与安装步骤
PgSQL介绍 PgSQL和MySQL一样是一种关系模型的数据库,全称为PostgreSQL 数据库。 优势:PgSQL是一种可扩展、可靠、可定制的数据库管理系统,具有良好的数据完整性和安全性,支持多种操作系统,包括 Linux、Windows、MacOS …...
如何在PHP中编写条件语句
引言 决策是生活不可缺少的一部分。从平凡的着装决定,到改变人生的工作和家庭决定。在开发中也是如此。要让程序做任何有用的事情,它必须能够对某种输入做出响应。当用户点击网站上的联系人按钮时,他们希望被带到联系人页面。如果什么都没有…...

LLM架构自注意力机制Transformers architecture Attention is all you need
使用Transformers架构构建大型语言模型显著提高了自然语言任务的性能,超过了之前的RNNs,并导致了再生能力的爆炸。 Transformers架构的力量在于其学习句子中所有单词的相关性和上下文的能力。不仅仅是您在这里看到的,与它的邻居每个词相邻&…...

计算机网络 QA
DNS 的解析过程 浏览器缓存。当用户通过浏览器访问某域名时,浏览器首先会在自己的缓存中查找是否有该域名对应的 IP 地址(曾经访问过该域名并且没有清空缓存)系统缓存。当浏览器缓存中无域名对应的 IP 地址时,会自动检测用户计算机…...

安果天气预报 产品介绍
软件介绍版本号 2.0.5 安果天气预报:全世界覆盖,中国定制 想要查找北京、上海、纽约、东京还是巴黎的天气?一款简约的天气预 报应用为你呈现。专注于为用户提供纯净的天气体验,我们不发送任何打扰的通知。包含空气质量、能见度、…...

net start Mysql 启动服务时 ,显示“Mysql服务正在启动 Mysql服务无法启动 服务没有报告任何错误
一、问题 有时候,输入net start Mysql 启动服务时 mysql>net start Mysql 显示 Mysql服务正在启动 Mysql服务无法启动 服务没有报告任何错误 二、原因 由于mysql的默认端口是3306,因此在启动服务的时候,如果此端口被占用,就会出…...

DAY24
题目一 啊 看着挺复杂 其实很简单 第一种方法 就是纵轴是怪兽编号 横轴是能力值 看看能不能打过 逻辑很简单 看看能不能打得过 打过的就在花钱和直接打里面取小的 打不过就只能花钱 这种方法就导致 如果怪兽的能力值很大 那么我们就需要很大的空间 所以引出下一种做法 纵…...

Redis过期数据的删除策略
1 介绍 Redis 是一个kv型数据库,我们所有的数据都是存放在内存中的,但是内存是有大小限制的,不可能无限制的增量。 想要把不需要的数据清理掉,一种办法是直接删除,这个咱们前面章节有详细说过;另外一种就是…...

如何使用CSS实现一个拖拽排序效果?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 实现拖拽排序效果的CSS和JavaScript示例⭐ HTML 结构⭐ CSS 样式 (styles.css)⭐ JavaScript 代码 (script.js)⭐ 实现说明⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...