【数据结构算法经典题目刨析(c语言)】使用队列实现栈(图文详解)

目录

一.题目描述

二.解题思路 

三.代码实现 

💓 博客主页:C-SDN花园GGbond

⏩ 文章专栏:数据结构经典题目刨析(c语言)

 

一.题目描述

二.解题思路 

首先这道题需要我们使用两个队列来完成栈的实现, 这里我们的思路是, 栈的要求是后进先出, 而队列是先进先出, 让两个队列来回导数据, 插入数据时, 插入到不为空的队列中, 如果需要出数据, 先让不为空的队列的前n-1个数据导入到为空的队列中, 然后在出数据, 此时正好就是最后一个数据, 也就是后入先出, 

以下是使用两个队列实现栈的基本步骤和原理: 

栈的结构定义:包含两个队列的结构

1.初始化:初始化两个空队列,在任意时刻,我们只会使用其中一个队列来进行入栈和出栈操作,     而另一个队列则保持为空。
2.入栈(Push):将元素添加到非空队列的末尾。

   如果两个队列都为空,则选择任意一个队列添加元素。
3.出栈(Pop):
  如果两个队列都为空,说明栈也为空,此时不能进行出栈操作。将非空队列中的元素(除了最后    一个)逐个出队并入队到另一个队列中,直到只剩下最后一个元    素。此时,该元素就是栈顶元    素,我们将其出队并返回。

4.查看栈顶元素(Peek):
   如果两个队列都为空,说明栈也为空,此时不能查看栈顶元素。
   如果队列的实现允许查看队尾数据,会比较简单,直接返回非空队列的队尾数据即可
   如果队列实现只允许查看队首数据,那么也需要移动元素
   我们将非空队列的元素(除了最后一个)逐个出队并入队到另一个队列中,直到只剩下最后一个    元素。此时,该元素就是栈顶元素,将其保存下来,入队到另一个队列中,并在本队列出队(这    样做是为了保持只有一个非空队列)然后返回该元素。

这里画图解释队列元素的移动过程(注意:为方便理解对队列的结构进行了简化)  

  

三.代码实现 

步骤如下 

1.因为C语言没有自带的队列, 所以我们需要把我们实现的队列写进去, C++会自带的队列.这里我们直接导入

2.创建MyStack,里面需要两个队列, myStackCreate其实也就是我们的初始化, 这里不可以直接 MyStack s, 因为函数里面的创建的变量出了函数就被释放了 ,所以我们需要动态开辟空间. 分别进行初始化

typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* s = (MyStack*)malloc(sizeof(MyStack));QueueInit(&s->q1);QueueInit(&s->q2);return s;
}

3.入栈, 哪个不为空, 我们就把元素插入到哪个队列, 这里我使用了假设法, 来找出不为空的队列.

void myStackPush(MyStack* obj, int x) {assert(obj);//假设法Queue* Empty = &obj->q1;Queue* nonEmpty = &obj->q2;if(QueueEmpty(&obj->q2)){Empty = &obj->q2;nonEmpty = &obj->q1;}//把数据插入到不为空的队列QueuePush(nonEmpty,x);
}

 

4.出栈, 还是假设法, 找到不为空的队列, 然后通过为空的队列导一下,不要忘记找到数据之后, 让最后一个数据出队列.

int myStackPop(MyStack* obj) {assert(obj);Queue* Empty = &obj->q1;Queue* nonEmpty = &obj->q2;if(QueueEmpty(&obj->q2)){Empty = &obj->q2;nonEmpty = &obj->q1;}//把不为空的队列的数据的前n-1个数据导入到为空的队列while(QueueSize(nonEmpty)>1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueTail(nonEmpty);QueuePop(nonEmpty);return top;
}

5.剩下的几个方法总体来说比较简单, 代码如下,注意销毁操作, 我们手动开辟的空间都需要手动释放.

int myStackTop(MyStack* obj) {assert(obj);if(!QueueEmpty(&obj->q1)){return QueueTail(&obj->q1);}else{return QueueTail(&obj->q2);}}bool myStackEmpty(MyStack* obj) {return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));
}void myStackFree(MyStack* obj) {assert(obj);QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

完整代码 


typedef int DataType;typedef struct QueueNode
{struct QueueNode* next;DataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, DataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!");//perror函数在<stdio.h>头文件包含,标准错误流return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq!=NULL);//条件为真,程序继续assert(pq->size!=0); //条件为真,程序继续if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}DataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}DataType QueueTail(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* s = (MyStack*)malloc(sizeof(MyStack));QueueInit(&s->q1);QueueInit(&s->q2);return s;
}void myStackPush(MyStack* obj, int x) {assert(obj);//假设法Queue* Empty = &obj->q1;Queue* nonEmpty = &obj->q2;if(QueueEmpty(&obj->q2)){Empty = &obj->q2;nonEmpty = &obj->q1;}//把数据插入到不为空的队列QueuePush(nonEmpty,x);
}int myStackPop(MyStack* obj) {assert(obj);Queue* Empty = &obj->q1;Queue* nonEmpty = &obj->q2;if(QueueEmpty(&obj->q2)){Empty = &obj->q2;nonEmpty = &obj->q1;}//把不为空的队列的数据的前n-1个数据导入到为空的队列while(QueueSize(nonEmpty)>1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top = QueueTail(nonEmpty);QueuePop(nonEmpty);return top;
}int myStackTop(MyStack* obj) {assert(obj);if(!QueueEmpty(&obj->q1)){return QueueTail(&obj->q1);}else{return QueueTail(&obj->q2);}}bool myStackEmpty(MyStack* obj) {return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));
}void myStackFree(MyStack* obj) {assert(obj);QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

 

 

 

 

 

 

 

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言进阶——一文带你深度了解“C语言关键字”(中篇6)

本篇文章记录我学习C语言进阶知识——C语言关键字&#xff0c;旨在记录分享&#xff0c;希望我的分享能带给你不一样的收获&#xff01; 目录 一、return关键字 二、const 关键字也许该被替换为 readolny &#xff08;一&#xff09;、 const 修饰的只读变量 &#xff08;二…

腾讯云COS和阿里云OSS在Springboot中的使用

引言&#xff1a;之前本来是用OSS做存储的&#xff0c;但是上线小程序发现OSS貌似消费比COS多一些&#xff0c;所以之前做了技术搬迁&#xff0c;最近想起&#xff0c;打算做个笔记记录一下&#xff0c;这里省去在阿里云注册OSS或腾讯云中注册COS应用了。 一、OSS 1、配置yml …

C ++ 也可以搭建Web?高性能的 C++ Web 开发框架 CPPCMS + MySQL 实现快速入门案例

什么是CPPCMS&#xff1f; CppCMS 是一个高性能的 C Web 开发框架&#xff0c;专为构建快速、动态的网页应用而设计&#xff0c;特别适合高并发和低延迟的场景。其设计理念类似于 Python 的 Django 或 Ruby on Rails&#xff0c;但针对 C 提供了更细粒度的控制和更高效的性能。…

Golang | Leetcode Golang题解之第330题按要求补齐数组

题目&#xff1a; 题解&#xff1a; func minPatches(nums []int, n int) (patches int) {for i, x : 0, 1; x < n; {if i < len(nums) && nums[i] < x {x nums[i]i} else {x * 2patches}}return }

【Python学习手册(第四版)】学习笔记19-函数的高级话题

个人总结难免疏漏&#xff0c;请多包涵。更多内容请查看原文。本文以及学习笔记系列仅用于个人学习、研究交流。 本文主要介绍函数相关的高级概念&#xff1a;递归函数、函数注解、lambda表达式函数&#xff0c;常用函数工具如map、filter、reduce&#xff0c;以及通用的函数设…

【超音速 专利 CN117576413A】种锂电池测试数据绑定方法、设备及存储介质

申请号CN202010618671.X公开号&#xff08;公开&#xff09;CN111967546A申请日2020.11.20申请人&#xff08;公开&#xff09;广州超音速自动化科技股份有限公司(833753)发明人&#xff08;公开&#xff09;张俊峰(总&#xff09;; 叶长春(总&#xff09;; 蓝明观 术语 治具…

【MySQL】数据库约束和多表查询

目录 1.前言 2.数据库约束 2.1约束类型 2.2 NULL约束 2.3 NUIQUE&#xff1a;唯一约束 2.4 DEFAULT&#xff1a;默认值约束 2.5 PRIMARY KEY&#xff1a;主键约束 2.6 FOREIGN KEY&#xff1a;外键约束 1.7 CHECK约束 3.表的设计 3.1一对一 3.2一对多 3.3多对多 …

vue3-02-vue3中的组件通信

目录 组件通信一、vue3组件通信和vue2的区别二、父子通信2.1 props通信1&#xff09;父→子传递数据&#xff08;父组件向子组件传递数据&#xff09;2&#xff09;子→父传递数据 2.2 v-model1&#xff09;v-model的本质2&#xff09;给modelValue起别名3&#xff09;$event 2…

用Python制作开心消消乐游戏|附源码

制作一个完整的“开心消消乐”风格的游戏在Python中是一个相对复杂的项目&#xff0c;因为它涉及到图形界面、游戏逻辑、动画效果以及用户交互等多个方面。不过&#xff0c;我可以为你提供一个简化的版本和概念框架&#xff0c;帮助你理解如何开始这个项目&#xff0c;并提供一…

英伟达元宇宙平台Omniverse的学习,技术调研

NVIDIA Omniverse™ 是一个基于 USD (Universal Scene Description) 的可扩展平台&#xff0c;可使个人和团队更快地构建自定义 3D 工作流并模拟大型虚拟世界。 Omniverse&#xff1a;三维设计协同、模拟的开发平台&#xff0c;实现3D实时渲染&#xff0c;RTX光线追踪技术 协…

职场英语培训柯桥外语学校学外语学英语到银泰泓畅学校

“工作量太大了”怎么说&#xff1f; 导致加班有一个非常大的因素就是&#xff1a; “工作量太大了&#xff01;” “ 注意&#xff1a;形容工作量太大不使用“big”一词&#xff0c;要用heavy&#xff0c;相应的要说工作量较小&#xff0c;可以用light. 工作量大/小 &…

数据中心互连的关键要素和核心技术

数据中心互连&#xff08;DCI&#xff09;依靠其关键要素和核心技术进行的高效、可靠和高速的连接&#xff0c;实现了数据中心跨区域连接的即时通信和数据交换&#xff0c;成为了现代数字通信基础设施的重要组成部分。从光模块和多路复用设备到网络协议和管理系统&#xff0c;D…

Leetcode75-5 反转字符串的元音字母

本质上来说就是反转字符串 一部分需要反转 一部分不动 思路: 1.用String字符串倒序拼接 就是过滤掉不是元音字符 然后把所有的字符&#xff08;非元音的直接复制过来 元音字母直接从反转的字符串里边复制即可&#xff09; 2.看了题解发现自己写的啰嗦了 就是一个双指针问题用…

酒店行业如何利用XML进行营销短信

随着信息社会的到来&#xff0c;消费者获得会所的服务也从单纯的电话方式&#xff0c;逐渐转变为电话、互联网、传真&#xff0c;群发短信等多种媒体并行的方式。今天着重介绍下酒店行业如何利用短信平台进行营销。 群发短信业务对酒店起到的效率&#xff1a;根据新产品或服务向…

java实现解析pdf格式发票

为了减少用户工作量及误操作的可能性&#xff0c;需要实现用户上传PDF格式的发票&#xff0c;系统通过解析PDF文件获取发票内容&#xff0c;并直接将其写入表单。以下文章记录了功能实现的代码。 发票样式 发票内容解析 引用Maven 使用pdfbox <dependency><groupI…

Spring Boot - 在Spring Boot中实现灵活的API版本控制(下)_ 封装场景启动器Starter

文章目录 Pre设计思路ApiVersion 功能特性使用示例配置示例 ProjectStarter Code自定义注解 ApiVersion配置属性类用于管理API版本自动配置基于Spring MVC的API版本控制实现WebMvcRegistrations接口&#xff0c;用于自定义WebMvc的注册逻辑扩展RequestMappingHandlerMapping的类…

前端CSS画图形

我以前一直很好奇&#xff0c;这些下拉菜单中的小箭头是怎么实现的&#xff0c;直到我看到了进阶的CSS。 OK&#xff0c;let me tell you hao to do. 想要实现这个效果&#xff0c;方法很多&#xff0c;我知道的就两个&#xff1a; 图片作弊法&#xff0c;CSS妙用法 图片作弊…

uni-app 开发App时调用uni-push 实现在线系统消息推送通知 保姆教程

一、引言 在开发App时避免不了需要推送系统通知&#xff0c;以提高用户的使用体验。在自己的一个工具型的小app上全流程接入了uni-push2.0的推送能力&#xff0c;做个记录&#xff0c;以防后期需要用到。在阅读本教程前最好先看看官方文档&#xff0c;结合官方文档使用&#xf…

下载免费设计素材,有这7个网站就够了

7个免费设计素材网站&#xff0c;这些网站提供了大量的免费资源&#xff0c;包括图片、字体、图标、模板等&#xff0c;涵盖了多种风格和主题&#xff0c;能够满足不同设计师和创作者的需求。无论是用于个人项目还是商业用途&#xff0c;这些网站都能给你提供丰富的选择&#x…

10步搞定Python爬虫从零到精通!

学习Python网络爬虫可以分为以下几个步骤&#xff0c;每一步都包括必要的细节和示例代码&#xff0c;以帮助你从零开始掌握这一技能。 第一步&#xff1a;理解网络爬虫基础 什么是网络爬虫&#xff1f; 网络爬虫是一种自动化程序,用来从互联网上收集数据.它通过发送 HTTP 请求…