算法导论上的课后题 两个栈模拟队列
这个原来做过 一般是这样 我看网上大概都是这种解法
原来栈空
a b
null null
1,2,3入站的时候入a
a b
3 null
2 null
1 null
出战的时候先进b 然后pop b 在调过来进a
a b
null 1
null 2
null 3
继续
a b
3 null
2 null
这样的话 入队列是o(1) 出队列o(2n) 有点不平衡
我想了一种出入栈都是o(n)的 灵感是来自两个队列模拟栈的 主要就是互相出入队列的时候都向另一个栈导入
入站的时候先把战中的元素调到另一个战中 在入站 出战的时候先pop出栈 再把剩下的元素调到另一个战中 还需要一个标示那个栈是存着元素的
以1,2,3入栈为例
a b
null null
a b
1 null
a b
null 2
null 1
a b
3 null
1 null
2 null
出队列
a b
null 2
null 1
pop = 3
再出的话
pop=2
a b
1 null
这样 出入队列都是o(n) 比较平衡 当然根据不同的需求再选择不同的算法:)
突然又想到。。这个都是能控制的 也可以入栈o(2n) 出栈o(1) 都行。。。
分享到:
相关推荐
基于c语言数据结构中栈和队列思想的简单停车场管理系统,以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车...
因此本题中用到两个栈和一个队列。 对于停车场和车辆规避所,有车辆进入和车辆离去两个动作,这就是栈的进栈和出栈操作,只是还允许排在中间的车辆先离开停车场,因此在栈中需要进行查找。而对于便道,也有入队列和...
本文实例讲述了JS实现利用两个队列表示一个栈的方法。分享给大家供大家参考,具体如下: 先看原理图: 理清楚思路,再动笔写: <!DOCTYPE html> <html> <head> <title>2 Queue</title>...
//用两个栈实现一个队列的功能 //栈s1提供入队列的功能,栈s2提供出队列的功能 //入队列:如s1 //出队列:(1)如果s2不为空,则直接弹出栈s2的数据(2)如果栈s2为空,则依次弹出栈s1的数据,放入s2中,再弹出栈s2的...
一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题...2、编程模拟队列的管理,主要包括:出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。
试用java.util.Stack泛型栈作为父类,用另一个泛型栈对象作为成员变量,模拟实现一个泛型子类Queue,当存储元素的第1个栈的元素超过dump时,再有元素入队列就倒入第2栈。除提供无参构造函数Queue( )外,其它所有队列...
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 思路 根据栈的特性...
建立一个栈列表和队列列表结构,并分别设计这两个列表的判断列表空、判断列表满及进行初始化的函数,先对St,Qu,St1三个列表进行初始化,栈列表St表示的是停车场,队列Qu代表候车场,当停车场里有空位的时候利用...
以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达和离去的时刻。对每一组输入数据进行操作后...
下面我们通过两段代码简单看一下递归和非递归的区别: 输入一个大于等于1的数,求1到n的和! # 普通函数方法 def hanshu(n): sum = 0 # 循环遍历每一个数字,将他们加到一个事先定义好的变量上,直到加完 ...
构建一个栈用以表示乘客,用等待队列表示电梯外等待的乘客 (2)算法设计 1.乘客类型反映乘客的所有属性 2乘客栈类型,电梯内的乘客用乘客栈表示,去不同楼层的乘客放在不同的栈中。 3.等候队列类型,在电梯外等待...
剑指offer9-用两个栈模拟队列 165-比较版本号 1-两数之和 2-两数相加 双指针 26-删除排序数组中的重复项 42-接雨水 动态规划 5-最长回文子串 最大子序和 322-零钱兑换 1024-视频拼接 剑指offer63-股票的最大利润 剑...
2.设计并实现算法,利用队列模拟课件中案例 3.4 的舞伴配对问题。 问题描述如下: 假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从 男队和女队的队头上各出一人配成舞伴。若两队...
题目:两个栈模拟一个队列,剑指offer书中的题目,用java写的
当滑动窗口为0时,发送方一般不能再发送数据包,但有两种情况除外,一种情况是可以发送紧急数据,例如,允许用户终止在远端机上的运行进程。另一种情况是发送方可以发送一个1字节的数据报来通知接收方重新声明它希望...
编制一个程序模拟银行的这种业务活动并计算一天中客户在银行的平均逗留时间。 提示:客户的到来的时间和办理业务时间可用随机数生成。 数据结构:用队列实现客户排队。用链表实现客户到来和离开事件表。
(1) 两个栈共享空间,思考应开辟数组的空间是多少? (2) 汽车可有不同种类,则它们的占地面积不同,收费标准也不同,如1辆客车和1.5辆小汽车的占地面积相同,1辆十轮卡车占地面积相当于3辆小汽车的占地面积...
如果两个元素具有相同的优先级,则它们按照它们在队列中的顺序出队。 优先队列在许多算法和数据结构中都有广泛的应用,包括图搜索算法(如Dijkstra算法和Prim算法)、任务调度、事件驱动模拟等。在这些应用中,优先...
由于停车场只有一个大门,当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,先进停车场的后退出,后进...因此,本题求解过程中需用到两个栈和一个队列。栈以顺序结构实现,队列以链表结构实现。