[整理III]微软等100题系列V0.1版之三:栈、堆、队列面试题集锦
July
==============
2.设计包含min函数的栈。
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
29.栈的push、pop序列
题目:输入两个整数序列。其中一个序列表示栈的push顺序,
判断另一个序列有没有可能是对应的pop顺序。
为了简单起见,我们假设push序列的任意两个整数都是不相等的。
比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。
因为可以有如下的push和pop序列:
push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,
这样得到的pop序列就是4、5、3、2、1。
但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
34.
实现一个队列。
队列的应用场景为:
一个生产者线程将int类型的数入列,一个消费者线程将int类型的数出列
35.
求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码
57.用俩个栈实现队列。
题目:某队列的声明如下:
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;
};
分析:从上面的类的声明中,我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,
因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,
我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。
66.颠倒栈。
题目:用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5},1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1},5处在栈顶。
-----------------------------------------------------
1.关于本微软等公司数据结构+算法面试100题系列V0.1版的郑重声明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
2.完整100题,请参见,
[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
3.更多详情,请参见,本人博客:
My Blog:
http://blog.csdn.net/v_JULY_v
4.所有的资源(题目+答案)下载地址:
http://v_july_v.download.csdn.net/
5.本微软等100题系列V0.1版,永久维护(网友,思路回复)地址:
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html
作者声明:
本人July对本博客所有任何内容和资料享有版权,转载请注明作者本人July及出处。
永远,向您的厚道致敬。谢谢。July、二零一零年十二月十七日。
分享到:
相关推荐
结合uCOS-III和循环队列的串口数据收发方式,实时性好。接收方面,使用STM32的总线空闲中断判断数据包接收完毕并发布消息,使用状态机检查数据包正误。发送方面,采用中断的方式发送数据,避免程序死等数据发送完毕...
NXP i.MX RT1052 uCOSIII实战。NXP i.MX RT1052驱动程序。资源代码可直接编译、运行。
c语言面试题 c语言面试题之双指针反转字符串中的单词III
IP 地址 : 192.168.0.1 子网掩码 : 255.255.255.0 处理器型号 : 486DX or Compatible 内存大小 : 8 MB 内部网络设备 : RealTek RTL8139(A/B) 10/100M PCI Ethernet 外部网络协议 : 固定 IP 地址 外部网络...
PHP经典面试题(基础型III)附答案 PHP经典面试题(基础型)附答案.pdf A popular general-purpose scripting language that is especially suited to web development. Fast, flexible and pragmatic, ...
uCOS-III V3.03.01 uCOS-II V2.92.07在STM32F2移植
uCOS-III V3.03.01 uCOS-II V2.92.07在STM32F1移植
【美团】Java 岗 154 道面试题(2.0版) 100 期 Java 面试题汇总 文章推荐: Java后端优质文章推荐 设计模式: 从零开始单排学设计模式「UML类图」定级赛 从零开始单排学设计模式「简单工厂设计模式」黑铁 III 从...
NXP i.MX RT1052 uCOSIII实战。NXP i.MX RT1052驱动程序。资源代码可直接编译、运行。
FANUC LADDER-III V8.0最新版 FANUC梯形图软件最新版
ThinkPad -- Integrated Bluetooth III微软蓝牙
原子哥战舰版整理的UCOSIII文档资料,内含有UCOSIII源码及其思维导图,各主要知识点总结等
μC/OS-III (pronounced “Micro C O S Three) is a scalable, ROMable, preemptive real-time kernel that manages an unlimited number of tasks. μC/OS-III is a third-generation kernel and offers all of the...
百度mp3批量下载III V8.4
多参数智能监测数据库(MIMIC-III)是一个免费开放的、公共资源的重症监护室研究数据库。 内容概要:本资源包含数据集中的三个表格,PATIENTS,CHARTEVENTS和LABEVENTS,表格的说明可参考 ...
uCOS-III 系统下 消息队列 源码
STM32F103ZET6单片机UCOSIII系统实验例程18例源码+开发板原理图: STM32F103ZET6单片机开发板PDF原理图.pdf 官方 uCOS-III 源码.zip 实验10:UCOSIII-互斥信号量.zip 实验11:UCOSIII-消息队列.zip 实验12:UCOSIII-...
在本文中,考虑了开发高效的基于Si和III-V的太阳能电池的一些新机会:在Si中形成pn结的节能环保型低温技术(1),结构完美的阐述GaAs / Ge / Si外延衬底(2)和基于立方氧化锆的保护性抗反射涂层的应用(3)。...
半导体材料课件:第8章 III-V族多元化合物半导体.pdf
简单的数据结构,主要有链表、栈、队列以及常见的排序算法