首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某队列的声明如下: template class CQueue { public: CQueue() {} ~CQueue() {} void appendTail(const T& node); // append a element to
某队列的声明如下: template class CQueue { public: CQueue() {} ~CQueue() {} void appendTail(const T& node); // append a element to
admin
2019-03-29
136
问题
某队列的声明如下:
template
class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T>m_stack1;
T>m_stack2;
};
选项
答案
/////////////////////////////////////////////////////////////////////// // Append a element at the tail of the queue /////////////////////////////////////////////////////////////////////// template
void CQueue
::appendTail(const T& element) { // push the new element into m_stack1 m_stack1.push(element); } /////////////////////////////////////////////////////////////////////// // Delete the head from the queue /////////////////////////////////////////////////////////////////////// template
void CQueue
::deleteHead() { // if m_stack2is empty,and there are some //elements inm_stack1, push them in m_stack2 if(m_stack2.size()<= 0) { while(m_stack1.size()>0) { T&data =m_stack1.top(); m_stack1.pop(); m_stack2.push(data); } } // push theelement into m_stack2 assert(m_stack2.size()>0); m_stack2.pop(); }
解析
从上面的类的声明中,我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。
我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素a,不妨把先它插入到m_stack1。这个时候m_stack1中的元素有{a},m_stack2为空。再插入两个元素b和c,还是插入到m_stack1中,此时m_stack1中的元素有{a,b,c},m_stack2中仍然是空的。
这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则,由于a比b、c先插入到队列中,这次被删除的元素应该是a。元素a存储在m_stack1中,但并不在栈顶上,因此不能直接进行删除。注意到m_stack2我们还一直没有使用过,现在是让m_stack2起作用的时候了。如果我们把m_stack1中的元素逐个pop出来并push进入m_stack2,元素在m_stack2中的顺序正好和原来在m_stack1中的顺序相反。因此经过两次pop和push之后,m_stack1为空,而m_stack2中的元素是{c,b,a}。这个时候就可以pop出m_stack2的栈顶a了。pop之后的m_stack1为空,而m_stack2的元素为{c,b},其中b在栈顶。
这个时候如果我们还想继续删除应该怎么办呢?在剩下的两个元素中b和c,b比c先进入队列,因此b应该先删除。而此时b恰好又在栈顶上,因此可以直接pop出去。这次pop之后,m_stack1中仍然为空,而m_stack2为{c}。
从上面的分析我们可以总结出删除一个元素的步骤:当m_stack2中不为空时,在m_stack2中的栈顶元素是最先进入队列的元素,可以pop出去。如果m_stack2为空时,我们把m_stack1中的元素逐个pop出来并push进入m_stack2。由于先进入队列的元素被压到m_stack1的底端,经过pop和push之后就处于m_stack2的顶端了,又可以直接pop出去。
接下来我们再插入一个元素d。我们是不是还可以把它push进m_stack1?这样会不会有问题呢?我们说不会有问题。因为在删除元素的时候,如果m_stack2中不为空,处于m_stack2中的栈顶元素是最先进入队列的,可以直接pop;如果m_stack2为空,我们把m_stack1中的元素pop出来并push进入m_stack2。由于m_stack2中元素的顺序和m_stack1相反,最先进入队列的元素还是处于m_stack2的栈顶,仍然可以直接pop。不会出现任何矛盾。
我们用一个表来总结一下前面的例子执行的步骤:
[16*]
总结完push和pop对应的过程之后,我们可以开始动手写代码了。
转载请注明原文地址:https://kaotiyun.com/show/zRmZ777K
0
程序员面试
相关试题推荐
RememberNapsterorGrokster?Bothservicesalloweduserstosharecomputerfiles—usuallydigitalmusic—thatinfringedthecopyr
Signslike"Pleaseratemefivestars"pointtoagrowingproblemwithbusinessesintheon-demandeconomyofapp-basedservices
Asthelatestcropofstudentspentheirundergraduateapplicationformandweighuptheiroptions,itmaybeworthconsidering
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 比如将二元查找树10
重载与覆盖的区别
邮件的删除。
在金山毒霸2008中,手动查杀“移动存储设备”中的病毒木马。
对于PPoint中的超链,以下说法错误的是()。A.利用超级链接可跳转到同一演示文稿中任一张幻灯片B.利用超级链接可跳转到别的演示文稿C.利用超级链接可跳转到某个Internet地址D.利用超级链接只能跳转到文件类型为.ppt的文件
在计算机的应用中,cad是指()。A.计算机辅助制造B.计算机辅助教学C.计算机辅助设计D.计算机辅助测试
论逻辑网络设计过程中财用户需求的把握对于网络规划设计工程师来说,在把某项工作系统化的时候,正确地理解该项工作的内容并设计出有效的系统,是一件最困难的事情。为了把用户的需求正确无误地反映到网络工程项目的逻辑设计文档中,常规的做法是将该工程项目的需求说
随机试题
我国立法上将犯罪分为10类.并通过刑法分则第一至十章分别予以论述,这种分类主要是依据()。
皮下注射
患者,男性,52岁。近半年来常于劳累后感疲乏,伴劳力性呼吸困难和发作性心前区闷痛,休息后稍好转。外院诊断为“心律失常二度Ⅱ型房室传导阻滞”,治疗情况不详。半天前,患者突然发生晕厥,伴抽搐,查体:心率30次/分,血压85/55mmHg,急诊以“晕厥待查”收
女性,38岁。3年前确诊急性早幼粒细胞白血病。经全反式维A酸治疗30天取得完全缓解,后DA、HA等方案化疗与维A酸交替进行巩固治疗2年。近一周又出现咽痛、高热。查体:咽充血明显。双肺未闻及干、湿性啰音。血象:WBC2.0×109/L,Hb105g/L,PL
社区健康教育的目标是
影响水泥体积安定性的因素有()。
某高新技术企业成立于2013年,当年发生业务(1)资金账簿记载实收资本为700万元、资本公积30万元.新启用其他账簿15本,办理了房尾产权证和工商营业执照各一本;(2)2月份发生购进业务,购进原材料85万元.4月份发生销售业务,销售额234.43万元,
下列合同中,应按“产权转移书据”税目征收印花税的有()。
事业单位发生的下列各项中,不会引起专用基金发生增减变化的是()。
请你用不超过300字的篇幅概括出我国能源存在的问题。概括的文字要精练,语言要流畅,内容要客观。请你针对我国存在的能源问题提出对策或者建议。要求:有针对性,切实合理,条理清楚,语言流畅,字数在450字左右。
最新回复
(
0
)