数据结构和算法基础篇（五）栈

之前我们谈了很多递归的算法思路，也讲到了数组、链表等数据结构。今天我们来说一说栈相关的操作，并以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. 逆波兰表达式求值（中等难度）