UDN-企业互联网技术人气社区

板块导航

浏览  : 860
回复  : 1

[资源] web前端开发面试题及答案①

[复制链接]
cat77的头像 楼主
本帖最后由 cat77 于 2016-9-7 10:19 编辑

  C++面试 利用两个栈实现1个队列

  1、题目 利用两个栈实现一个队列

  2、要求 只能使用栈的pop(),top()和push(),以及测试栈是否为空empty()四个操作. 来实现队列的empty(), push(),pop(),back(),front()等操作。

  3、准备 做这道题之前先分别了解下栈和队列相关知识点。queue 是一种先进先出(first in first out, FIFO)的数据类型,他有两个口,数据元素只能 从一个口进,从另一个口出.队列只允许从队尾加入元素,队头删除元素,必须符合先进先 出的原则,queue 和 stack 一样不具有遍历行为。如下图所示:
1.jpg

  stack 是一种先进后出(first in last out,FILO)的数据结构,它只有一个出口,stack 只允许在栈顶新增元素,移除元素,获得顶端元素,但是除了顶端之外,其他地方不允许存取 元素,只有栈顶元素可以被外界使用,也就是说 stack 不具有遍历行为,没有迭代器。

  4、思路总结实现队列的pop方法弹出队头元素:stack是一个口进出,也不支持随机存取,所以你无法直接从栈底拿到第一个元素。要想拿到第一个元素,需要将左边栈容器中的所有元素拷贝到右边栈容器中。由于stack先进后出的数据结构,这样左边容器的第一个元素会作为最后一个元素存储到右边栈容器中,这样不就拿到左边栈容器中的第一个元素了吗 ?

  实现队列的back方法获取队列的队尾元素:逻辑和思路1一样,唯一不同的是pop和top
1.jpg

  1. //  
  2. //  利用两个栈实现⼀个队列.cpp  
  3. //  c++  
  4. //  
  5. //  Created by 刘龙玲 on 16/1/29.  
  6. //  Copyright © 2016年 liulongling. All rights reserved.  
  7. //  
  8.   
  9. #include <iostream>  
  10. #include <stack>  
  11.   
  12. using namespace std;  
  13.   
  14.   
  15. template <class T>  
  16. class MyQueue  
  17. {  
  18. public:  
  19.     bool empty()const  
  20.     {  
  21.         return head.empty()&&tail.empty();  
  22.     }  
  23.       
  24.     void push(T t)  
  25.     {  
  26.         head.push(t);  
  27.     }  
  28.       
  29.     //删除对头元素  
  30.     //因为queue是一种先进先出,而stack是先进后出,所以需要把head里的数据拷贝到tail中然后再从tail中pop头元素  
  31.     void pop()  
  32.     {  
  33.         if(this->empty())  
  34.         {  
  35.             //throw exception("队列为NULL");  
  36.         }  
  37.         while(!head.empty())  
  38.         {  
  39.             tail.push(head.top());  
  40.             head.pop();  
  41.         }  
  42.         //删除头元素  
  43.         tail.pop();  
  44.          
  45.         //再将队尾栈容器元素拷贝到队头栈容器中  
  46.         while(!tail.empty())  
  47.         {  
  48.             head.push(tail.top());  
  49.             tail.pop();  
  50.         }  
  51.     }  
  52.       
  53.     T& back()  
  54.     {  
  55.         if(this->empty())  
  56.         {  
  57.            // throw exception("head is NULL");  
  58.         }  
  59.         return head.top();  
  60.     }  
  61.       
  62.     //返回第一个元素  
  63.     T& front()  
  64.     {  
  65.         if(this->empty())  
  66.         {  
  67.             //throw exception("队列为NULL");  
  68.         }  
  69.         while(!head.empty())  
  70.         {  
  71.             tail.push(head.top());  
  72.             head.pop();  
  73.         }  
  74.          
  75.        int tmp =  tail.top();  
  76.          
  77.         //再将队尾栈容器元素拷贝到队头栈容器中  
  78.         while(!tail.empty())  
  79.         {  
  80.             head.push(tail.top());  
  81.             tail.pop();  
  82.         }  
  83.   
  84.         return tmp;  
  85.     }  
  86.       
  87. private:  
  88.     stack<int> head;  
  89.     stack<int> tail;  
  90. };  
  91.   
  92. int main()  
  93. {  
  94.     MyQueue<int> q;  
  95.     for(int i=1;i<5;i++)  
  96.     {  
  97.         q.push(i);  
  98.     }  
  99.       
  100.     cout<<"front:"<<q.front()<<endl;  
  101.     cout<<"back:"<<q.back()<<endl;  
  102.       
  103.     return 0;  
  104. }
复制代码

相关帖子

发表于 2016-9-7 10:55:17 | 显示全部楼层
赞一个
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部