1.注意: * 栈中: push是压栈,peek是返回栈顶元素,pop是弹栈. * 队列中: offer是进队列,poll是出队列,peek是返回队列首元素. * linkedlist实现了queue接口,所以我们可以把linkedlist当作队列来使用.其中queue接口和list,set接口一样都是继承自collection接口.
实现一个特殊的栈,在实现栈的基础功能的基础上,再实现返回栈中最小元素的操作.
要求:
pop, push, getMin操作的时间复杂度都是O(1).设计的栈类型可以使用现成的栈结构.思路: 设计两个栈,一个和正常栈一样放数据,另一个用来放最小值
每次数据栈中有数进来的时候,就和最小值栈中的栈顶元素比较,当数据栈栈顶元素>最小值栈栈顶元素的时候,最小值栈再存入一个当前栈顶元素,反之存入数据栈栈顶元素.如图: 特殊栈找最小元素图解.代码.
如何用队列结构实现栈结构?
思路:
用两个队列,当push的时候,就放在其中一个队列中,然后要弹栈和返回栈顶元素的时候,将除了最后一个元素的其它元素倒入另一个队列中,然后返回队列中剩余的最后一个元素.队列实现栈结构代码.
看了代码以后要注意的地方:
交换的函数swap不能带参数,带参数之后,它改变的就只是参数,而不是成员变量,就相当于swap没发挥作用,因为变量有就近原则,找离自己进的,有参数的时候找参数哈哈哈.只能将数据队列最后一个参数赋值给一个局部变量然后返回,不能直接返回数据队列的最后一个元素,因为在返回前,数据队列和辅助队列引用交换了如何用栈结构实现队列结构?
思路: 用两个栈,一个栈专门给offer方法用,另一个栈专门给poll和peek方法用,当需要出队列或者返回队列首元素的时候,就把offer方法专用的栈中的数据全部倒入另一个栈中,然后返回和出队列. 注意事项: 专门给poll和peek用的栈有两个注意事项: 倒就要一次性全部倒完.倒的时候要保证该队列为空. 栈结构实现队列代码.