使用2个栈实现队列及其最大容量
发布日期:2021-10-02 06:27:34 浏览次数:2 分类:技术文章

本文共 1292 字,大约阅读时间需要 4 分钟。

文章目录

前言

通过我们在数据结构中的学习(或者可以直接看博主的《》),我们知道:

  • 栈是先进后出的数据结构
  • 队列是先进先出的数据结构

即栈是逆序的,队列是顺序的,因此我们通过两个栈(逆序的逆序为顺序)可以实现队列

实现思路

利用2个栈stack1stack2实现队列

  1. 将元素压入到stack1用来模拟入队操作
  2. stack1压入完成后弹出并将stack1中所有元素压入到stack2(此时已经为顺序,且stack2栈顶为队头)
  3. stack2如果不为空,直接进行弹出,即为出队操作
  4. 如果stack2为空,进行步骤2的操作,如果两个栈stack1stack2都为空,则队列为空

示意图如下:

在这里插入图片描述

2个栈实现队列的最大容量

我们令stack1stack2的容量分别为pq,其中stack1的容量更大–p更大些

根据们在上一步的分析:

若要使stack1中的元素要按照队列的顺序弹出,stack1中的元素必须先压入stack2才能实现顺序出队

因此:

stack2已经满,而stack1中还能压入元素,则stack1中压入的元素不能超过stack2的容量,此时队列的容量为2*q(q<p),如下图所示:

在这里插入图片描述

但这里我们假定stack2为负责出队的栈,而如果stack1也可以负责出队的话,则stack1还能再压入一个元素(stack1中的元素全部压入stack2后从stack1出队,再从stack2出队),依然能够满足队列的要求

如下图所示:
在这里插入图片描述

因此,使用两个栈实现队列的最大容量为容量较小的栈的容量*2+1

用2个栈实现队列的C++代码

使用了C++语言进行了实现,完整代码见

代码运行效果如下:

在这里插入图片描述

拓展—牛客网题目链接

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

class Solution{
public: void push(int node) {
stack1.push(node); } int pop() {
int res; if(!stack2.empty()){
res=stack2.top(); stack2.pop(); }else if(!stack1.empty()){
while(!stack1.empty()){
stack2.push(stack1.top()); stack1.pop(); } res=stack2.top(); stack2.pop(); } return res; }private: stack
stack1; stack
stack2;};
运行时间:2ms占用内存:504k

转载地址:https://blog.csdn.net/Jeaten/article/details/107977378 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:N皇后问题的求解 — 回溯法C++实现
下一篇:重建二叉树C++实现

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年02月28日 12时23分51秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

冒泡排序面向对象java_所谓的面向对象实现的冒泡排序 2019-04-21
proto 客户端 JAVA_Kubernetes官方java客户端之五:proto基本操作 2019-04-21
java编写roguelike_RogueLike地牢生成算法Unity实现 2019-04-21
java ajax 修改数据库数据库数据库_AJAX 自学练习 无刷新提交并修改数据库数据并显... 2019-04-21
java并发编程指南博客_Java并发编程-synchronized指南 2019-04-21
java怎么中断阻塞状态_java并发编程()阻塞方法与中断方法 2019-04-21
java zlib 位运算_位运算入门:找出一个二进制数的最右端的第一个1;计算一个二进制数中1的个数;找出数组中唯一一个出现次数为奇数的数;找出数组中唯二两个出现次数为奇数的数... 2019-04-21
java lua热更新_lua热更新学习 2019-04-21
script执行php文件_php命令行(cli)下执行PHP脚本文件的相对路径的问题解决方法... 2019-04-21
apache 2.4 php5.4_apache2.4+php5.4+my sql 5.6,网站经常无故不能访问 2019-04-21
php apc.dll下载,PHP之APC缓存详细介绍 apc模块安装 2019-04-21
html贝塞尔曲线在线,贝塞尔曲线的一些事情_html/css_WEB-ITnose 2019-04-21
Java前台显示近20天的东西_第十次课:前台首页设计及显示商品信息 2019-04-21
java开发web网站的路由设计_理解Web路由(浅谈前后端路由与前后端渲染) 2019-04-21
excel如何把顺序倒过来_在excel中怎么使文字颠倒顺序反过来显示呢? 2019-04-21
php正则表达式获取图片路径,php 常用正则表达式实例(图片地址,与指定内容获取)... 2019-04-21
脚本语言php是什么意思,PHP脚本语言 2019-04-21
matlab数学规划模型,数学规划模型 2019-04-21
视频提取音频php,如何提取视频中的音频,从视频文件中提取出音频输出成MP3格式... 2019-04-21
diy.php添加验证码,织梦dedecms自定义表单中加入验证码 2019-04-21