C/C++之用两个栈实现一个队列的功能

发表于:2014-4-16 10:33

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:骄傲的倔强    来源:51Testing软件测试网采编

  问题:有两个栈s1和s2,实现队列的push和pop功能。
  一般思路:始终维护s1作为存储空间,并以s2作为临时缓冲区。s1实现入队操作,s2实现出队操作。
  1,入队时,将元素压入s1。
  2,出队时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素作为出队元素,之后再将s2剩下的元素逐个“倒回”s1中。
  见下面示意图:
  上述思路,可行性毋庸置疑,但是有一个小细节可以优化。即:在出队时,将s1元素逐个“倒入”s2时,原来在s1中最后一个元素不用“倒入”s2中(即只需倒入s1.Count()-1个即可),可以直接将其弹出作为出队元素返回。这样可以减少一次压栈操作。
  思路变种,如下:
  入队时,先判断s1是否为空,如不为空,说明所有元素都在s1,此时将入队元素直接压入s1;如为空,要将s2的元素逐个“倒回”s1,再压入入队元素。
  出队时,先判断s2是否为空,如不为空,直接弹出s2的顶元素并出队;如为空,将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
  相对于第一种方法,变种的s2好像比较“懒”,每次出队后,并不将元素“倒回”s1,如果赶上下次还是出队操作,效率会高一些,但下次如果是入队操作,效率不如第一种方法。
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号