数据结构和算法基础篇(五)栈

之前我们谈了很多递归的算法思路,也讲到了数组、链表等数据结构。今天我们来说一说栈相关的操作,并以Leetcode上面第12题为例,实现一个可以实现返回最小值的栈。

12. 带最小值操作的栈

描述

实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。

你实现的栈将支持push,pop和min操作,所有操作要求都在O(1)时间内完成。

样例

如下操作:push(1),pop(),push(2),push(3),min(), push(1),min()返回1,2,1

我们首先回顾一下Java中栈的使用,以及方法。如下所示:

栈是一种先进后出(FILO)的数据结构,其主要实现是依赖于Vector,这是一种现场安全的数组结构。其主要方法为判断栈为空(empty)、查看栈顶元素(peek)、删除栈顶元素(pop)、压入一个元素(push)。

我们回头思考这个题目,如何实现一个查看最小值的栈。其中多了一个方法public int min();当调用这个方法时,返回目前栈中的最小值。那我们肯定需要一个栈保存最小值。所以我们需要使用双栈实现。

首先我们需要定义两个栈,分别为stack和minStack。分别保存当前数据和最小值。

(1)push方法实现

当我们调用push方法,需要存放元素时,我们将元素存入stack,同时判断minStack中是否有元素,如果没有元素,当前压入的元素就是最小值。如果有元素,那么就要比较了。反正要保证minStack中存放的都是当前stack中的最小值。

(2)pop方法

当调用pop方法,说明要删除一个元素,那么stack和minStack不为空时,同时删除一个元素即可。

(3)min方法

调用此方法,需要返回栈中的最小值,那么我们直接返回minStack中的栈顶元素即可。因为minStack的长度和stack的长度相同,每当stack压入一个元素或者删除一个元素的时候,minStack也会压入当前的最小值和删除minStack栈顶元素。

代码如下:

publicclassMinStack{

publicMinStack(){

// do intialization if necessarystack =newStack(); minStack =newStack(); }

/* * @param number: An integer * @return: nothing */publicvoidpush(intnumber){

// write your code herestack.push(number);

if(minStack.empty()){ minStack.push(number); }

else{

intTopNumber = minStack.peek();

if(TopNumber

/** @return: An integer

*/publicintpop(){// write your code hereintk=stack.peek(); stack.pop(); minStack.pop();

returnk; }

/* * @return: An integer */publicintmin(){

// write your code herereturn(int)minStack.peek(); }

privateStack stack;

privateStack minStack;}

思考:如果实现一个最大栈呢?

这个题目在Lintcode上面有。可以试试。

还可以练练 LeetCode 495,实现栈;

后续我们还会讲解栈相关算法题:

370. 将表达式转换为逆波兰表达式(高难度)

424. 逆波兰表达式求值(中等难度)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180612G1MZMP00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券