用队列实现栈

目录

  • 题目
    • 题目要求
    • 示例
  • 解答
    • 方法一、
      • 实现思路
      • 时间复杂度和空间复杂度
      • 代码
    • 方法二、
      • 实现思路
      • 时间复杂度和空间复杂度
      • 代码
    • 方法三、
      • 实现思路
      • 时间复杂度和空间复杂度
      • 代码
  • 总结

题目

用队列实现栈

题目要求

在这里插入图片描述
题目链接

示例

解答

方法一、

使用两个队列来实现栈。

实现思路

题目说了使用两个队列来实现栈的操作，我们知道栈结构的特点是元素后进先出，而队列的特点是先进先出。即栈的操作是尾插尾删，而队列的操作是尾插头删，所以我们可以将一个队列中按顺序将数据入队来模仿元素进栈。
在这里插入图片描述
当元素出栈时，我们可以将有元素的队列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));
	//当队列中只有一个结点时，该结点出队后队列就为空了
	//所以需要将队列的头指针和尾指针都置为NULL
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = NULL;
		//虽然按照下面的处理pq->head也会为NULL，
		//但tail指针还指向已经释放空间的最后一个结点的地址，所以此时tail为野指针，所以需要特别处理，将tail置为NULL
		pq->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);
}

总结

用队列实现栈的第一种方法和第二种方法类似，不过一个是在入栈时进行处理，一个是在出栈时处理。而第三种方法只使用了一个队列，在入栈时做处理。

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

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

相关文章

科技成果鉴定测试有什么意义?专业CMA、CNAS软件测评公司

科技成果鉴定测试有什么意义?专业CMA、CNAS软件测评公司

科技成果鉴定测试是指通过一系列科学的实验和检测手段&#xff0c;对科技成果进行客观评价和鉴定的过程。通过测试&#xff0c;可以对科技成果的技术优劣进行评估&#xff0c;从而为科技创新提供参考和指导。 一、科技成果鉴定测试的意义 1、帮助客户了解科技产品的性能特点和…
阅读更多...
【Spring】一次性打包学透 Spring | 阿Q送书第五期

【Spring】一次性打包学透 Spring | 阿Q送书第五期

文章目录 如何竭尽可能确保大家学透Spring1. 内容全面且细致2. 主题实用且本土化3. 案例系统且完善4. 知识有趣且深刻 关于作者丁雪丰业内专家推图书热卖留言提前获赠书 不知从何时开始&#xff0c;Spring 这个词开始频繁地出现在 Java 服务端开发者的日常工作中&#xff0c;很…
阅读更多...
nvm安装使用教程

nvm安装使用教程

文章目录 下载配置安装最新稳定版 node安装指定版本查看版本切换版本删除版本 常见问题安装node后 显示拒绝访问的问题使用cnpm会报错的问题降低cnpm版本npm镜像 下载 NVM for Windows 下载地址&#xff1a;https://link.juejin.cn/?targethttps%3A%2F%2Fgithub.com%2Fcoreyb…
阅读更多...
java学习网站_Java程序员必看的学习网站

java学习网站_Java程序员必看的学习网站

哔哩哔哩 B 站动力节点官方视频 https://space.bilibili.com/76542346?spm_id_from333.337.0.0 超多视频免费白嫖 专注 java 培训的动力节点 毕业学员业内高薪就业&#xff0c;逐渐得到了业界广大的好评&#xff0c;被业界誉为 “口口相传的 Java 黄埔军校 “。 网址&#x…
阅读更多...
【计算机网络】【常考问题总结】

【计算机网络】【常考问题总结】

1. ping 127.0.0.1 后会发生什么&#xff1f; ping 127.0.0.1 &#xff1b;ping 0.0.0.0 &#xff1b; ping localhost 面试官问&#xff1a;断网了&#xff0c;还能ping通 127.0.0.1 吗&#xff1f;为什么&#xff1f;_kevin_tech的博客-CSDN博客 2. MTU&#xff0c;MMU是…
阅读更多...
某多多商品平台数据采集

某多多商品平台数据采集

某多多商品平台数据采集 声明逆向目标寻找加密位置代码分析补环境补充内容声明 本文章中所有内容仅供学习交流，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者 无关，若有侵权，请私信我立即删除! 逆向目标 Anti-Content参数 寻找加密位置 先在控制台全局搜…
阅读更多...
【从零学习python 】69. 网络通信及IP地址分类解析

【从零学习python 】69. 网络通信及IP地址分类解析

文章目录 网络通信的概念IP地址IP地址的分类A类地址B类地址C类地址D类地址E类地址私有地址 进阶案例 网络通信的概念 简单来说&#xff0c;网络是用物理链路将各个孤立的工作站或主机相连在一起&#xff0c;组成数据链路&#xff0c;从而达到资源共享和通信的目的。 使用网络…
阅读更多...
k8s-ingress-context deadline exceeded

k8s-ingress-context deadline exceeded

报错&#xff1a; rancher-rke-01:~/rke # helm install rancher rancher-latest/rancher --namespace cattle-system --set hostnamewww.rancher.local Error: INSTALLATION FAILED: Internal error occurred: failed calling webhook "validate.nginx.ingress.kube…
阅读更多...
leetcode 118.杨辉三角

leetcode 118.杨辉三角

⭐️ 题目描述 &#x1f31f; leetcode链接&#xff1a;https://leetcode.cn/problems/pascals-triangle/description/ 代码&#xff1a; class Solution { public:vector<vector<int>> generate(int numRows) {// 先开空间vector<vector<int>> v;v.…
阅读更多...
这样管理销售线索，销售成功率增加30%！

这样管理销售线索，销售成功率增加30%！

当你的内容、产品或服务吸引到他人的注意时&#xff0c;你就拥有了一个潜在客户。这条线索能否转化为客户&#xff0c;很大程度上取决于你的线索管理流程的质量。 但是&#xff0c;这个流程到底是什么样的&#xff0c;如何才能让它为你的业务服务呢&#xff1f; 什么是线索管理…
阅读更多...
不在同一局域网也想轻松使用RDP？向日葵远程控制帮你实现

不在同一局域网也想轻松使用RDP？向日葵远程控制帮你实现

不在同一局域网也想轻松使用RDP&#xff1f;向日葵远程控制帮你实现 很多极客朋友家中或者办公室有不止一台PC电脑需要同时操作&#xff0c;但人挪来挪去始终不太方便&#xff0c;于是就有很多朋友采用微软自带的RDP桌面功能&#xff0c;实现在一台电脑上同时操作多台设备&…
阅读更多...
Pyqt5打开电脑摄像头进行拍照

Pyqt5打开电脑摄像头进行拍照

目录 1、设计UI界面 2、设计逻辑代码&#xff0c;建立连接显示窗口 3、结果 1、设计UI界面 将ui界面转为py文件后获得的逻辑代码为&#xff1a;&#xff08;文件名为 Camera.py&#xff09; # -*- coding: utf-8 -*-# Form implementation generated from reading ui file …
阅读更多...
Oracle 查询（当天，月，年）的数据

Oracle 查询（当天，月，年）的数据

Trunc 在oracle中&#xff0c;可利用 trunc函数 查询当天数据&#xff0c;该函数可用于截取时间或者数值&#xff0c;将该函数与 select 语句配合使用可查询时间段数据 查询当天数据 --sysdate是获取系统当前时间函数 --TRUNC函数用于截取时间或者数值&#xff0c;返回指定的…
阅读更多...
如何向学校图书馆推荐数据库？

如何向学校图书馆推荐数据库？

学校图书馆在满足师生学习和研究需求方面起着至关重要的作用。作为一名学生或研究员&#xff0c;您可能会意识到某些数据库对于学校的教学和研究至关重要。遇到拥有优质数据的数据库如何向学校图书馆推荐呢&#xff1f; 一、了解学校需求。 在向学校图书馆推荐数据库之前&…
阅读更多...
【【萌新的STM32学习-16中断的基本介绍1】】

【【萌新的STM32学习-16中断的基本介绍1】】

萌新的STM32学习-16中断的基本介绍1 中断 什么是中断 中断是打断CPU执行正常的程序&#xff0c;转而处理紧急程序&#xff0c;然后返回原暂停的程序继续执行&#xff0c;就叫中断 中断的作用 实时控制 &#xff1a; 就像对温度进行控制 故障控制 &#xff1a; 第一时间对突发情…
阅读更多...
【HTML】HTML面试知识梳理

【HTML】HTML面试知识梳理

目录 DOCTYPE&#xff08;文章类型&#xff09;head标签浏览器乱码的原因及解决常用的meta标签与SEOscript标签中defer和async的区别src&href区别HTML5有哪些更新语义化标签媒体标签表单进度条、度量器DOM查询Web存储Canvas和SVG拖放 &#xff08;HTML5 drag API&#xff0…
阅读更多...
UWB超宽带定位技术介绍

UWB超宽带定位技术介绍

UWB超宽带定位技术介绍 UWB系统是近几年来非常热门的一个技术&#xff0c;UWB技术使用两种方式传输数据&#xff1a;一种是无线收发&#xff0c;利用卫星信号进行传输&#xff0c;另一种是通过无线通信的方式传输数据。 无线收发采用的模式主要是同步、异步和自适应多址。 一…
阅读更多...
谈谈智能交通的概念

谈谈智能交通的概念

目录 1.什么是智能交通 2.智能交通的应用场景 1.智能公交车 2.共享单车 3.汽车联网 4.智慧停车 1.什么是智能交通 智能交通是指运用信息技术和通信技术等现代技术手段&#xff0c;对交通运输系统进行智能化的管理和优化&#xff0c;以提高交通效率、安全性和环境友好性的一…
阅读更多...
成集云 | 抖店连接器客户静默下单催付数据同步钉钉 | 解决方案

成集云 | 抖店连接器客户静默下单催付数据同步钉钉 | 解决方案

源系统成集云目标系统 方案介绍 随着各品牌全渠道铺货&#xff0c;主播在平台上直播时客户下了订单后不能及时付款&#xff0c;第一时间客户收不到提醒&#xff0c;不仅造成了客户付款率下降&#xff0c;更大量消耗了企业的人力成本和经济。而成集云与钉钉深度合作&#xff0…
阅读更多...
Unity——DOTween插件使用方法简介（上）

Unity——DOTween插件使用方法简介（上）

例子演示&#xff1a; DOTween移动 缓动动画既是一种编程技术&#xff0c;也是一种动画的设计思路。从设计角度来看&#xff0c;可以有以下描述 事先设计很多基本的动画样式&#xff0c;如移动、缩放、旋转、变色和弹跳等。但这些动画都以抽象方式表示&#xff0c;一般封装为程…
阅读更多...
最新文章

Copyright @ 2022~2023