- 浏览: 897893 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (537)
- Java SE (114)
- Struts (18)
- Hibernate (25)
- Spring (3)
- Page_Tech (41)
- Others (87)
- Database (29)
- Server (24)
- OpenSource_Tools (15)
- IDE_Tool (22)
- Algorithm (28)
- Interview (22)
- Test (28)
- Hardware (1)
- Mainframe (25)
- Web application (4)
- Linux (3)
- PHP (17)
- Android (1)
- Perl (6)
- ubuntu (1)
- Java EE (9)
- Web Analysis (5)
- Node.js (2)
- javascript (2)
最新评论
-
一键注册:
request.getRequestURL()和request.getRequestURI() -
SuperCustomer:
...
SED的暂存空间和模式空间 -
juyo_ch:
讲得挺好理解的,学习了
java 死锁及解决 -
chinaalex:
最后一题答案正确,但是分析有误.按照如下过程,上一行为瓶,下一 ...
zz智力题 -
liaowuxukong:
多谢博主啦,弱弱的了解了一点。
C++/Java 实现多态的方法(C++)
题目:某队列的声明如下:
- template<typename T> 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;
- };
template<typename T> 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; };
分析:从上面的类的声明中,我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。
我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素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。不会出现任何矛盾。
我们用一个表来总结一下前面的例子执行的步骤:
操作
m_stack1
m_stack2
append a
{a}
{}
append b
{a,b}
{}
append c
{a,b,c}
{}
delete head
{}
{b,c}
delete head
{}
{c}
append d
{d}
{c}
delete head
{d}
{}
总结完push和pop对应的过程之后,我们可以开始动手写代码了。参考代码如下:
- ///////////////////////////////////////////////////////////////////////
- // Append a element at the tail of the queue
- ///////////////////////////////////////////////////////////////////////
- template<typename T> void CQueue<T>::appendTail(const T& element)
- {
- // push the new element into m_stack1
- m_stack1.push(element);
- }
- ///////////////////////////////////////////////////////////////////////
- // Delete the head from the queue
- ///////////////////////////////////////////////////////////////////////
- template<typename T> void CQueue<T>::deleteHead()
- {
- // if m_stack2 is empty,
- // and there are some elements in m_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);
- }
发表评论
-
IGT JAVA Test
2012-06-18 10:18 01. static synchronized vs synch ... -
zz IBM 面试问题
2012-05-30 14:31 9391.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 848面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 754堆:顺序随意栈:先进 ... -
淘宝面试的几个算法题
2010-10-21 11:27 1451一、给你1副扑克牌,你 ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 978题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1792题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 863题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1426题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2010-10-18 22:38 870题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 950题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2010-10-18 22:36 1315题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1011题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1124题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 952题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1152题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 760题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1416题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 823题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2010-10-18 22:20 833题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ...
相关推荐
C/C++面试题库,eg:题目:某队列的声明如下。分析从上面的类的声明中,我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。
面试题12:能否用两个栈实现一个队列的功能 10.5 二叉树 面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现...
C++面试题 1.是不是一个父类写了一个virtual 函数,如果子类覆盖它的函数不加virtual ,也能实现多态? virtual修饰符会被隐形继承的。 private 也被集成,只事派生类没有访问权限而已 virtual可加可不加 子类的...
左程云《程序员代码面试指南》第二版编程题的Python语言实现 牛客网OJ: LeetCode: 1、故下面除特殊说明,否则OJ链接均默认为LeetCode对应题目链接。因为牛客网OJ在链表、二叉树等相关题目均把题目数据以链表数据...
根据我两个半月找工作笔试面试经验吐血整理好的最常考的C/C++基本程序题(尤其适合嵌入式软件岗位的同学),几乎囊括了链表堆栈队列二叉树字符串排序所有基本程序,可直接打印成小抄,楼主自从有了这个基本上笔试必...
07用两个栈实现队列 08旋转数组的最小数字 09斐波那契数列 09跳台阶 09变态跳台阶 09矩阵覆盖 10二进制中1的个数 11数值的整数次方 14调整数组顺序使奇数位于偶数前面 15链表中倒数第k个结点 16反转链表 17合并两个...
C++面试题 参考:http://blog.csdn.net/Ghost90/archive/2009/04/22/4099672.aspx 整理:松鼠 时间:2009-5-8 1、const 有什么用途?(请至少说明两种) 答: (1)可以定义 const 常量 (2)const可以修饰函数的...
leetcode 剑指 Offer 50 ...用两个栈实现队列 - - leetcode 232 | lintcode 40 旋转数组的最小数字 - - leetcode 153 | lintcode 159 斐波那契数列 - - leetcode 509 | lintcode 366 二进制中 1 的
18_栈的属性和buf地址增长方向是两个不同的概念 19_函数调用模型_主调函数和被调用函数 20_课堂答疑_函数调用流程入栈出栈过程 21_指针也是一种数据类型_基础 22_指针也是一种数据类型_强化_传智扫地僧 源码及文档 ...
实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句在数组中搜索指定图书 42 第3章 字符串处理技术 44 3.1 字符及字符串转换 45 实例035 将字母全部转换为大写或小写 45 ...
通过作业,定时同步两个数据库 SQLSERVER高级注入技巧 利用反射实现ASP.NET控件和数据实体之间的双向绑定,并且在客户端自动验证输入的内容是否合法 asp.net报表解决方法 SQLDMO类的使用 SQL过程自动C#封装,支持从表到...
面试中手写算法题考察的其实是三个方面,『数据结构』,『编程语言』,『算法』。优秀的程序员应该具备这三方面的能力。 我希望跟随者书本题目的练习和总结,利用github新建这个项目,为自己的算法学习立一个规划。 ...
在Java语言中重要的两个以SOAP技术开始的网络服务框架XFire和Axis也把REST作为自己的另一种选择。它们的新的项目分别是ApacheCXF和Axis2.Java语言也制定关于REST网络服务规范:JAX-RS:JavaAPIforRESTfulWebServices...