队列实现栈与栈实现队列

文章目录

  • 前言
  • 一、使用队列实现栈
  • 二、使用栈实现队列

前言

1、用于巩固栈和队列。
2、本章是使用纯C语言实现的栈和队列，不懂的可以先看看这个喔：c语言实现栈和队列，当然这里直接用C++的栈和队列会更方便哦。
3、利于复习C语言的知识点。

一、使用队列实现栈

1·、题目链接：用队列实现栈
2、题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

3、例子：
在这里插入图片描述
4、题目分析：

（1）队列的操作是先进先出并且队头出，队尾进，而栈相反是先进后出，栈顶出，栈顶入。
（2）题目要求我们使用两个队列来实现这个栈的一些操作，如：push，pop等。 我们可以使用两个队列进行倒数据：
（3）进栈：将数据储存到有数据的队列里队尾（要是两个队列都为空的话随便进一个就行喔）
（4）出栈：将有数据的队列往没有数据的队列里倒，直到剩下一个数据之后停止倒数据，进行队列的出队操作即可将最后进的数据删除（也就是出栈）。
（5）取栈顶元素：查看有数据队列的队头即可。 （6）判断栈是否为空：即判断两个队列是否为空即可，两个队列为空栈就为空，不然就是不为空。

5、图解：
进栈：
在这里插入图片描述
出栈：
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/b9c9ef27c88b445ba0d12f329af7451f.png

6、参考代码：

typedef  int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

// 初始化队列 
void QueueInit(Queue* q)
{
	q->_front = NULL;
	q->_rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	//生成节点
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("err");
		return;
	}
	tmp->_data = data;
	tmp->_next = NULL;
	//没有节点
	if (q->_front ==NULL)
	{
		q->_front = q->_rear = tmp;
	}
	//有节点
	else
	{
		 q->_rear->_next=tmp;
		 q->_rear = tmp;
	}
	q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	//队列为空
	assert(q->_front);
	//队列只有一个元素或多个元素
	if (q->_front == q->_rear)
	{
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* tmp = q->_front;
	while (tmp!=NULL)
	{
		QNode* next = tmp->_next;
		free(tmp);
		tmp = next;
	}
	q->_front=q->_rear= NULL;
	q->size = 0;
}

//栈的结构体，因为通过两个队列来实现，所以成员为2个队列
typedef struct {
    Queue  q1;
    Queue  q2;
} MyStack;



/
//主要部分在下面，上面的是队列




//初始化栈
MyStack* myStackCreate() {
    //动态申请一个栈，如果直接创建 MyStack st 的话，这个栈会随着函数销毁而销毁，但是动态申请就不会
    MyStack *st=(MyStack*)malloc(sizeof(MyStack));
    //初始化两个队列
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

//进栈
void myStackPush(MyStack* obj, int x) {
    //往不为空的队列进
    if(!QueueEmpty(&obj->q1))
    {
      QueuePush(&obj->q1,x);
    }
    else
    {
      QueuePush(&obj->q2,x);
    }
}


//出栈
int myStackPop(MyStack* obj) {
     //将不为空的队列往空的队列倒，直到只剩下一个元素
     //假设p1是为空的队列 
     Queue *p1=&obj->q1;
     Queue *p2=&obj->q2;
     //假设不成立进行修正
     if(!QueueEmpty(p1))
     {
         p1=&obj->q2;
         p2=&obj->q1;
     }

     //倒数据
     while(QueueSize(p2)>1)
     {
          QueuePush(p1,QueueFront(p2));
          QueuePop(p2);
     }
     //先将最后一个保存再弹出
       int tmp=QueueBack(p2);
         QueuePop(p2);
         return tmp;
    
}

//取栈顶的元素
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);
    obj=NULL;
}

二、使用栈实现队列

1、题目链接：栈实现队列
2、题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek()返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

3、例子：
在这里插入图片描述
4、题目分析：

（1）通过两个栈来实现队列的push、pop等操作。
（2）我们可以固定一个栈（sta1）保存数据（进行入队操作），另一个栈（sta2）来进行展现队头数据和出队头的操作，当要展现队头数据和出队头的操作时，如果sta2为不空的话就展示栈顶的元素或者出栈，当sta2为空时就将sta1的数据倒到sat2里，再进行不为空的操作。
（3）取队头元素：直接取sta2的栈顶数据，（如果sta2为空的话就要将sta1的数据倒到sta2再取）
（4）判断队列是否为空：通过判断两个栈是否存在元素来判断是否为空，两个都为空即为空。

5、图解：
在这里插入图片描述
6、参考代码：

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

// 初始化栈 
void StackInit(Stack* ps)
{
    assert(ps);
    ps->_capacity = 0;
    ps->_a = NULL;
    ps->_top = 0;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
    //满了扩容
    if (ps->_capacity == ps->_top)
    {
        int size = 0;
        if (ps->_capacity == 0)
        {
                 size = 4;
        }
        else
        {
            size = ps->_capacity * 2;
        }
        STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * size);
        //判断
        if (tmp == NULL)
        {
            perror("err");
            return ;
        }
        ps->_a = tmp;
        ps->_capacity = size;
    }
    //入栈
    ps->_a[ps->_top] = data;
    ps->_top++;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->_top);
    return ps->_a[ps->_top - 1];
}

// 出栈 
void StackPop(Stack* ps)
{
    assert(ps);
    //栈为空 
    assert(ps->_top);
    ps->_a[ps->_top - 1] = 0;
    //栈不为空
    ps->_top--;
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->_top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
    assert(ps);
    return ps->_top == 0;
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}





//
//下面是主要部分，上面是栈





typedef struct {
    //存数据
     Stack sta1;
    //倒数据
     Stack sta2;
} MyQueue;

//初始化队列
MyQueue* myQueueCreate() {
    MyQueue* tmp=(MyQueue*)malloc(sizeof(MyQueue));
    //初始化两个栈
    StackInit(&tmp->sta1);
    StackInit(&tmp->sta2);
    //返回队列
      return tmp;
}
//进队
void myQueuePush(MyQueue* obj, int x) {
   //压进储存数据的sta1
    StackPush(&obj->sta1,x);
}

int myQueuePop(MyQueue* obj) {
    //sta2为空就倒数据
    int tmp=0;
    if(StackEmpty(&obj->sta2))
    {
     while(!StackEmpty(&obj->sta1))
    {
       StackPush(&obj->sta2,StackTop(&obj->sta1));
       StackPop(&obj->sta1);
    }  
    }
    //保存队头数据
    tmp=StackTop(&obj->sta2);
    //出队
     StackPop(&obj->sta2);
        return tmp;
}

int myQueuePeek(MyQueue* obj) {
    //sta2为空就倒数据
     if(StackEmpty(&obj->sta2))
     {
    while(!StackEmpty(&obj->sta1))
    {
       StackPush(&obj->sta2,StackTop(&obj->sta1));
       StackPop(&obj->sta1);
    }
     }
   //返回队头数据，不用出队
    int tmp=StackTop(&obj->sta2);
        return tmp;
}

//判断是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->sta1)&&StackEmpty(&obj->sta2);
}

//销毁队列
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->sta1);
    free(obj);
    obj=NULL;
}

以上就是分享的内容了，如有错误，评论区留言。

最后 ，谢谢大家的观看！

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

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

相关文章

吸猫毛空气净化器哪个好？推荐除猫毛效果好宠物空气净化器品牌

吸猫毛空气净化器哪个好？推荐除猫毛效果好宠物空气净化器品牌

当下有越来越多的家庭选择养宠物！尽管家里变得更加温馨，但养宠可能会带来异味和空气中的毛发增多可能会带来健康问题，这是一个大问题！ 不想家里弥漫着异味，特别是来自宠物便便的味道，所以需要一款能够处理…
阅读更多...
跨境知识分享：什么是动态IP？和静态IP有什么区别？

跨境知识分享：什么是动态IP？和静态IP有什么区别？

对于我们跨境人来说，清楚地了解IP地址、代理IP等这些基础知识，并学会正确地使用IP地址对于保障店铺的安全性和稳定性至关重要，尤其是理解动态IP和静态IP之间的区别，以及如何利用这些知识来防止账号关联，对于每个电商卖…
阅读更多...
什么是MAC地址? win10电脑查看MAC地址的多种方法

什么是MAC地址? win10电脑查看MAC地址的多种方法

您是否知道连接到家庭网络的每件硬件都有自己的身份？正如每个设备都分配有自己的 IP 地址一样，每个硬件都有一个唯一的网络标识符。 该标识符称为MAC 地址。MAC 代表媒体访问控制。您可能需要 MAC 地址来解决网络问题或配置新设备。在 Windows 中查找您…
阅读更多...
地图可视化绘制 | R-cartography 艺术地图绘制

地图可视化绘制 | R-cartography 艺术地图绘制

本期推文我们介绍一个可以绘制颇具“艺术”风格地图的可视化包-cartography，主要涉及的内容如下： R-cartography 简介 R-cartography 实例应用 所有完整代码都已整理之我们的线上课程，有需要的同学v yidianshuyulove 咨询 R-cartography …
阅读更多...
阿里云全面降价，释放了什么信号？

阿里云全面降价，释放了什么信号？

元宵节刚过，阿里云就放了一个大招—— 今天（2月29日）上午，阿里云发布通告，宣布全线下调云产品官网售价。这次降价涉及计算、存储、数据库等在内的100多款产品，平均降价幅度超过20%，最高降幅达55…
阅读更多...
day07_分类管理EasyExcel品牌管理

day07_分类管理EasyExcel品牌管理

文章目录 1 分类管理1.1 菜单添加1.2 表结构介绍1.3 页面制作1.4 列表查询1.4.1 需求分析1.4.2 后端接口CategoryCategoryControllerCategoryServiceCategoryMapperCategoryMapper.xml 1.4.3 前端对接category.jscategory.vue 2 EasyExcel2.1 数据导入导出意义2.2 EasyExcel简介…
阅读更多...
1950-2022年各省逐年平均降水量数据

1950-2022年各省逐年平均降水量数据

1950-2022年各省逐年平均降水量数据 1、时间：1950-2022年 2、指标：省逐年平均降水量 3、范围：33省（不含澳门） 4、指标解释：逐年平均降水数据是指当年的日降水量的年平均值，不是累计值&#…
阅读更多...
【leetcode】环形链表✚环形链表II

【leetcode】环形链表✚环形链表II

大家好，我是苏貝，本篇博客带大家刷题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️ 目录 1.环形链表解题拓展： 2.环形链表II 1.环形链表 点击查看题目 解题 思路: bool hasCycle…
阅读更多...
【问题记录】pip install遇到“No space left on device“

【问题记录】pip install遇到“No space left on device“

一、pip安装包的过程中出现以下问题 二、问题溯源 【1】刚开始以为是空间不足，后来 df -h 看了一下，pip安装目录下空间绝对足够！明显不是空间不足的问题。 【2】后来查了一下，发现是home目录下的空间满了，pip安装时&…
阅读更多...
一台工控机的能量

一台工控机的能量

使用Docker搭建EPICS的IOC记录 Zstack EPICS Archiver在小课题组的使用经验 以前电子枪调试，用一台工控机跑起束测后台，这次新光源用的电子枪加工回来又是测试，又是用一台工控机做起重复的事，不过生命在于折腾，重复的…
阅读更多...
计算机网络-网络互连和互联网（五）

计算机网络-网络互连和互联网（五）

1.路由器技术NAT： 网络地址翻译，解决IP短缺，路由器内部和外部地址进行转换。静态地址转换：静态NAT（一对一） 静态NAT，内外一对一转换，用于web服务器，ftp服务器等固定IP的…
阅读更多...
C++ 入门（七）— 基本数据类型

C++ 入门（七）— 基本数据类型

文章目录 Void整数有符号整数无符号整数固定宽度的整数和size_t 浮点数布尔值字符类型转换 Void Void 是最容易解释的数据类型。void 没有类型 不返回值的函数 最常见的是&#xff0c;void 用于指示函数不返回值&#xff1a; void writeValue(int x) {std::cout <<…
阅读更多...
【MySQL】数据库中常用的函数

【MySQL】数据库中常用的函数

目录 聚合函数COUNT()函数的多种用法COUNT(*)COUNT(主键)COUNT(1)COUNT(常量)COUNT(非主键)COUNT(distinct(字段)) COUNT()函数小结 字符函数length(str)函数&#xff1a;获取参数值的字节个数concat(str1,str2,...)函数&#xff1a;字符串拼接upper(str)、lower(str)函数:大小…
阅读更多...
部署Docker私有镜像仓库Harbor

部署Docker私有镜像仓库Harbor

Harbor介绍 Harbor 是为企业用户设计的开源镜像仓库项目&#xff0c;包括了权限管理(RBAC)、LDAP、审计、安全漏洞扫描、镜像验真、管理界面、自我注册、HA等企业必需的功能&#xff0c;同时针对中国用户的特点&#xff0c;设计镜像复制和中文支持等功能。 官网&#xff1a;h…
阅读更多...
kotlin开发环境搭建，算法题+JVM+自定义View

kotlin开发环境搭建，算法题+JVM+自定义View

什么是中年危机 根据权威数据显示&#xff0c;国内IT程序员鼎盛时期是在25-27岁左右&#xff0c;30岁对于程序员而言完全是一个38线&#xff0c;接着就是转业转岗的事情&#xff0c;这一点在业界也算是一个共识了。 大学毕业步入IT行业普遍年龄也是在22岁左右&#xff0c;然而…
阅读更多...
线程安全的队列

线程安全的队列

学习一下别人写的&#xff0c;线程安全的队列代码。https://github.com/markparticle/WebServer/blob/master/code/log/blockqueue.hhttps://github.com/markparticle/WebServer/blob/master/code/log/blockqueue.h /** Author : mark* Date : 2020-06-16* copy…
阅读更多...
20240301作业

20240301作业

1.使用fwrite、fread将一张随意的bmp图片&#xff0c;修改成德国的国旗 #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> int main(int argc, const char *argv[]) {FILE* fp fopen("./gaoda.bmp","…
阅读更多...
Attention 中的 Q, K, V

Attention 中的 Q, K, V

Attention 中的 Q, K, V flyfish Attention Is All You Need. Q query 查询 K key 键 V value 值 简单理解 一篇文章&#xff0c;文章的标题就是key&#xff0c;文章的内容就是V 使用搜索引擎时&#xff0c;输入到 搜索栏中的文本 就是 query 输入内容 query 与 文章标…
阅读更多...
你不可不知的数据安全词汇都在这！

你不可不知的数据安全词汇都在这！

关注公众号&#xff0c;回复关键词 “数据安全”&#xff0c;即可获取报告完整版 随着数字化时代的快速发展&#xff0c;数据安全已成为全球企业和组织面临的一项重大挑战。在这一背景下&#xff0c;我们深感需要有一个统一的、全面的数据安全术语基础&#xff0c;以便行业从业…
阅读更多...
P2040 打开所有的灯

P2040 打开所有的灯

题目传送门&#xff1a;P2040 打开所有的灯 用深度优先搜索实现的一个填色题。 题目步骤&#xff1a; 1..dfs 首先dfs要判断是否符合题意&#xff0c;如果符合题意就更新最短路&#xff1b; 如果不符合题意就枚举 如果是关的就把周围四个包括 给标记上和原来相反的&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023