速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧

2023-11-05 11:44
文章标签 实现 技巧 数据结构 队列 掌握 速学 难住

本文主要是介绍速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！


在这里插入图片描述

🎬 鸽芷咕：个人主页

 🔥个人专栏:《Linux深造日志》《C++干货基地》

⛺️生活的理想，就是为了理想的生活!

📋 前言

  🌈hello！ 各位铁铁们大家好啊，栈和队列我们都学过了那么试试用队列实现栈你会嘛？。
  ⛳️本篇文章就来给大家来篇如何用队列来实现栈的全部解析让你彻底拿捏队列。
  📚本期文章收录在《数据结构&算法》，大家有兴趣可以看看呐！
  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝！

文章目录

  • 📋 前言
  • 一、队列实现栈的具体功能
  • 二、队列实现栈的具体思路
    • 2.1 实现栈区的具体方法
    • 2.1 栈区的插入思路
    • 2.1 栈区的删除思路
  • 三、队列实现栈（具体代码）
    • 3.1 队列的准备
    • 3.2 栈区的初始化
    • 3.3 栈区的插入
    • 3.4 栈区的删除
    • 3.5 栈区的判空
    • 3.6 获取栈区的头元素
    • 3.7 栈区的销毁
  • 三、全部实现代码
  • 📝全篇总结

一、队列实现栈的具体功能

在这里插入图片描述

二、队列实现栈的具体思路

我们先来总结一下队列的特点 先进先出 ，队列的特点 是 后进先出 ：

  • 具体我们可以看一下下图来快速了解

在这里插入图片描述

  • 队列的特点是先进先出
  • 我们要实现栈的功能是后进先出

2.1 实现栈区的具体方法

我们是不是可以具体这样想，队列既然是先进先出，栈是后进先出，的意识就是我们需要每次获取的栈区数据是队列的最后一个：

  • ⁉️那可以不可以这样呢？
  • 开辟俩个队列空间，每次让其中一个为空
  • 另外一个不为空，这样就可以解决删除的问题了。

在这里插入图片描述

2.1 栈区的插入思路

这思路就很简单如果使用俩个指针来管理队列，那么插入就非常简单了，只需要考虑俩种情况：

  • 第一种当然是俩个栈区都为空的情况，还没开始插数据
  • 第二种就是已经插入数据了，那么插入的时候直接往不为空的栈区插入就好了。

2.1 栈区的删除思路

大家看如何我们使用俩个指针来管理队列，来实现栈的话那么来删除就非常简单了为什么这样说呢？

  • 既然一个队列永远为空，一个不为空
  • 那么删除的时候直接把不为空的队列插入到为空的队列
  • 留下最后一个元素用来删除就好了

在这里插入图片描述

三、队列实现栈（具体代码）

好了以上就是队列实现栈的核心思想了，只要核心思想掌握了，那么其他就是小菜了。下面我们就来快速实现一下吧：

3.1 队列的准备

这里是队列的实现代码，由于C语言库里面并没有队列这个数据结构我们就只能手动实现了：

  • 如果有想了解队列的可以看这篇文章：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QueDataType;typedef struct QueueType {QueDataType data;struct QueueType* next;
}QueueNode;typedef struct Queue {struct QueueType* head;struct QueueType* tail;int size;
}Que;//初始化队列
void QueueInit(Que* ps);
//销毁队列
void QueueDestroy(Que* ps);
//插入数据
void QueuePush(Que* ps, QueDataType x);
//删除数据
void QueuePop(Que* ps);
//获取头数据
QueDataType QueueFront(Que* ps);
//获取尾数据
QueDataType QueueBack(Que* ps);
//获取队列长度
int QueueSize(Que* ps);
//判断是否为空
bool QueueEmpty(Que* ps);//初始化队列
void QueueInit(Que* ps)
{assert(ps);ps->head = NULL;ps->tail = NULL;ps->size = 0;
}//销毁队列
void QueueDestroy(Que* ps)
{assert(ps);QueueNode* cur = ps->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}ps->head = ps->tail = NULL;ps->size = 0;
}//插入数据
void QueuePush(Que* ps, QueDataType x)
{assert(ps);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (ps->head == NULL){ps->head = ps->tail = newnode;}else{ps->tail->next = newnode;ps->tail = newnode;}ps->size++;
}//删除数据
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//获取头数据
QueDataType QueueFront(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}//获取尾数据
QueDataType QueueBack(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->tail->data;
}//获取队列长度
int QueueSize(Que* ps)
{assert(ps);return ps->size;
}//判断是否为空
bool QueueEmpty(Que* ps)
{assert(ps);return ps->head == NULL;
}

3.2 栈区的初始化

好了思路我们理清楚了接下来就是看看具体队列实现栈的代码到底如何实现：

  • 前面我们说过了使用俩个指针来管理队列就好了
  • 然后进行 malloc 申请空间就好了

📚 代码演示：

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

3.3 栈区的插入

插入的话我们思想已经都知道，下面就是考验你的代码能力了：

  • 如果俩个队列为空随便插入一个就好了
  • 否则就插入另一个队列

📚 代码演示：

void myStackPush(MyStack* obj, int x) {assert(obj);if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}

3.4 栈区的删除

删除的思想很简单，每次搬运一下队列就好了：

  • 这里使用了一个非常实用的判定方法大家可以去看看
  • 先假设一个为空一个不为空
  • 然后如果错了就换过来

📚 代码演示：

int myStackPop(MyStack* obj) {assert(obj);Que* empty = &obj->q1;Que* noempty = &obj->q2;if(!QueueEmpty(empty)){empty = &obj->q2;noempty = &obj->q1;}while(QueueSize(noempty) > 1){QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}int top = QueueFront(noempty);QueuePop(noempty);return top;
}

3.5 栈区的判空

这个就简单了只要栈中管理俩个队列的的都为空那当然都没有数据了：

  • QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)

📚 代码演示：

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

3.6 获取栈区的头元素

既然我们使用了俩个队列来实现栈，并且只有一个队列存放数据。

  • 那么只需要看哪个队列不为取出队尾数据就好了。

📚 代码演示：

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

3.7 栈区的销毁

老样子了，先把栈区里面的 malloc 里面的空间释放了，然后再释放栈就好了。

📚 代码演示：

void myStackFree(MyStack* obj) {  QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}

三、全部实现代码

📚 代码演示：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QueDataType;typedef struct QueueType {QueDataType data;struct QueueType* next;
}QueueNode;typedef struct Queue {struct QueueType* head;struct QueueType* tail;int size;
}Que;//初始化队列
void QueueInit(Que* ps);
//销毁队列
void QueueDestroy(Que* ps);
//插入数据
void QueuePush(Que* ps, QueDataType x);
//删除数据
void QueuePop(Que* ps);
//获取头数据
QueDataType QueueFront(Que* ps);
//获取尾数据
QueDataType QueueBack(Que* ps);
//获取队列长度
int QueueSize(Que* ps);
//判断是否为空
bool QueueEmpty(Que* ps);//初始化队列
void QueueInit(Que* ps)
{assert(ps);ps->head = NULL;ps->tail = NULL;ps->size = 0;
}//销毁队列
void QueueDestroy(Que* ps)
{assert(ps);QueueNode* cur = ps->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}ps->head = ps->tail = NULL;ps->size = 0;
}//插入数据
void QueuePush(Que* ps, QueDataType x)
{assert(ps);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (ps->head == NULL){ps->head = ps->tail = newnode;}else{ps->tail->next = newnode;ps->tail = newnode;}ps->size++;
}//删除数据
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//获取头数据
QueDataType QueueFront(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}//获取尾数据
QueDataType QueueBack(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->tail->data;
}//获取队列长度
int QueueSize(Que* ps)
{assert(ps);return ps->size;
}//判断是否为空
bool QueueEmpty(Que* ps)
{assert(ps);return ps->head == NULL;
}typedef struct {Que q1;Que q2;} MyStack;MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}void myStackPush(MyStack* obj, int x) {assert(obj);if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}int myStackPop(MyStack* obj) {assert(obj);Que* empty = &obj->q1;Que* noempty = &obj->q2;if(!QueueEmpty(empty)){empty = &obj->q2;noempty = &obj->q1;}while(QueueSize(noempty) > 1){QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}int top = QueueFront(noempty);QueuePop(noempty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* 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.chinasem.cn/article/349626。

相关文章

Java实现字节字符转bcd编码

Java实现字节字符转bcd编码

《Java实现字节字符转bcd编码》BCD是一种将十进制数字编码为二进制的表示方式,常用于数字显示和存储,本文将介绍如何在Java中实现字节字符转BCD码的过程,需要的小伙伴可以了解下... 目录前言BCD码是什么Java实现字节转bcd编码方法补充总结前言BCD码（Binary-Coded Decima
阅读更多...
SpringBoot全局域名替换的实现

SpringBoot全局域名替换的实现

《SpringBoot全局域名替换的实现》本文主要介绍了SpringBoot全局域名替换的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录 项目结构⚙️ 配置文件application.yml️ 配置类AppProperties.Ja
阅读更多...
Python实现批量CSV转Excel的高性能处理方案

Python实现批量CSV转Excel的高性能处理方案

《Python实现批量CSV转Excel的高性能处理方案》在日常办公中,我们经常需要将CSV格式的数据转换为Excel文件,本文将介绍一个基于Python的高性能解决方案,感兴趣的小伙伴可以跟随小编一... 目录一、场景需求二、技术方案三、核心代码四、批量处理方案五、性能优化六、使用示例完整代码七、小结一、
阅读更多...
Java实现将HTML文件与字符串转换为图片

Java实现将HTML文件与字符串转换为图片

《Java实现将HTML文件与字符串转换为图片》在Java开发中,我们经常会遇到将HTML内容转换为图片的需求,本文小编就来和大家详细讲讲如何使用FreeSpire.DocforJava库来实现这一功... 目录前言核心实现：html 转图片完整代码场景 1：转换本地 HTML 文件为图片场景 2：转换 H
阅读更多...
C#使用Spire.Doc for .NET实现HTML转Word的高效方案

C#使用Spire.Doc for .NET实现HTML转Word的高效方案

《C#使用Spire.Docfor.NET实现HTML转Word的高效方案》在Web开发中,HTML内容的生成与处理是高频需求,然而,当用户需要将HTML页面或动态生成的HTML字符串转换为Wor... 目录引言一、html转Word的典型场景与挑战二、用 Spire.Doc 实现 HTML 转 Word1
阅读更多...
C#实现一键批量合并PDF文档

C#实现一键批量合并PDF文档

《C#实现一键批量合并PDF文档》这篇文章主要为大家详细介绍了如何使用C#实现一键批量合并PDF文档功能,文中的示例代码简洁易懂,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言效果展示功能实现1、添加文件2、文件分组（书签）3、定义页码范围4、自定义显示5、定义页面尺寸6、PDF批量合并7、其他方法
阅读更多...
SpringBoot实现不同接口指定上传文件大小的具体步骤

SpringBoot实现不同接口指定上传文件大小的具体步骤

《SpringBoot实现不同接口指定上传文件大小的具体步骤》：本文主要介绍在SpringBoot中通过自定义注解、AOP拦截和配置文件实现不同接口上传文件大小限制的方法,强调需设置全局阈值远大于... 目录一  springboot实现不同接口指定文件大小1.1 思路说明1.2 工程启动说明二 具体实施2
阅读更多...
Python实现精确小数计算的完全指南

Python实现精确小数计算的完全指南

《Python实现精确小数计算的完全指南》在金融计算、科学实验和工程领域,浮点数精度问题一直是开发者面临的重大挑战,本文将深入解析Python精确小数计算技术体系,感兴趣的小伙伴可以了解一下... 目录引言：小数精度问题的核心挑战一、浮点数精度问题分析1.1 浮点数精度陷阱1.2 浮点数误差来源二、基础解决
阅读更多...
Java实现在Word文档中添加文本水印和图片水印的操作指南

Java实现在Word文档中添加文本水印和图片水印的操作指南

《Java实现在Word文档中添加文本水印和图片水印的操作指南》在当今数字时代,文档的自动化处理与安全防护变得尤为重要,无论是为了保护版权、推广品牌,还是为了在文档中加入特定的标识,为Word文档添加... 目录引言Spire.Doc for Java：高效Word文档处理的利器代码实战：使用Java为Wo
阅读更多...
Java实现远程执行Shell指令

Java实现远程执行Shell指令

《Java实现远程执行Shell指令》文章介绍使用JSch在SpringBoot项目中实现远程Shell操作,涵盖环境配置、依赖引入及工具类编写,详解分号和双与号执行多指令的区别... 目录软硬件环境说明编写执行Shell指令的工具类总结jsch(Java Secure Channel)是SSH2的一个纯J
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2