- 浏览: 913467 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (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 9651.JAVA内存回收机制 2.抽象类与接口的区别 3. ... -
面试的准备与发挥
2012-04-26 10:00 870面试是一场智力的较 ... -
栈内存和堆内存
2010-10-21 11:55 790堆:顺序随意栈:先进 ... -
淘宝面试的几个算法题
2010-10-21 11:27 1476一、给你1副扑克牌,你 ... -
程序员面试题精选(17)-把字符串转换成整数
2010-10-18 22:44 999题目:输入一个表示整 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2010-10-18 22:41 1826题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2010-10-18 22:41 884题目:下面是一个数组类的声明与实现。请分析这个类有什么问题,并 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2010-10-18 22:40 1449题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2010-10-18 22:38 907题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2010-10-18 22:37 965题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2010-10-18 22:36 1341题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2010-10-18 22:33 1029题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2010-10-18 22:32 1144题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2010-10-18 22:31 980题目:求1+2+…+n,要求不能使用乘除法、for、while ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2010-10-18 22:30 1174题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2010-10-18 22:27 781题目:输入一个整数数 ... -
程序员面试题精选(05)-查找最小的k个元素
2010-10-18 22:24 1439题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2010-10-18 22:22 851题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2010-10-18 22:20 850题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ...
相关推荐
本资源"程序员面试题精选(1-57)"显然是一个汇集了众多面试题目的集合,涵盖了从基础到高级的各种问题,旨在帮助求职者提升自己的技能并顺利通过面试。 首先,我们要理解数据结构的重要性。数据结构是组织和存储数据...
【程序员面试题精选】——用两个栈实现队列 在面试中,经常会出现这样一道题:如何使用两个栈来模拟一个队列的行为。这道题目旨在考察候选者对数据结构的理解,尤其是对栈(LIFO,后进先出)和队列(FIFO,先进先出...
【程序员面试题精选100题】是一份中文Word文档,包含了针对程序员的100道面试题目,这些题目详细解答了如何准备编程面试,尤其是技术面试环节。面试是求职过程中至关重要的一环,它能让雇主直接评估应聘者的技能和...
面试题12:能否用两个栈实现一个队列的功能 10.5 二叉树 面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现...
18. **两个栈实现队列**:使用两个栈模拟队列的入队(push)和出队(pop)操作,当栈A为空时,将栈B中的元素弹出并压入栈A,再进行出队操作。 以上知识点是程序员面试中常见的数据结构和算法问题,掌握它们对于面试...
- 如何在不复制元素的情况下合并两个vector? - 何时使用list,何时使用vector,以及它们各自的优缺点? - 举例说明如何自定义一个函数对象,并在STL算法中使用。 - 描述STL容器的内存管理和效率特点,比如...
- **判断相交**:使用两个指针,一个从一个链表的头开始,另一个从可能的相交点开始,如果最终相遇则相交,否则不相交。 - **计算相交点**:同上,两个指针同时移动,直到相遇点即为相交点。 - **模拟大整数加法*...
根据提供的文件信息,本文将围绕“程序员面试逻辑题”这一主题进行深入探讨,解析与程序员面试相关的逻辑题目及其重要性,帮助求职者更好地准备面试。 ### 知识点一:理解程序员面试逻辑题的重要性 在程序员招聘...
根据提供的文件信息,本文将对“程序员面试100题精选”进行详细的解析与扩展,旨在为准备参加技术面试的程序员提供有价值的参考。 ### 一、程序员面试的重要性 在当前竞争激烈的IT行业中,拥有一份优秀的简历固然...
【程序员面试笔试真题与解析】是一份针对程序员面试准备的重要资源,涵盖了C++和JAVA两个主流编程语言的面试真题及其详细解析。这个压缩包包含两份PDF文档,分别是"程序员面试笔试真题与解析_2017版.pdf"和"Java...
- 使用二分查找,因为旋转后的数组可以看作是由两个有序数组拼接而成。 - 当中间值小于左右两端值时,最小值在左半边。 - 否则,最小值在右半边。 - **算法实现**: ```cpp int findMin(vector<int>& nums) { ...
### 中级程序员必备面试题解析 #### 如何创建一个有序集合 有序集合通常是通过`TreeSet`或`LinkedHashSet`等类实现。`TreeSet`基于红黑树存储元素,可以保证元素的自然排序;而`LinkedHashSet`则是基于哈希表与...
在第232题中,我们需要使用两个栈来模拟一个队列的行为。这个问题的关键在于如何利用栈的特性来实现队列的两个主要操作:入队(enqueue)和出队(dequeue)。 1. 入队(enqueue)操作:将新元素直接压入栈1。这个...
根据给定文件的信息,我们可以提炼出一系列与程序员笔试面试相关的知识点。下面将详细解析这些知识点。 ### 数据结构 1. **非线性数据结构** - **知识点**: 数据结构可以分为线性和非线性两大类。线性数据结构中...
总之,《世界500强面试题+程序员面试宝典》将为程序员提供一个全面的准备平台,帮助他们在激烈的竞争中脱颖而出。通过深入学习和理解其中的内容,不仅可以提升技术实力,也能提高面试的成功率,从而在IT行业中攀登更...
《程序员面试宝典》是一本专门为程序员准备面试所编写的参考资料,它覆盖了算法思想、数据结构以及计算等多个方面,针对程序员在面试过程中可能遇到的问题提供了深入的分析和解答。 首先,在算法思想方面,书中介绍...
【程序员经典面试题】涉及到的是两个常见的编程问题,一个是寻找字符串中第一个只出现一次的字符,另一个是层次遍历二叉树。这两个问题都考察了程序员对于数据结构和算法的理解及应用。 首先,第一个问题——寻找...
《C/C++程序员面试宝典》是一本专为准备C/C++编程面试的求职者精心编写的指南。这本书以PDF格式提供,具有清晰的目录结构,使得读者可以快速定位到感兴趣或需要复习的知识点,有助于高效学习和查阅。在追求理想的...