- 浏览: 141184 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
Jonathan樊:
请LZ不要简单的Copy过来,好吧?起码编辑一下啊~~该加的超 ...
直接拿来用!最火的Android开源项目 -
tao71535:
学习了、
不过为还是觉得看视频做例子、
比较好、、
Intent总结
题目:某队列的声明如下:
分析:从上面的类的声明中,我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。
我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素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对应的过程之后,我们可以开始动手写代码了。参考代码如下:
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); }
发表评论
-
微软等数据结构+算法面试100题
2011-02-23 17:48 1899微软等100题系列V0.1版终于结束了。 从2010年10月 ... -
百度11月4日网上笔试题及答案
2010-10-27 22:27 1193编程: 用C语言实现一个revert函数,它的功能是将输入的字 ... -
程序员面试题精选(17)-把字符串转换成整数
2009-08-15 12:00 2353题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。例 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2009-08-15 11:59 2584题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2009-08-15 11:57 1461题目:下面是一个数组 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2009-08-15 11:55 2282题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2009-08-15 11:52 1698题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2009-08-15 11:49 1174题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2009-08-15 11:43 1188题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2009-08-15 11:40 1882题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2009-08-15 11:30 1703题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2009-08-08 21:18 2628题目:求1+2+…+n,要求 ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2009-08-08 21:17 1871题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2009-08-08 21:15 1500题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历 ... -
程序员面试题精选(05)-查找最小的k个元素
2009-08-08 21:14 1712题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2009-08-08 21:12 1249题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(03)-求子数组的最大和
2009-08-08 21:10 1867题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个 ... -
程序员面试题精选(02)-设计包含min函数的栈
2009-08-08 21:08 1771题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最 ... -
程序员面试题精选(01)-把二元查找树转变成排序的双向链表
2009-08-08 20:58 1902题目:输入一棵二元查 ...
相关推荐
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...