Java面试题:栈和队列的实现

面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容:

(1)栈的创建

(2)队列的创建

(3)两个栈实现一个队列

(4)两个队列实现一个栈

(5)设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)

(6)判断栈的push和pop序列是否一致

1、栈的创建:

我们接下来通过链表的形式来创建栈,方便扩充。

代码实现:

入栈操作时,14、15行代码是关键。

运行效果:

2、队列的创建:

队列的创建有两种形式:基于数组结构实现(顺序队列)、基于链表结构实现(链式队列)。

我们接下来通过链表的形式来创建队列,这样的话,队列在扩充时会比较方便。队列在出队时,从头结点head开始。

代码实现:

入栈时,和在普通的链表中添加结点的操作是一样的;出队时,出的永远都是head结点。

运行效果:

3、两个栈实现一个队列:

思路:

栈1用于存储元素,栈2用于弹出元素,负负得正

说的通俗一点,现在把数据1、2、3分别入栈一,然后从栈一中出来(3、2、1),放到栈二中,那么,从栈二中出来的数据(1、2、3)就符合队列的规律了,即负负得正。

完整版代码实现:

注意第22行和第30行代码的顺序,以及注释,需要仔细理解其含义。

运行效果:

4、两个队列实现一个栈:

思路:

将1、2、3依次入队列一, 然后最上面的3留在队列一,将下面的2、3入队列二,将3出队列一,此时队列一空了,然后把队列二中的所有数据入队列一;将最上面的2留在队列一,将下面的3入队列二。。。依次循环。

代码实现:

运行效果:

5、设计含最小函数min()的栈,要求min、push、pop、的时间复杂度都是O(1)。min方法的作用是:就能返回是栈中的最小值。【微信面试题】

普通思路:

一般情况下,我们可能会这么想:利用min变量,每次添加元素时,都和min元素作比较,这样的话,就能保证min存放的是最小值。但是这样的话,会存在一个问题:如果最小的元素出栈了,那怎么知道剩下的元素中哪个是最小的元素呢?

改进思路:

这里需要加一个辅助栈,用空间换取时间。辅助栈中,栈顶永远保存着当前栈中最小的数值。具体是这样的:原栈中,每次添加一个新元素时,就和辅助栈的栈顶元素相比较,如果新元素小,就把新元素的值放到辅助栈中,如果新元素大,就把辅助栈的栈顶元素再copy一遍放到辅助栈的栈顶;原栈中,出栈时,

完整代码实现:

6、判断栈的push和pop序列是否一致:

通俗一点讲:已知一组数据1、2、3、4、5依次进栈,那么它的出栈方式有很多种,请判断一下给出的出栈方式是否是正确的?

例如:

数据:

1、2、3、4、5

出栈1:

5、4、3、2、1(正确)

出栈2:

4、5、3、2、1(正确)

出栈3:

4、3、5、1、2(错误)

完整版代码:

代码比较简洁,但也比较难理解,要仔细体会。

运行效果:

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2016-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏飞雪无情的博客

Go语言参数传递是传值还是传引用

其实对于传值和传引用,是一个比较古老的话题,做研发的都有这个概念,但是可能不是非常清楚。对于我们做Go语言开发的来说,也想知道到底是什么传递。

2373
来自专栏个人分享

Scala第四章学习笔记(面向对象编程)

DelayedInit特质是为编译器提供的标记性的特质。整个构造器被包装成一个函数并传递给delayedInit方法。

881
来自专栏我是攻城师

再谈方法调用与堆栈

堆内存是被多个线程共享的,而栈内存是线程私有的。堆主要用来存储运行时所有的对象数据和各种数组,简单点说通过new创建的实例,都会在堆上分配空间。堆在虚拟机启动时...

1051
来自专栏Golang语言社区

Go语言学习之cgo(golang与C语言相互调用)

几乎所有的编程语言都有C语言的影子,当然golang也不例外。可以看到golang的创始者们与c language有着密切的联系。所有,golang和c语言的相...

5897
来自专栏一个会写诗的程序员的博客

Kotlin 中 有趣 好玩的高阶函数《Kotlin极简教程》正式上架:

922
来自专栏偏前端工程师的驿站

Java魔法堂:深入正则表达式API

目录                               一、前言 二、正则表达式的使用诉求 三、java.util.regex包 四、java.lan...

2115
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻block的本质(二)

3014
来自专栏编程

程序员工作三年想涨薪,却因为小细节没注意,被直接开除!

前 言 需求是暂时的,只有变化才是永恒的,面向变化编程,而不是面向需求编程。 不要过分追求技巧,降低程序的可读性。 简洁的代码可以让bug无处藏身。要写出明...

1918
来自专栏个人分享

工程开发实用类与方法总结(未完)

1 .checkArgument(boolean) :   功能描述:检查boolean是否为真。 用作方法中检查参数   失败时抛出的异常类型: Illeg...

1123
来自专栏我是攻城师

Java开发者如何正确的使用String,StringBuffer,StringBuilder类

通过前面的文章,我们知道String类最大的特点是不可变性,这意味着对String类的任何修改都会新生成一个字符串,比如你执行了String类的substrin...

965

扫码关注云+社区

领取腾讯云代金券