如何用两个栈实现队列的先进先出?

2023-11-02 06:32

本文主要是介绍如何用两个栈实现队列的先进先出?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、分析问题
我们学完了栈和队列,也对这两个线性结构有了一定的了解,那么我们今天来看一看如何用栈实现队列的特性,先进先出呢?显然一个栈是完成不了的。
首先我们需要两个空栈,我们指定一个栈stack1当数据来的时候先入stack1,然后将栈stack1的元素依次弹出,弹出元素依次入栈stack2,然后在依次弹出stack2的元素就好了,但是细心的朋友有没有发现一个问题,如果我们弹出1、2,在3、4,没有弹出以前stack1又来了5、6,那怎么办?
在这里插入图片描述
在这里插入图片描述

所以我们要保证的是在有元素入栈stack1以前栈stack2是空的,也就是如果此时有元素要入栈stack1且栈stack2内有元素,要先将栈stack2内的元素全部压回栈stack1,stack2为空栈,再进行新元素入栈stack1的操作,同样道理在接下来对stack2进行Pop时也要保证stack1中的元素已经全部弹出压入stack2,也就是stack1是空栈。
二、代码实现分析
既然是用栈实现队列,那么就一定会用到我们之前学到的,对栈的一系列的操作代码。当然没用到那么多,那让我们看看需要我们新实现的部分,我们需要两个栈去充当一个队列,那么还需要一个队列计数器变量来实现监控队列里的元素个数,可以把这三个变量封装在一个结构体里面,还需要对我们的这个结构体进行初始化,说白了就是调用栈的初始化来对这个结构体里面的两个栈进行初始化,然后对队列的Push和Pop也要通过栈的Push和Pop重新完成。
三、代码实现

#include<stdio.h>
#include<stdlib.h>typedef struct data
{int nValue;struct data *pNext;
}MyStack;typedef struct stack
{int nCount;MyStack *pTop;
}Stack;void s_Init(Stack **pStack)
{*pStack = (Stack*)malloc(sizeof(Stack));(*pStack)->nCount = 0;(*pStack)->pTop = NULL;
}void s_Push(Stack *pStack,int nNum)
{if(pStack == NULL){printf("不存在\n");return;}MyStack *pTemp = NULL;pTemp = (MyStack*)malloc(sizeof(MyStack));pTemp->nValue = nNum;pTemp->pNext = pStack->pTop;pStack->pTop = pTemp;pStack->nCount ++;
}int s_Pop(Stack *pStack)
{if(pStack == NULL) exit(1);if(pStack->pTop == NULL) return -1;MyStack *pDel = pStack->pTop;int nNum = pDel->nValue;pStack->pTop = pStack->pTop->pNext;free(pDel);pDel = NULL;pStack->nCount --;return nNum;
}int s_IsEmpty(Stack *pSatck)
{if(pSatck == NULL) exit(1);return pSatck->nCount ? 0:1;
}
//以下是新代码typedef struct queue
{int nCount;Stack *pStack1;Stack *pStack2;
}Queue;void q_Init(Queue **pQueue)
{*pQueue = (Queue *)malloc(sizeof(Queue));(*pQueue)->nCount = 0;s_Init(&(*pQueue)->pStack1);s_Init(&(*pQueue)->pStack2);
}void q_Push(Queue *pQueue,int nNum)
{if(pQueue == NULL) exit(1);//栈1入队//栈2非空 将栈2元素放回栈1 在向栈1压入while(!s_IsEmpty(pQueue->pStack2)){s_Push(pQueue->pStack1,s_Pop(pQueue->pStack2));}s_Push(pQueue->pStack1,nNum);pQueue->nCount ++;
}int q_Pop(Queue *pQueue)
{if(pQueue == NULL) exit(1);if(pQueue ->nCount==0) return -1;//栈2出队//栈1非空 将栈1元素压入栈2 栈2弹出while(!s_IsEmpty(pQueue->pStack1)){s_Push(pQueue->pStack2,s_Pop(pQueue->pStack1));}int nNum = s_Pop(pQueue->pStack2);pQueue->nCount --;return nNum;}int main()
{Queue *pQueue = NULL;q_Init(&pQueue);q_Push(pQueue,1);q_Push(pQueue,2);q_Push(pQueue,3);q_Push(pQueue,4);printf("%d\n",q_Pop(pQueue));printf("%d\n",q_Pop(pQueue));q_Push(pQueue,5);printf("%d\n",q_Pop(pQueue));q_Push(pQueue,6);printf("%d\n",q_Pop(pQueue));printf("%d\n",q_Pop(pQueue));printf("%d\n",q_Pop(pQueue));return 0;
}

在这里插入图片描述

这篇关于如何用两个栈实现队列的先进先出?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/328778

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

PyQt6/PySide6中QTableView类的实现

《PyQt6/PySide6中QTableView类的实现》本文主要介绍了PyQt6/PySide6中QTableView类的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学... 目录1. 基本概念2. 创建 QTableView 实例3. QTableView 的常用属性和方法

PyQt6/PySide6中QTreeView类的实现

《PyQt6/PySide6中QTreeView类的实现》QTreeView是PyQt6或PySide6库中用于显示分层数据的控件,本文主要介绍了PyQt6/PySide6中QTreeView类的实现... 目录1. 基本概念2. 创建 QTreeView 实例3. QTreeView 的常用属性和方法属性

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType?FIT_XYFIT_STARTFIT_CENTE

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服